E

题目链接：https://vjudge.net/contest/332656#problem/E
思路：
稍微改下线段树求连续区间的代码就好了
具体的解释还是看代码注释吧
  1 #include <math.h>
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <string>
  7 #include <string.h>
  8 #include <vector>
  9 #include <map>
 10 #include <stack>
 11 #include <set>
 12 #include <random>
 13 
 14 #define LL long long
 15 #define ls nod<<1
 16 #define rs (nod<<1)+1
 17 const int maxn = 2e5 + 10;
 18 const double eps = 1e-9;
 19 
 20 
 21 LL v[maxn];
 22 struct Node {
 23     int l,r;
 24     int lsum,rsum,sum;
 25 }tree[maxn<<2];
 26 
 27 void build(int l,int r,int nod) {
 28     tree[nod].l = l;
 29     tree[nod].r = r;
 30     tree[nod].lsum = tree[nod].rsum = tree[nod].sum = r-l+1;
 31     if (l == r ) {
 32         return ;
 33     }
 34     int mid = (l + r) >> 1;
 35     build(l,mid,nod<<1);
 36     build(mid+1,r,(nod<<1)+1);
 37 }
 38 
 39 void pushup(int nod) {
 40     int l = tree[nod].l,r = tree[nod].r;
 41     int mid = (l + r ) >> 1;
 42     tree[nod].sum = std::max(std::max(tree[ls].sum,tree[rs].sum),tree[ls].rsum + tree[rs].lsum);
 43     tree[nod].lsum = tree[ls].lsum;
 44     tree[nod].rsum = tree[rs].rsum;
 45     if (mid - l + 1 == tree[ls].lsum)
 46         tree[nod].lsum = tree[ls].sum + tree[rs].lsum;
 47     if (r-mid == tree[rs].rsum)
 48         tree[nod].rsum = tree[rs].sum + tree[ls].rsum;
 49 }
 50 
 51 
 52 void modify(int x,int z,int nod=1) {
 53     int l = tree[nod].l,r = tree[nod].r;
 54     if (l == r) {
 55         tree[nod].sum = tree[nod].lsum = tree[nod].rsum = z;
 56         return ;
 57     }
 58     int mid = (l + r) >> 1;
 59     if (x <= mid) {
 60         modify(x,z,nod<<1);
 61     }
 62     if (x > mid) {
 63         modify(x,z,(nod<<1)+1);
 64     }
 65     pushup(nod);
 66 }
 67 
 68 LL query(int x,int nod=1) {
 69     int l = tree[nod].l,r = tree[nod].r;
 70     if(l == r)
 71         return tree[nod].sum;
 72     int mid = (l + r) >> 1;
 73     if (x <= mid) {
 74         if (x >= tree[ls].r - tree[ls].rsum + 1) {
 75             return tree[ls].rsum + tree[rs].lsum;
 76         }
 77         else {
 78             return query(x,ls);
 79         }
 80     }
 81     else {
 82         if (x <= tree[rs].lsum + tree[rs].l - 1) {
 83             return tree[ls].rsum + tree[rs].lsum;
 84         }
 85         else
 86             return query(x,rs);
 87     }
 88 }
 89 
 90 int main() {
 91     int n,m,x;
 92     char s[2];
 93     while (~scanf("%d%d",&n,&m)) {
 94         std::stack<int> sta;
 95         build(1,n,1);
 96         while (m--) {
 97             scanf("%s",s);
 98             if (s[0] == 'D') {
 99                 scanf("%d",&x);
100                 modify(x,0);
101                 sta.push(x);
102             }
103             else if (s[0] == 'R') {
104                 x = sta.top();
105                 sta.pop();
106                 if (x > 0)
107                     modify(x,1);
108             }
109             else {
110                 scanf("%d",&x);
111                 printf("%lld
",query(x));
112             }
113         }
114     }
115     return 0;
116 }