P3988 [SHOI2013] 发牌

Solution

容易发现，答案就是维护当前序列的第 k 大值，而且只有删除，这个时候就可以使用权值线段树来维护。这颗树的每一个叶子表示一张牌，然后线段树记录改节点为根的子树的节点个数，接着进行查询即可，代码见下：

Code

#include <bits/stdc++.h>
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define IOS ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef long long ll;
struct SGT
{vector<int> tree;SGT(){}SGT(int n){tree.resize(n << 2);build(1, 1, n);}void build(int u, int l, int r){if(l == r){tree[u] = 1;return;}int mid = l + r >> 1;build(ls(u), l, mid), build(rs(u), mid + 1, r);pushup(u);return;}void pushup(int u){tree[u] = tree[ls(u)] + tree[rs(u)];return;}int query(int q, int u, int l, int r){tree[u] --;if(l == r) return l;int mid = l + r >> 1;if(q <= tree[ls(u)]) return query(q, ls(u), l, mid);else return query(q - tree[ls(u)], rs(u), mid + 1, r);}
};
int n, tmp, now;
int main() 
{IOS;cin >> n;SGT sgtree(n);for(int i = 1; i <= n; i ++){cin >> tmp;now = (now + tmp) % (n - i + 1);cout << sgtree.query(now + 1, 1, 1, n) << "\n";}return 0;
}