rt,调废了,写线段树好久没这么崩溃了/kk
请大佬指教/kel
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
struct ST{
int lmax;
int rmax;
}st[N*4];
int q[N];
int tail;
void build(int root,int l,int r){
st[root].lmax=st[root].rmax=r-l+1;
if(l==r)
return;
int mid=(l+r)/2;
build(root*2,l,mid);
build(root*2+1,mid+1,r);
}
void change(int root,int l,int r,int x,int k){
if(l==r){
st[root].lmax=st[root].rmax=k;
return;
}
int mid=(l+r)/2;
if(mid>=x)
change(root*2,l,mid,x,k);
else
change(root*2+1,mid+1,r,x,k);
if(st[root*2].lmax==mid-l+1)
st[root].lmax=st[root*2+1].lmax+mid-l+1;
else
st[root].lmax=st[root*2].lmax;
if(st[root*2+1].rmax==r-mid)
st[root].rmax=st[root*2].rmax+r-mid;
else
st[root].rmax=st[root*2+1].rmax;
}
ST ask(int root,int l,int r,int x,int y){
if(l>=x&&r<=y)
return st[root];
int mid=(l+r)/2;
if(mid>=y)
return ask(root*2,l,mid,x,y);
else{
if(mid+1<=x)
return ask(root*2+1,mid+1,r,x,y);
else{
ST L=ask(root*2,l,mid,x,y);
ST R=ask(root*2+1,mid+1,r,x,y);
ST res;
if(L.lmax==mid-l+1)
res.lmax=R.lmax+mid-l+1;
else
res.lmax=L.lmax;
if(R.rmax==r-mid)
res.rmax=L.rmax+r-mid;
else
res.rmax=R.rmax;
return res;
}
}
}
int main(){
int n,m;
cin>>n>>m;
build(1,1,n);
for(int i=1;i<=m;i++){
char opt;
cin>>opt;
if(opt=='D'){
int x;
cin>>x;
tail++;
q[tail]=x;
change(1,1,n,x,0);
}
if(opt=='R'){
int x=q[tail];
tail--;
change(1,1,n,x,1);
}
if(opt=='Q'){
int x;
cin>>x;
int ans=0;
ST res=ask(1,1,n,1,x);
ans+=res.rmax;
if(x!=n){
res=ask(1,1,n,x+1,n);
ans+=res.lmax;
}
printf("%d\n",ans);
}
}
return 0;
}