题目大意:
- 给一个序列 n
- 会有n次操作, 每次都会 删除 一个数
- 这个数 是 连续子序列里面 最大的逆序对的个数 ^ Q[i], q[i] 给出
思路 :
- 启发式 拆分, 每次选择长度小的序列来 进行处理
- 数学化: rev(逆序对个数) rev(x + 1, r) = rev(l, r) - rev(l, x - 1) - (一个元素在 [l, x - 1]，另一个元素在 [x + 1, r] 的逆序对数) - (其中一个元素是 a_x 的逆序对数) ,依次内推
- 值域主席树 可以解决 逆序对个数问题, 枚举每一个数, 看他比那些数大即可
- 因此 值域线段树去 解决 数学化
- 然后 利用 mp 模拟 区间的逆序对的值, 利用 multiset 解决当前最大的逆序对的数量
#include <bits/stdc++.h> #define MAXN ((int) 1e5) #define MAXP 20 using namespace std; int n, A[MAXN + 10]; int tot, sumo[MAXN * MAXP + 10], ch[MAXN * MAXP + 10][2], root[MAXN + 10]; // map key 都是已删除的位置 // mp[i]：以 A[i + 1] 为开头的段的逆序对数 map<int, long long> mp; // 保存所有段的逆序对数 multiset<long long> ms; // 新建线段树节点 int newNode() { tot++; sumo[tot] = 0; ch[tot][0] = ch[tot][1] = 0; return tot; } // 添加一个整数 pos void add(int id, int l, int r, int old, int pos) { sumo[id] = sumo[old]; ch[id][0] = ch[old][0]; ch[id][1] = ch[old][1]; if (l == r) sumo[id]++; else { int mid = (l + r) >> 1; if (pos <= mid) add(ch[id][0] = newNode(), l, mid, ch[old][0], pos); else add(ch[id][1] = newNode(), mid + 1, r, ch[old][1], pos); sumo[id] = sumo[ch[id][0]] + sumo[ch[id][1]]; } } // 询问整数 ql 到 qr 一共有几个 int query(int id, int l, int r, int ql, int qr) { if (ql > qr) return 0; if (ql <= l && r <= qr) return sumo[id]; int mid = (l + r) >> 1; return (ql <= mid ? query(ch[id][0], l, mid, ql, qr) : 0) + (qr > mid ? query(ch[id][1], mid + 1, r, ql, qr) : 0); } // 启发式分裂，将区间 [L + 1, R - 1] 从 X 处分裂 void split(int L, int R, int X) { long long old = mp[L]; ms.erase(ms.find(old)); // base：一个元素是 A[X] 的逆序对数 long long base = query(root[R - 1], 1, n, 1, A[X] - 1) - query(root[X], 1, n, 1, A[X] - 1); base += query(root[X - 1], 1, n, A[X] + 1, n) - query(root[L], 1, n, A[X] + 1, n); if (X - L < R - X) { // 左半边更短，枚举左半边 // a：[L + 1, X - 1] 的逆序对数 // b：base + 一个元素在 [L + 1, X - 1]，另一个元素在 [X + 1, R - 1] 的逆序对数 long long a = 0, b = base; for (int i = L + 1; i < X; i++) { a += query(root[i - 1], 1, n, A[i] + 1, n) - query(root[L], 1, n, A[i] + 1, n); b += query(root[R - 1], 1, n, 1, A[i] - 1) - query(root[X], 1, n, 1, A[i] - 1); } mp[L] = a; ms.insert(mp[L]); mp[X] = old - a - b; ms.insert(mp[X]); } else { // 右半边更短，枚举右半边 // a：[X + 1, R - 1] 的逆序对数 // b：base + 一个元素在 [L + 1, X - 1]，另一个元素在 [X + 1, R - 1] 的逆序对数 long long a = 0, b = base; for (int i = X + 1; i < R; i++) { a += query(root[i - 1], 1, n, A[i] + 1, n) - query(root[X], 1, n, A[i] + 1, n); b += query(root[X - 1], 1, n, A[i] + 1, n) - query(root[L], 1, n, A[i] + 1, n); } mp[L] = old - a - b; ms.insert(mp[L]); mp[X] = a; ms.insert(mp[X]); } } void solve() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &A[i]); // 将 A[1] 到 A[n] 依次加入主席树 // root[i] 就是加入 A[i] 之后的情况 tot = 0; for (int i = 1; i <= n; i++) add(root[i] = newNode(), 1, n, root[i - 1], A[i]); // 计算整个序列的逆序对数 long long tmp = 0; for (int i = 1; i <= n; i++) tmp += query(root[i - 1], 1, n, A[i] + 1, n); // 把下标 0 和 n + 1 视为已删除的下标，方便处理 mp.clear(); ms.clear(); mp[0] = tmp; ms.insert(tmp); mp[n + 1] = 0; ms.insert(0); long long ans = *prev(ms.end()); for (int i = 1; i <= n; i++) { printf("%lld%c", ans, "\n "[i < n]); long long x; scanf("%lld", &x); x ^= ans; auto it = prev(mp.lower_bound(x)); split(it->first, next(it)->first, x); ans = *prev(ms.end()); } } int main() { int tcase; scanf("%d", &tcase); while (tcase--) solve(); return 0; }