题解 P2617 【Dynamic Rankings】
Ireliaღ
2019-10-31 13:25:55
**看下面都是树状数组+主席树,我来一个树状数组+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;
}
```