题意：在抗日战争期间，地道战在华北平原得到广泛的实施，一般而言，村庄通过一些隧道在一条线上连接，除了两端剩下的每个村庄都有两个相连。
侵略者会频繁的对这些村庄进行扫荡，并且摧他们的地道，当然八路军会把这一些已经被摧毁的村庄修复的，会优先修复最近被破坏的村庄。
分析：被这道题折磨了一上午啊，不过也学到了很多，尤其是这种涉及左右区间的。
*********************************************************************
#include<stdio.h>
#include<algorithm>
#include<stack>
using namespace std; const int maxn = ; struct node
{//sum代表区间种最大的连续区间，lsum代表左端能到达的最右端的个数
int L, R, sum, lsum, rsum;
int Mid(){return (L+R)/;}
int Len(){return (R-L+);}
}a[maxn*]; void Up(int r)
{
a[r].lsum = a[r<<].lsum, a[r].rsum = a[r<<|].rsum; if(a[r<<].lsum == a[r<<].Len())
a[r].lsum = a[r<<].lsum + a[r<<|].lsum;
if(a[r<<|].rsum == a[r<<|].Len())
a[r].rsum = a[r<<|].rsum + a[r<<].rsum; a[r].sum = max(a[r].lsum, max(a[r].rsum, a[r<<].rsum+a[r<<|].lsum));
}
void Build(int r, int L, int R)
{
a[r].L = L, a[r].R = R;
a[r].lsum = a[r].rsum = a[r].sum = a[r].Len(); if(L == R)return ; Build(r<<, L, a[r].Mid());
Build(r<<|, a[r].Mid()+, R);
}
void Insert(int r, int k, int e)
{
if( a[r].L == a[r].R )
{
a[r].lsum = a[r].rsum = a[r].sum = e;
return ;
} if(k <= a[r].Mid())
Insert(r<<, k, e);
else
Insert(r<<|, k, e); Up(r);
}
int Query(int r, int k)
{
if(a[r].sum == )return ;
if(k < a[r].L+a[r].lsum)return a[r].lsum;//判断是否在左边
if(k > a[r].R-a[r].rsum)return a[r].rsum;//判断是否在右边
if(k > a[r<<].R-a[r<<].rsum && k < a[r<<|].L+a[r<<|].lsum)//判断是否在中间
return a[r<<].rsum + a[r<<|].lsum; if(k <= a[r].Mid())
return Query(r<<, k);
else
return Query(r<<|, k);
} int main()
{
int N, M; while(scanf("%d%d", &N, &M) != EOF)
{
int x; char s[];
stack<int> sta; Build(, , N); while(M--)
{
scanf("%s", s); if(s[] == 'D')
{
scanf("%d", &x);
Insert(, x, );
sta.push(x);
}
else if(s[] == 'R' && sta.size())
{
Insert(, sta.top(), );
sta.pop();
}
else if(s[] == 'Q')
{
scanf("%d", &x);
printf("%d\n", Query(, x));
}
}
} return ; }