题解
- 动态区间第k小,我的做法是树状数组套线段树,空间开小了,RE无数次,看了大佬们的题解,建点方式不太一样大佬们的建点方式空间效率常数比我小。。。
- 数太大了,所以离散化,但是修改的值可能并没有出现过所以必须离线做…
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
using namespace std;
const int N=1e4+7;
int tr[N*800],lson[N*800],rson[N*800],root[N],L[30],R[30];
int a[N],b[N<<2],s[N][3],llen,rlen,len,cnt,n,m;
inline void update(int &o,int l,int r,int x,int v){
if(!o)o=++cnt;
tr[o]+=v;
if(l==r)return ;
int mid=l+r>>1;
if(x<=mid)update(lson[o],l,mid,x,v);
else update(rson[o],mid+1,r,x,v);
}
inline void UPDATE(int x,int v){
int k=lower_bound(b+1,b+len+1,a[x])-b;
for(;x<=n;x+=lowbit(x))update(root[x],1,len,k,v);
}
inline int query(int l,int r,int k){
if(l==r)return l;
int sum=0,mid=l+r>>1;
rep(i,1,rlen)sum+=tr[lson[R[i]]];
rep(i,1,llen)sum-=tr[lson[L[i]]];
if(k<=sum){
rep(i,1,rlen)R[i]=lson[R[i]];
rep(i,1,llen)L[i]=lson[L[i]];
return query(l,mid,k);
}
rep(i,1,rlen)R[i]=rson[R[i]];
rep(i,1,llen)L[i]=rson[L[i]];
return query(mid+1,r,k-sum);
}
inline int QUERY(int l,int r,int k){
llen=rlen=0;
for(register int i=l-1;i;i-=lowbit(i))L[++llen]=root[i];
for(register int i=r;i;i-=lowbit(i))R[++rlen]=root[i];
return query(1,len,k);
}
int main(){
scanf("%d%d",&n,&m);
rep(i,1,n){scanf("%d",&a[i]);b[i]=a[i];}len=n;
rep(i,1,m){
char op;while(isspace(op=getchar()));
scanf("%d%d",&s[i][0],&s[i][1]);
if(op=='Q')scanf("%d",&s[i][2]);
else {b[++len]=s[i][1];s[i][2]=-1;}
}
sort(b+1,b+len+1);
len=unique(b+1,b+len+1)-b-1;
rep(i,1,n)UPDATE(i,1);
rep(i,1,m){
if(s[i][2]==-1){UPDATE(s[i][0],-1);a[s[i][0]]=s[i][1];UPDATE(s[i][0],1);}
else printf("%d\n",b[QUERY(s[i][0],s[i][1],s[i][2])]);
}
return 0;
}