题意：
有一个长度为n的序列a，一开始所有数为0， q次操作，操作有两种： (C x v)：将a[x]修改为v (Q l r)：问[l,r]中第8大的数
数据范围：n,q<=1e5，0<=a(i)<=1e9
解法：
问题可以离线，因此可以整体二分。
ps： 这题树套树也可以做，但是整体二分省空间
code：
#include<bits/stdc++.h>
using namespace std
;
const int maxm
=2e5+5;
struct QQ
{
int op
,x
,y
,k
,id
;
}Q
[maxm
],lc
[maxm
],rc
[maxm
];
int mark
[maxm
];
int ans
[maxm
];
int c
[maxm
];
int n
,q
;
int lowbit(int i
){
return i
&-i
;
}
void add(int i
,int t
){
while(i
<=n
){
c
[i
]+=t
,i
+=lowbit(i
);
}
}
int ask(int i
){
int ans
=0;
while(i
){
ans
+=c
[i
],i
-=lowbit(i
);
}
return ans
;
}
void solve(int l
,int r
,int ql
,int qr
){
if(ql
>qr
)return ;
if(l
==r
){
for(int i
=ql
;i
<=qr
;i
++){
if(Q
[i
].op
==2)ans
[Q
[i
].id
]=l
;
}
return ;
}
int mid
=(l
+r
)>>1;
int cnt1
=0,cnt2
=0;
for(int i
=ql
;i
<=qr
;i
++){
if(Q
[i
].op
==1){
if(Q
[i
].y
<=mid
)lc
[++cnt1
]=Q
[i
];
else add(Q
[i
].x
,Q
[i
].k
),rc
[++cnt2
]=Q
[i
];
}else if(Q
[i
].op
==2){
int t
=ask(Q
[i
].y
)-ask(Q
[i
].x
-1);
if(t
>=Q
[i
].k
)rc
[++cnt2
]=Q
[i
];
else Q
[i
].k
-=t
,lc
[++cnt1
]=Q
[i
];
}
}
for(int i
=ql
;i
<=qr
;i
++){
if(Q
[i
].op
==1&&Q
[i
].y
>mid
){
add(Q
[i
].x
,-Q
[i
].k
);
}
}
for(int i
=1;i
<=cnt1
;i
++){
Q
[ql
+i
-1]=lc
[i
];
}
for(int i
=1;i
<=cnt2
;i
++){
Q
[ql
+cnt1
+i
-1]=rc
[i
];
}
solve(l
,mid
,ql
,ql
+cnt1
-1);
solve(mid
+1,r
,ql
+cnt1
,qr
);
}
signed main(){
scanf("%d%d",&n
,&q
);
int tot
=0;
int q1
=0;
for(int i
=1;i
<=q
;i
++){
char op
[3];scanf("%s",op
);
int x
,y
;scanf("%d%d",&x
,&y
);
if(op
[0]=='C'){
if(mark
[x
]){
Q
[++tot
]={1,x
,mark
[x
],-1,666};
}
Q
[++tot
]={1,x
,y
,1,666};
mark
[x
]=y
;
}else{
Q
[++tot
]={2,x
,y
,8,++q1
};
}
}
solve(0,1e9,1,tot
);
for(int i
=1;i
<=q1
;i
++){
printf("%d\n",ans
[i
]);
}
return 0;
}
