题解 P3988 【[SHOI2013]发牌】

这道题去年联赛就在写此题，省选前尝试用平衡树，都无果，现在重拾此题 不难发现排的相对顺序不会发生改变，而且每一个$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; } ```