题解 P2617 【Dynamic Rankings】

Ireliaღ

2019-10-31 13:25:55

Solution

**看下面都是树状数组+主席树,我来一个树状数组+01Trie** ## 为什么用01Trie(可以不看) 显然,我们需要用一个区间树套一个值域树来做到$\Theta(\log ^ 2(n))$操作。而这个值域树只需要满足**可减性**即可,也就是说,用两个前缀值域树相同地位的节点的`size`相减,得到的就是这段区间的“值域树”的该节点`size` 所以,由于平衡树每次操作形态改变较大,我们不能使用,只能用值域线段树和01Trie来代替。01Trie的编码难度更加简单,并且可以实现最大异或和等其他操作,所以本人更加推荐 ## 实现方法 既然是动态操作,那么修改时我们将树状数组上对应的$\log$个树全部删除原数并加入新数,查询时用$R$在树状数组上对应的$\log$个树的节点的`size`和减去$L - 1$在树状数组上对应的$\log$个树的节点的`size`和,得到的就是这个区间的信息,和要求的$kth$比较,全部进入左/右子树即可 ## 程序实现 需要吸氧 ```cpp #include <iostream> #include <cstdio> using namespace std; const int MAXN = 2e5 + 5; struct Node{ int siz; Node *ch[2]; Node() {} }npool[50000000]; int n, m; int a[MAXN]; int ncnt; Node *rt[MAXN]; Node *cur1[MAXN], *cur2[MAXN]; int tot1, tot2; int LB(int x) {return x & -x;} void Insert(Node *&now, int bit, int k) { if (!now) now = &npool[ncnt++]; now->siz++; if (bit == 0) return; int f = (k & (1 << (bit - 1))) ? 1 : 0; Insert(now->ch[f], bit - 1, k); } void Remove(Node *now, int bit, int k) { if (!now) return; now->siz--; if (bit == 0) return; int f = (k & (1 << (bit - 1))) ? 1 : 0; Remove(now->ch[f], bit - 1, k); } int Query(int k, int bit, int res) { if (bit == 0) return res; int ls = 0; for (int i = 1; i <= tot1; i++) ls -= ((cur1[i] && cur1[i]->ch[0]) ? cur1[i]->ch[0]->siz : 0); for (int i = 1; i <= tot2; i++) ls += ((cur2[i] && cur2[i]->ch[0]) ? cur2[i]->ch[0]->siz : 0); if (k <= ls) { for (int i = 1; i <= tot1; i++) { if (cur1[i]) cur1[i] = cur1[i]->ch[0]; } for (int i = 1; i <= tot2; i++) { if (cur2[i]) cur2[i] = cur2[i]->ch[0]; } return Query(k, bit - 1, res); } else { for (int i = 1; i <= tot1; i++) { if (cur1[i]) cur1[i] = cur1[i]->ch[1]; } for (int i = 1; i <= tot2; i++) { if (cur2[i]) cur2[i] = cur2[i]->ch[1]; } res |= (1 << (bit - 1)); k -= ls; return Query(k, bit - 1, res); } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; for (int j = i; j <= n; j += LB(j)) Insert(rt[j], 30, a[i]); } char op[2]; int x, y, z, res; for (int i = 1; i <= m; i++) { cin >> op; if (op[0] == 'Q') { cin >> x >> y >> z; tot1 = 0; for (int j = x - 1; j >= 1; j -= LB(j)) cur1[++tot1] = rt[j]; tot2 = 0; for (int j = y; j >= 1; j -= LB(j)) cur2[++tot2] = rt[j]; res = Query(z, 30, 0); cout << res << "\n"; } else { cin >> x >> y; for (int j = x; j <= n; j += LB(j)) Remove(rt[j], 30, a[x]); a[x] = y; for (int j = x; j <= n; j += LB(j)) Insert(rt[j], 30, a[x]); } } return 0; } ```