Tunnel Warfare HDU - 1540 线段树之连通区间查询（巧用最大值，最小值）

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <string>
  9 #include <cstring>
 10 #include <map>
 11 #include <stack>
 12 #include <set>
 13 #include <sstream>
 14 #include <iostream>
 15 #define mod 998244353
 16 #define eps 1e-6
 17 #define ll long long
 18 #define INF 0x3f3f3f3f
 19 using namespace std;
 20 
 21 const int maxn=500000;
 22 int m,n;
 23 struct node
 24 {
 25     //l表示左边，r表示右边
 26     int li,ri;
 27     int mi,ma;
 28 };
 29 node no[maxn];
 30 //初始化,k表示当前节点的编号，l表示当前区间的左边界，
 31 void build(int k,int l,int r)
 32 {
 33     no[k].li=l;
 34     no[k].ri=r;
 35     //如果递归到最低点
 36     if(l==r)
 37     {
 38         no[k].mi=m+1;
 39         no[k].ma=0;
 40         return ;
 41     }
 42     //对半分
 43     int mid=(l+r)/2;
 44     //递归到左线段
 45     build(k*2,l,mid);
 46     //递归到右线段
 47     build(k*2+1,mid+1,r);
 48     //更新当前节点的值
 49     no[k].mi=min(no[k*2].mi,no[k*2+1].mi);
 50     no[k].ma=max(no[k*2].ma,no[k*2+1].ma);
 51 }
 52 
 53 //单点修改,指定坐标x的值修改为y
 54 void singlemodify(int k,int x,int y)
 55 {
 56     if(no[k].li==no[k].ri)
 57     {
 58         no[k].mi=y;
 59         no[k].ma=y;
 60         return ;
 61     }
 62     int mid = (no[k].li+no[k].ri)/2;
 63     if(x<=mid)
 64     {
 65         singlemodify(k*2,x,y);
 66     }
 67     else
 68     {
 69         singlemodify(k*2+1,x,y);
 70     }
 71     //维护线段树
 72     no[k].mi=min(no[k*2].mi,no[k*2+1].mi);
 73     no[k].ma=max(no[k*2].ma,no[k*2+1].ma);
 74 }
 75 //恢复指定坐标的值,
 76 void recovery(int k,int x)
 77 {
 78     if(no[k].li==no[k].ri)
 79     {
 80         no[k].mi=m+1;
 81         no[k].ma=0;
 82         return ;
 83     }
 84     int mid = (no[k].li+no[k].ri)/2;
 85     if(x<=mid)
 86     {
 87         recovery(k*2,x);
 88     }
 89     else
 90     {
 91         recovery(k*2+1,x);
 92     }
 93     //维护线段树
 94     no[k].mi=min(no[k*2].mi,no[k*2+1].mi);
 95     no[k].ma=max(no[k*2].ma,no[k*2+1].ma);
 96 }
 97 
 98 //区间最值,flag为1时表示最小，为0时表示最大
 99 int querymaxin(int k,int l,int r,int flag)
100 {
101     //到对应层时返回值
102     if(no[k].li==l&&no[k].ri==r)
103     {
104         if(flag==1)
105         {
106             return no[k].mi;
107         }
108         else
109         {
110             return no[k].ma;
111         }
112     }
113     //取中值
114     int mid=(no[k].li+no[k].ri)/2;
115     if(r<=mid)
116     {
117         return querymaxin(k*2,l,r,flag);
118     }
119     else if(l>mid)
120     {
121         return querymaxin(k*2+1,l,r,flag);
122     }
123     else
124     {
125         if(flag==1)
126         {
127             return min(querymaxin(k*2,l,mid,flag),querymaxin(k*2+1,mid+1,r,flag));
128         }
129         else
130         {
131             return max(querymaxin(k*2,l,mid,flag),querymaxin(k*2+1,mid+1,r,flag));
132         }
133 
134     }
135 }
136 
137 int main()
138 {
139     while(scanf("%d %d",&m,&n)!=EOF)
140     {
141         build(1,1,m);
142         //记录毁掉的村庄的编号
143         int history[50000];
144         int ans=0;
145         while(n--)
146         {
147             char ch[2];
148             int s;
149             cin>>ch;
150             if(ch[0]==‘D‘)
151             {
152                 scanf("%d",&history[ans]);
153                 singlemodify(1,history[ans],history[ans]);
154                 ans++;
155             }
156             else if(ch[0]==‘Q‘)
157             {
158                 cin>>s;
159                 int mi = querymaxin(1,s,m,1);
160                 int ma = querymaxin(1,1,s,0);
161                 if(mi==ma)
162                 {
163                     printf("0\n");
164                 }
165                 else
166                 {
167                     //记得要减一
168                     printf("%d\n",mi-ma-1);
169                 }
170             }
171             else if(ch[0]==‘R‘)
172             {
173                 ans--;
174                 recovery(1,history[ans]);
175             }
176         }
177     }
178 }