题目大意
带插入、修改的区间$k$小值在线查询。（卡块状链表）
题目分析
接着上篇替罪羊树的分析，发现除了不旋转的替罪羊树可以使用，treap也可以使用。
考虑旋转的时候如何维护信息，因为treap是重量平衡的，故我们可以暴力递归子树，具体方法如图：
我们发现$son$的权值线段树就是原来$x$的权值线段树，因此我们将$son$的权值线段树清空并从$x$拷贝过来，再将$x$的权值线段树重构。
怎么重构呢？我们可以暴力合并其左右儿子的线段树。
因为treap重量平衡，故时间复杂度为$O(n\log n\log n\log \log n)=O(n\log^2n)$。
treap的区间提取和其他的维护和替罪羊树类似。
代码
注：本代码在bzoj会CE，请自行修改。
注2：本代码不CE后会RE，本地数据没问题，若有读者找到错误请联系我谢谢。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=70005;
struct node {
bool bj; //点/树
int x;
node(bool _bj=0,int _x=0):bj(_bj),x(_x) {}
};
struct Tree1 {
int l,r,size;
void clear() {
l=r=size=0;
}
};
vector<node>Root;
struct Segment_Tree {
Tree1 tree[maxn*500];
int size;
queue<int>Q; //garbage collection
int newnode() {
if(Q.empty())return ++size;
int New=Q.front();
Q.pop();
tree[New].clear();
return New;
}
void insert(int Left,int Right,int& now,int v,int delta) {
if(!now)now=newnode();
tree[now].size+=delta;
if(Left==Right)return;
int mid=(Left+Right)>>1;
if(v<=mid)insert(Left,mid,tree[now].l,v,delta);
else insert(mid+1,Right,tree[now].r,v,delta);
}
void insert(int& root,int v,int delta) {
insert(0,MAX,root,v,delta);
}
void remove(int now) {
if(!now)return;
Q.push(now);
remove(tree[now].l);
remove(tree[now].r);
}
int merge(int x,int y) {
if(!x&&!y)return 0;
int now=newnode();
tree[now].l=merge(tree[x].l,tree[y].l);
tree[now].r=merge(tree[x].r,tree[y].r);
tree[now].size=tree[x].size+tree[y].size;
return now;
}
int query(int Left,int Right,int rank) {
if(Left==Right)return Left;
int sum=0,mid=(Left+Right)>>1;
for(auto root:Root) {
if(root.bj)sum+=tree[tree[root.x].l].size;
else sum+=(root.x>=Left&&root.x<=mid);
}
if(rank<=sum) {
for(auto& root:Root)
if(root.bj)root.x=tree[root.x].l;
return query(Left,mid,rank);
} else {
for(auto& root:Root)
if(root.bj)root.x=tree[root.x].r;
return query(mid+1,Right,rank-sum);
}
}
} st;
mt19937 g(rand());
struct Tree2 {
int child[2];
int d,v;
int root,size;
};
struct Treap {
Tree2 tree[maxn];
int size,root;
void push_up_merge(int index) {
int ls=ls(index),rs=rs(index);
size(index)=size(ls)+size(rs)+1;
root(index)=st.merge(root(ls),root(rs));
st.insert(root(index),v(index),1);
}
void push_up(int index) {
int ls=ls(index),rs=rs(index);
size(index)=size(ls)+size(rs)+1;
}
int newnode(int v) {
int now=++size;
v(now)=v;
d(now)=g()%maxn;
size(now)=1;
return now;
}
int build(int Left,int Right,int* a) {
if(Left>Right)return 0;
int mid=(Left+Right)>>1,now=newnode(a[mid]);
ls(now)=build(Left,mid-1,a);
rs(now)=build(mid+1,Right,a);
push_up_merge(now);
return now;
}
int rotate(int& index,bool side) {
int son=tree[index].child[side^1];
tree[index].child[side^1]=tree[son].child[side];
tree[son].child[side]=index;
st.remove(tree[son].root);
tree[son].root=tree[index].root;
push_up_merge(index);
push_up(son);
index=son;
}
void insert(int& index,int pos,int val) {
if(!index) {
index=newnode(val);
st.insert(tree[index].root,val,1);
return;
}
bool side=pos>(size(ls(index))+1);
if(side)insert(rs(index),pos-size(ls(index))-1,val);
else insert(ls(index),pos,val);
size(index)++;
st.insert(tree[index].root,val,1);
if(d(index)<d(tree[index].child[side]))rotate(index,side^1);
}
int change(int index,int pos,int v) {
if(size(ls(index))+1==pos) {
st.insert(root(index),v(index),-1);
st.insert(root(index),v,1);
return index;
}
int tmp;
if(size(ls(index))>=pos)tmp=change(ls(index),pos,v);
else tmp=change(rs(index),pos-size(ls(index))-1,v);
st.insert(root(index),v(tmp),-1);
st.insert(root(index),v,1);
return tmp;
}
void get(int index,int Left,int Right) {
int l=size(ls(index)),r=size(index);
if(Left==1&&Right==r) {
Root.push_back(node(1,root(index)));
return;
}
if(Left<=l+1&&Right>=l+1)Root.push_back(node(0,v(index)));
if(Right<=l)get(ls(index),Left,Right);
else if(Left>l+1)get(rs(index),Left-l-1,Right-l-1);
else {
if(Left<=l)get(ls(index),Left,l);
if(Right>l+1)get(rs(index),1,Right-l-1);
}
}
} treap;
int n,a[maxn],q,lastans;
int main() {
srand(time(NULL));
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
treap.root=treap.build(1,n,a);
q=Get_Int();
for(int i=1; i<=q; i++) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
int x=Get_Int()^lastans,y=Get_Int()^lastans;
if(opt=='Q') {
int v=Get_Int()^lastans;
Root.clear();
treap.get(treap.root,x,y);
lastans=st.query(0,MAX,v);
printf("%d\n",lastans);
} else if(opt=='M') {
int tmp=treap.change(treap.root,x,y);
treap.tree[tmp].v=y;
} else treap.insert(treap.root,x,y);
}
return 0;
}
