小风的冒险者任务调度 tag 数据结构（树状数组，线段树），模拟 题意简述 对于一个长度为 $n$ 的自然排列，执行 $m$ 次操作，每次操作可以选择一个数，将他移动到排列的最前方。求每个数在排列中出现过的最靠前位置和最靠后位置。 fun fact 赛时看到这题，第一时间想到了平衡树，然后打了一个无旋treap，但是发现treap只能按排名分裂，而本题是找到数本身再操作，然后又想了好久的如何维护排名，最后想到了树状数组维护排名，然后就打了一个树状数组维护每个数的排名+无旋treap维护每个数的最前和最后位置。把题打完之后，突然意识到，树状数组维护排名，答案不就可以直接统计了吗？直接更新就行，为什么要用treap呢？QAQ 题解思路 首先，需要注意到一点：每个数的最小排名只会有两种情况：1或者它本身，对于每次操作，如果对象是这个数，那么它的最小排名就会变成 $1$ ，否则他的排名一定不会变得更优。所以，最小排名只需要看他是否被操作过就行，没操作就是它本身，操作过就是 $1$。难点在于如何维护最大排名。我们思考排名的本质：有多少个数的位置在他的前面。也就是我们可以用权值树状数组维护每个数的位置，一个数的排名就是 $pos_i$ 的前缀和。 然后再来考虑处理操作，想到权值树状数组维护维护位置，每次操作本质上是把一个数的位置移动到所有数的前面，我们可以在权值树状数组的前面预留出 $m$ 个位置，每次操作就把数的权值移动到前面的位置，然后更新答案即可。 参考代码 ```cpp vector<pii> ans(N + 1); int bit[N * 2]; void add(int pos, int x) { for(; pos < N * 2; pos += (pos & -pos)) bit[pos] += x; } int query(int pos) { int res = 0; for(; pos; pos -= (pos & -pos)) res += bit[pos]; return res; } signed main() { IOS; int n, m; cin >> n >> m; vector<int> pos(n + m + 1); for(int i = 1; i <= n; i ++) { // 预留出前面 m 个位置，所有数往后偏移 m pos[i] = m + i; add(pos[i], 1); ans[i].first = ans[i].second = i; } // 倒着放前面预留的位置 for(int i = m; i >= 1; i --) { int p; cin >> p; ans[p].first = 1; int rk = query(pos[p]); // 一个数被提前，他原来的排名可能会成为最大排名，更新答案 ans[p].second = max(ans[p].second, rk); add(pos[p], -1); pos[p] = i; add(pos[p], 1); } for(int i = 1; i <= n; i ++) { // 最后所有数确定好之后再更新一次答案 ans[i].second = max(ans[i].second, query(pos[i])); cout << ans[i].first << ' ' << ans[i].second << '\n'; } } ``` 赛时写的抽象东西（逃） ps：不要这样做QAQ ```cpp vector<pii> ans(N + 1); struct fhq_treap { struct node { int l, r; int size; unsigned key; int val; int min, max; int tag; node() {tag = val = size = key = l = r = 0;} node(int val, int size,int key) : val(val), size(size), key(key), min(val), max(val) {tag = l = r = 0;} }; vector<node> tr; random_device rd; mt19937 rng; int root; fhq_treap() { root = 0; tr.resize(1); rng = mt19937(rd()); } int create(int v) { int u = tr.size(); tr.push_back(node(v, 1, rng())); return u; } void pushup(int u) { tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1; tr[u].max = max(tr[u].max, tr[u].val); } void pushdown(int u) { if (tr[u].tag) { tr[tr[u].l].val += tr[u].tag; tr[tr[u].l].tag += tr[u].tag; tr[tr[u].r].val += tr[u].tag; tr[tr[u].r].tag += tr[u].tag; tr[u].tag = 0; } } void split_by_val(int u, int val, int &x, int &y) { if (!u) { x = y = 0; return; } if (tr[u].val <= val) { x = u; split_by_val(tr[x].r, val, tr[u].r, y); } else { y = u; split_by_val(tr[u].l, val, x, tr[u].l); } pushup(u); } void split_by_rank(int u, int rank, int &x, int &y) { if (!u) { x = y = 0; return; } pushdown(u); if (rank > tr[tr[u].l].size) { rank -= tr[tr[u].l].size + 1; x = u; split_by_rank(tr[u].r, rank, tr[u].r, y); } else { y = u; split_by_rank(tr[u].l, rank, x, tr[u].l); } pushup(u); } int merge(int x, int y) { if (!x || !y) return x + y; if (tr[x].key < tr[y].key) { pushdown(x); tr[x].r = merge(tr[x].r, y); pushup(x); return x; } else { pushdown(y); tr[y].l = merge(x, tr[y].l); pushup(y); return y; } } void insert(int val) { int z = create(val); int x, y; split_by_val(root, val, x, y); root = merge(merge(x, z), y); } void del(int val) { int x, y, z; split_by_val(root, val, x, z); split_by_val(x, val - 1, x, y); y = merge(tr[y].l, tr[y].r); root = merge(merge(x, y), z); } int get_rank(int u, int k) // 获取排名为k的树 { if (k <= tr[tr[u].l].size) return get_rank(tr[u].l, k); else if (k == tr[tr[u].l].size + 1) return tr[u].val; else return get_rank(tr[u].r, k - tr[tr[u].l].size - 1); } int rank(int val) // 获取val的排名 { int x, y; split_by_val(root, val - 1, x, y); int res = tr[x].size + 1; merge(x, y); return res; } int pre(int val) { int x, y; split_by_val(root, val - 1, x, y); int res = get_rank(x, tr[x].size); root = merge(x, y); return res; } int suc(int val) { int x, y; split_by_val(root, val, x, y); int res = get_rank(y, 1); root = merge(x, y); return res; } node &operator[](int idx) { return tr[idx]; } void inorder(int u) { pushdown(u); if(tr[u].l != 0) inorder(tr[u].l); if(tr[u].r != 0) inorder(tr[u].r); pushup(u); ans[u] = {tr[u].min, tr[u].max}; } }; int bit[N * 2]; void add(int pos, int x) { for(; pos < N * 2; pos += (pos & -pos)) bit[pos] += x; } int query(int pos) { int res = 0; for(; pos; pos -= (pos & -pos)) res += bit[pos]; return res; } signed main() { IOS; int n, k; cin >> n >> k; fhq_treap fhq; vector<int> pos(n + k + 1); for(int i = 1; i <= n; i ++) fhq.insert(i), pos[i] = n - i + 1, add(pos[i], 1); for(int i = 1; i <= k; i ++) { int p; cin >> p; int rk = query(n + k + 1) - query(pos[p] - 1); add(pos[p], -1); pos[p] = n + i; add(pos[p], 1); int x = 0, y = 0, z = 0; fhq.split_by_rank(fhq.root, rk, x, y); fhq.split_by_rank(x, rk - 1, x, z); fhq[x].val += 1; fhq[x].tag += 1; fhq[z].val = fhq[z].min = 1; fhq.root = fhq.merge(z, fhq.merge(x, y)); } fhq.inorder(fhq.root); for(int i = 1; i <= n; i ++) { cout << ans[i].first << ' ' << ans[i].second << '\n'; } } ```