Nemlit 的博客

Nemlit 的博客

By a konjac

题解 P3988 【[SHOI2013]发牌】

posted on 2019-11-08 17:10:25 | under 题解 |

这道题去年联赛就在写此题,省选前尝试用平衡树,都无果,现在重拾此题

不难发现排的相对顺序不会发生改变,而且每一个 $R$ 的实际意义其实是查询当前排名为第 $R$ 的数

我们定义当前牌顶为 $x$ ,每一次操作其实是查询往x后的 $R$ 个数

我们可以先查询x是现在第几大(令此为p),然后就意味着求出 $p+R$ 大的数,注意需要对当前数取模

查出后更新 $x$ ,并且把这个数删掉即可

发现以上所有操作都可以用权值线段树/平衡树实现,复杂度为 $O(NlogN)$

$Code:$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i , a , b) for(int i = (a) , i##Limit = (b) ; i <= i##Limit ; ++ i)
#define ls k * 2
#define rs k * 2 + 1
#define maxn 700007
int n, sum[maxn << 2], now;
il void build(int k, int l, int r) {
    if(l == r) return (void)(sum[k] = 1);
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r), sum[k] = sum[ls] + sum[rs];
}
il void modify(int k, int l, int r, int ll, int v) {
    if(l == r) return (void)(sum[k] += v);
    int mid = (l + r) >> 1;
    if(ll <= mid) modify(ls, l, mid, ll, v);
    else modify(rs, mid + 1, r, ll, v);
    sum[k] = sum[ls] + sum[rs];
}
il int query(int k, int l, int r, int ll) {
    if(ll == 0) return 0;
    if(l == r) return 1;
    int mid = (l + r) >> 1;
    if(ll > mid) return query(rs, mid + 1, r, ll) + sum[ls];
    return query(ls, l, mid, ll);
}
il int K_th(int k, int l, int r, int b) {
    if(l == r) return l;
    int mid = (l + r) >> 1, pax = sum[ls];
    if(pax >= b) return K_th(ls, l, mid, b);
    return K_th(rs, mid + 1, r, b - pax);
}
signed main() {
    n = read(), now = 1, build(1, 1, n);
    rep(i, 1, n) {
        int r = (read() + now) % (n - i + 1), t;
        if(r == 0) r = n - i + 1;
        printf("%d\n", t = K_th(1, 1, n, now = r)), modify(1, 1, n, t, -1);
    }
    return 0;
}