1 #include <algorithm>  2 #include <iostream>  3 #include <iomanip>  4 #include <cstring>  5 #include <climits>  6 #include <complex>  7 #include <fstream>  8 #include <cassert>  9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19  20 using namespace std; 21 #define fr first 22 #define sc second 23 #define cl clear 24 #define BUG puts("here!!!") 25 #define W(a) while(a--) 26 #define pb(a) push_back(a) 27 #define Rint(a) scanf("%d", &a) 28 #define Rll(a) scanf("%lld", &a) 29 #define Rs(a) scanf("%s", a) 30 #define Cin(a) cin >> a 31 #define FRead() freopen("in", "r", stdin) 32 #define FWrite() freopen("out", "w", stdout) 33 #define Rep(i, len) for(int i = 0; i < (len); i++) 34 #define For(i, a, len) for(int i = (a); i < (len); i++) 35 #define Cls(a) memset((a), 0, sizeof(a)) 36 #define Clr(a, p) memset((a), (p), sizeof(a)) 37 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 38 #define lrt rt << 1 39 #define rrt rt << 1 | 1 40 #define pi 3.14159265359 41 #define RT return 42 #define lowbit(p) p & (-p) 43 #define onenum(p) __builtin_popcount(p) 44 typedef long long LL; 45 typedef long double LD; 46 typedef unsigned long long ULL; 47 typedef pair<int, int> pii; 48 typedef pair<string, int> psi; 49 typedef pair<LL, LL> pll; 50 typedef map<string, int> msi; 51 typedef vector<int> vi; 52 typedef vector<LL> vl; 53 typedef vector<vl> vvl; 54 typedef vector<bool> vb; 55  56 const int maxn = 50500; 57 typedef struct Node { 58     int left, max, right; 59     int l; 60     int r; 61 }Node; 62 Node seg[maxn<<2]; 63 int n, m, p; 64 char q[3]; 65 stack<int> last; 66  67 void build(int l, int r, int rt) { 68     seg[rt].l = l; seg[rt].r = r; 69     seg[rt].left = r - l + 1; 70     seg[rt].right = r - l + 1; 71     seg[rt].max = r - l + 1; 72     if(l == r) return; 73     int mid = (l + r) >> 1; 74     build(l, mid, lrt); 75     build(mid+1, r, rrt); 76 } 77  78 void update(int l, int r, int rt, int v, int p) { 79     if(l == r) { 80         seg[rt].left = v; 81         seg[rt].right = v; 82         seg[rt].max = v; 83         return; 84     } 85     int mid = (l + r) >> 1; 86     if(p <= mid) update(l, mid, lrt, v, p); 87     else update(mid+1, r, rrt, v, p); 88      89     seg[rt].max=max(max(seg[lrt].max,seg[rrt].max),seg[lrt].right+seg[rrt].left); 90     if(seg[lrt].left==(seg[lrt].r-seg[lrt].l+1)) seg[rt].left = seg[lrt].max + seg[rrt].left; 91     else seg[rt].left = seg[lrt].left; 92     if(seg[rrt].right==(seg[rrt].r-seg[rrt].l+1)) seg[rt].right = seg[rrt].max + seg[lrt].right; 93     else seg[rt].right=seg[rrt].right; 94 } 95  96 int query(int l, int r, int rt, int p) { 97     if(seg[rt].max==0||(seg[rt].max==(seg[rt].r-seg[rt].l+1))) 98         return seg[rt].max; 99     if(l == r)100         return seg[rt].max;101     int mid = (l + r) >> 1;102     if(p <= mid) {103         if(p >= seg[lrt].r - seg[lrt].right + 1) return query(l, mid, lrt, p) + query(mid+1, r, rrt, mid+1);104         else return query(l, mid, lrt, p);105     }106     else {107         if(p<=seg[rrt].l+seg[rrt].left-1) return query(mid+1, r, rrt, p) + query(l, mid, lrt, mid);108         else return query(mid+1, r, rrt, p);109     }110 }111 112 int main() {113     // FRead();114     while(~Rint(n) && ~Rint(m)) {115         while(!last.empty()) last.pop();116         build(1, n, 1);117         Rep(i, m) {118             Rs(q);119             if(q[0] == ‘D‘) {120                 Rint(p);121                 last.push(p);122                 update(1, n, 1, 0, p);123             }124             if(q[0] == ‘Q‘) {125                 Rint(p);126                 printf("%d\n", query(1, n, 1, p));127             }128             if(q[0] == ‘R‘) {129                 p = last.top();130                 last.pop();131                 update(1, n, 1, 1, p);132             }133         }134     }135     RT 0;136 }