P1503 鬼子进村
题目背景
小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。
题目描述
描述 县城里有\(n\)个用地道相连的房子，第\(i\)个只与第\(i-1\)和第\(i+1\)个相连。这是有\(m\)个消息依次传来
1、消息为\(D\) \(x\)：鬼子将\(x\)号房子摧毁了，地道被堵上。
2、消息为\(R\) ：村民们将鬼子上一个摧毁的房子修复了。
3、消息为\(Q\) \(x\)：有一名士兵被围堵在\(x\)号房子中。
李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。
输入输出格式
输入格式：
第一行2个整数\(n\)，\(m\) \((n,m \le 50000)\)。
接下来\(m\)行，有如题目所说的三种信息共\(m\)条。
输出格式：
对于每一个被围堵的士兵，输出该士兵能够到达的房子数。
说明
若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。
这道题方法好多啊QAQ
提供一种点分裂合并的平衡树做法
平衡树每个节点维护一个\(segl\)和一个\(segr\),表示这个节点所代表的连续区间
这样我们在询问的时候只需要找到对应的点，看看这个点有多大就行了
对于删除，我们直接找到点，然后分情况把这个点分裂掉删掉就行了
对于修改，我们塞进去的时候看看可不可以和左右节点进行合并，如果可以，就把节点合并成一个
事实上实现起来有些麻烦，我用的是fhqtreap，写起来还算方便叭
Code:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define ls ch[now][0]
#define rs ch[now][1]
const int N=1e5+10;
int ch[N][2],segl[N],segr[N],val[N],tot,root,s[N],n,m,tot0,in[N];
void split(int now,int k,int &x,int &y)
{
if(!now){x=y=0;return;}
if(k>=segl[now])
x=now,split(rs,k,rs,y);
else
y=now,split(ls,k,x,ls);
}
int Merge(int x,int y)
{
if(!x||!y) return x+y;
if(val[x]<val[y])
{
ch[x][1]=Merge(ch[x][1],y);
return x;
}
else
{
ch[y][0]=Merge(x,ch[y][0]);
return y;
}
}
int New(int l,int r)
{
val[++tot]=rand(),segl[tot]=l,segr[tot]=r;
return tot;
}
void Insert(int k)
{
int x,y,z;
in[k]=0;
split(root,k,x,y);
split(y,k+1,z,y);
int now=x;while(rs) now=rs;
if(segr[now]==k-1)
{
++segr[now];
if(segr[now]==segl[z]-1)
{
segr[now]=segr[z];
root=Merge(x,y);//三个全合并
}
else
root=Merge(x,Merge(z,y));
}
else if(k==segl[z]-1)
{
--segl[z];
root=Merge(x,Merge(z,y));
}
else
root=Merge(Merge(x,New(k,k)),Merge(z,y));
}
int query(int k)
{
int x,y,ans,now;
split(root,k,x,y);
now=x;while(rs) now=rs;
ans=segr[now]+1-segl[now];
root=Merge(x,y);
return ans;
}
void destroy(int k)
{
int x,y,z;
in[k]=1;
split(root,k,x,y);
int now=x,rr;while(rs) now=rs;
rr=segr[now];
if(segl[now]==segr[now]) split(x,segl[now]-1,x,z);
else segr[now]=k-1;
if(k<rr) x=Merge(x,New(k+1,rr));
root=Merge(x,y);
}
int main()
{
scanf("%d%d",&n,&m);
root=New(1,n);
char op[3];
for(int x,i=1;i<=m;i++)
{
scanf("%s",op);
if(op[0]=='D')
{
scanf("%d",&x);
destroy(s[++tot0]=x);
}
else if(op[0]=='R')
Insert(s[tot0--]);
else
{
scanf("%d",&x);
if(in[x]) printf("0\n");
else printf("%d\n",query(x));
}
}
return 0;
}
2018.9.6