Tunnel Warfare
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7703 Accepted Submission(s):
2981
warfare was carried out extensively in the vast areas of north China Plain.
Generally speaking, villages connected by tunnels lay in a line. Except the two
at the ends, every village was directly connected with two neighboring
ones.
Frequently the invaders launched attack on some of the villages and
destroyed the parts of tunnels in them. The Eighth Route Army commanders
requested the latest connection state of the tunnels and villages. If some
villages are severely isolated, restoration of connection must be done
immediately!
integers n and m (n, m ≤ 50,000) indicating the number of villages and events.
Each of the next m lines describes an event.
There are three different
events described in different format shown below:
D x: The x-th village
was destroyed.
Q x: The Army commands requested the number of villages
that x-th village was directly or indirectly connected with including
itself.
R: The village destroyed last was rebuilt.
request in order on a separate line.
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4
0
2
4
tr[x].l=tr[ls].l;
tr[x].r=tr[rs].r;
如果完整覆盖了左或右区间再做特殊处理
if(tr[ls].l==mid-l+1) tr[x].l+=tr[rs].l;
if(tr[rs].r==r-mid) tr[x].r+=tr[ls].r;
所以对于摧毁和恢复直接进行单点修改，将tr[x].l=tr[x].r=z(z为0或1)
对于询问，可以分别查询a向左的最长1串和a向右最长1串-1
特别的如果a已经被摧毁，则ans=-1
此时要做特判。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ls x<<1
#define rs x<<1|1
const int N=;
struct X
{
int l,r;
}tr[N<<];
int st[N];
void bu(int l,int r,int x)
{
if(l==r) tr[x].l=tr[x].r=;
else
{
int mid=l+(r-l)/;
bu(l,mid,ls);
bu(mid+,r,rs);
tr[x].l=tr[x].r=r-l+;
}
}
void chan(int l,int r,int x,int w,int z)
{
if(l==r) tr[x].l=tr[x].r=z;
else
{
int mid=l+(r-l)/;
if(w<=mid) chan(l,mid,ls,w,z);
else chan(mid+,r,rs,w,z);
tr[x].l=tr[ls].l;tr[x].r=tr[rs].r;
if(tr[x].l==mid-l+) tr[x].l+=tr[rs].l;
if(tr[x].r==r-mid) tr[x].r+=tr[ls].r;
}
}
int ask1(int l,int r,int x,int w)
{
if(w==r) return tr[x].r;
else
{
int mid=l+(r-l)/,re;
if(w>mid)
{
re=ask1(mid+,r,rs,w);
if(w-mid==re) re+=tr[ls].r;
}
else re=ask1(l,mid,ls,w);
return re;
}
}
int ask2(int l,int r,int x,int w)
{
if(w==l) return tr[x].l;
else
{
int mid=l+(r-l)/,re;
if(w<=mid)
{
re=ask2(l,mid,ls,w);
if(mid-w+==re) re+=tr[rs].l;
}
else re=ask2(mid+,r,rs,w);
return re;
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int s=;
memset(st,,sizeof(st));
memset(tr,,sizeof(tr));
bu(,n,);
while(m--)
{
char c;
scanf("\n%c",&c);
if(c=='D')
{
scanf("%d",&st[++s]);
chan(,n,,st[s],);
}
else if(c=='R') chan(,n,,st[s--],);
else
{
int a,ans;
scanf("%d",&a);
ans=ask1(,n,,a)+ask2(,n,,a)-;
if(ans>) printf("%d\n",ans);
else printf("0\n");
}
}
}
return ;
}