题目大意
带插入、修改的区间$k$小值在线查询。（卡块状链表）
题目分析
本题有四种做法（见vfk博客），本人仅介绍其中两种。
我们若能用平衡树维护每个数，那么我们就可以方便的提取区间，再在每个平衡树结点处维护一棵权值线段树，权值线段树维护其子树所有点的权值，这样我们可以方便的统计$k$小。
对于每次的询问，我们需要在平衡树提取出区间，将对应的主席树根结点提取出来并在主席树上进行二分操作（经典操作求$k$小），即可回答询问。
现在考虑如何维护外层平衡树，我们要快速的维护出子树对应的权值线段树，显然Splay不可做，我们无法在旋转的同时更新权值线段树。
考虑不旋转的方法，使用替罪羊树，我们每次暴力重构同时暴力重构内部的权值线段树，即可做到更新内部权值线段树。
注意到替罪羊树重量平衡的性质，时间复杂度$O(n\log^2n)$。
update:关于替罪羊树怎么提取区间的问题。
和线段树差不多，如果已经得到区间就返回，否则递归子树找。区别是要可能算上根节点这一个单点。
代码
注：本代码在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
219
220
221
222
223
224
225
226
227
228
229
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;
struct Tree2 {
int child[2],father;
int size,root;
int v;
Tree2(int l=0,int r=0,int f=0,int s=0,int _v=0,int ro=0):father(f),size(s),root(ro),v(_v) {
child[0]=l;
child[1]=r;
}
};
struct ScapeGoat_Tree {
Tree2 tree[maxn];
int root,size;
bool balance(int index) {
return size(index)*0.75>=max(size(ls(index)),size(rs(index)));
}
bool checkson(int index) {
return rs(fa(index))==index;
}
void push_up(int index) {
size(index)=size(ls(index))+1+size(rs(index));
}
int cnt,a[maxn];
void dfs(int index) {
if(ls(index))dfs(ls(index));
st.remove(root(index));
root(index)=0;
a[++cnt]=index;
if(rs(index))dfs(rs(index));
}
int build(int Left,int Right) {
if(Left>Right)return 0;
int mid=(Left+Right)>>1,pos=a[mid];
ls(pos)=build(Left,mid-1);
rs(pos)=build(mid+1,Right);
fa(ls(pos))=fa(rs(pos))=pos;
push_up(pos);
for(int i=Left; i<=Right; i++)
st.insert(root(pos),v(a[i]),1);
return pos;
}
void rebuild(int index) {
cnt=0;
dfs(index);
int father=fa(index),side=checkson(index);
int pos=build(1,cnt);
if(father)tree[father].child[side]=pos;
fa(pos)=father;
if(index==root)root=pos;
}
void insert(int k,int v) {
int now=root,father=0,side;
while(now) {
father=now;
if(size(ls(now))+1<k) {
k-=size(ls(now))+1;
now=rs(now);
side=1;
} else now=ls(now),side=0;
size(father)++;
st.insert(root(father),v,1);
}
tree[now=++size]=Tree2(0,0,father,1,v);
if(size==1)root=now;
st.insert(root(now),v,1);
if(father)tree[father].child[side]=now;
int pos=0;
for(int i=now; i; i=fa(i))
if(!balance(i))pos=i;
if(pos)rebuild(pos);
}
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);
}
}
} sgt;
int n,a[maxn],q,lastans;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=n; i++)sgt.insert(i,a[i]);
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();
sgt.get(sgt.root,x,y);
lastans=st.query(0,MAX,v);
printf("%d\n",lastans);
} else if(opt=='M') {
int tmp=sgt.change(sgt.root,x,y);
sgt.tree[tmp].v=y;
} else sgt.insert(x,y);
}
return 0;
}
