1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6 int ql,qr,x,n,ll[150005],rl[150005],a[150005];  7 stack
         
          s;  8 void build(int o,int l,int r)  9 { 10     int mid=l+(r-l)/2; 11     ll[o]=rl[o]=r-l+1; 12     if (l!=r) 13     { 14         build(o*2,l,mid); 15         build(o*2+1,mid+1,r); 16     } 17 } 18 int lquery(int o,int l,int r) 19 { 20     int mid=l+(r-l)/2; 21     if (ql==l) return ll[o]; 22     else if (qr<=mid) return lquery(o*2,l,mid); 23     else if (ql>mid) return lquery(o*2+1,mid+1,r); 24     else{ 25         int temp=lquery(o*2,l,mid); 26         if (temp==mid-ql+1) temp+=ll[o*2+1]; 27         return temp; 28     } 29 } 30 int rquery(int o,int l,int r) 31 { 32     int mid=l+(r-l)/2; 33     if (qr==r) return rl[o]; 34     else if (qr<=mid) return rquery(o*2,l,mid); 35     else if (ql>mid) return rquery(o*2+1,mid+1,r); 36     else{ 37         int temp=rquery(o*2+1,mid+1,r); 38         if (temp==qr-mid) temp+=rl[o*2]; 39         return temp; 40     } 41 } 42 void rupdate(int o,int l,int r) 43 { 44     int mid=l+(r-l)/2; 45     if (l==r) rl[o]=ll[o]=1; 46     else{ 47         if (x<=mid) rupdate(o*2,l,mid); 48         else rupdate(o*2+1,mid+1,r); 49         if (ll[o]==x-l) 50         { 51             ql=x+1; qr=r; ll[o]+=1; 52             if (ql<=qr) ll[o]+=lquery(1,1,n); 53         } 54         if (rl[o]==r-x) 55         { 56             ql=l; qr=x-1; rl[o]+=1; 57             if (ql<=qr) rl[o]+=rquery(1,1,n); 58         } 59     } 60 } 61 void dupdate(int o,int l,int r) 62 { 63     int mid=l+(r-l)/2; 64     if (l==r) rl[o]=ll[o]=0; 65     else{ 66         if (x<=mid) dupdate(o*2,l,mid); 67         else dupdate(o*2+1,mid+1,r); 68         if (ll[o]>x-l) ll[o]=x-l; 69         if (rl[o]>r-x) rl[o]=r-x; 70     } 71 } 72 int main() 73 { 74     int m,i,flong,temp; 75     char c; 76     while (~scanf("%d%d",&n,&m)) 77     { 78         while (!s.empty()) s.pop(); 79         build(1,1,n); 80         for (i=1;i<=n;i++) a[i]=1; 81         for (i=1;i<=m;i++) 82         { 83             getchar(); scanf("%c",&c); 84             if (c=='Q') 85             { 86                 scanf("%d",&x); 87                 if (a[x]==0) printf("0\n"); 88                 else{ 89                     flong=0; ql=1; qr=x-1; 90                     if (qr>=ql) flong=rquery(1,1,n); 91                     temp=1+flong; 92                     flong=0; ql=x+1; qr=n; 93                     if (qr>=ql) flong=lquery(1,1,n); 94                     printf("%d\n",temp+flong); 95                 } 96             } 97             else if (c=='R') 98             { 99                 x=s.top(); s.pop();100                 a[x]=1; rupdate(1,1,n);101             }102             else if (c=='D')103             {104                 scanf("%d",&x);105                 a[x]=0; s.push(x); dupdate(1,1,n);106             }107         }108     }109 }