P1503 鬼子进村
题目背景
小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。
题目描述
描述 县城里有n个用地道相连的房子，第i个只与第i-1和第i+1个相连。这是有m个消息依次传来
1、消息为D x：鬼子将x号房子摧毁了，地道被堵上。
2、消息为R ：村民们将鬼子上一个摧毁的房子修复了。
3、消息为Q x：有一名士兵被围堵在x号房子中。
李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。
输入输出格式
输入格式：
第一行2个整数n，m（n，m<=50000）。
接下来m行，有如题目所说的三种信息共m条。
输出格式：
对于每一个被围堵的士兵，输出该士兵能够到达的房子数。
输入输出样例
输入样例#1：
7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4
输出样例#1：
1
0
2
4
说明
若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。
sol：对于R显然可以用一个栈来搞一搞。难点是另两个
对于每个D，如果那个点不在栈里就插入那个点
对于A，我们查询那个点的后继和前驱，减一下就可以了
Ps：说起来容易，写起来真操蛋
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=;
int n,Q;
namespace Pht
{
int Points=,Root;
int Child[N][],Parent[N];
int Size[N];
int Pos[N]; //Pos[i]表示标号为i的节点在平衡树上的位置
int Id[N]; //Id[i]表示树上的节点i的标号为i int Stack[N],Top=;
bool Instack[N]; inline void Init();
inline int Check(int x);
inline void PushUp(int x);
inline void Rotate(int x);
inline void Splay(int At,int To);
inline void Insert(int Val);
inline void Remove(int Val);
inline int Find(int Val);
inline int Ask_Upper(int Val);
inline int Ask_Lower(int Val); inline void Init()
{
Points=Root=;
Insert(); Insert(n+);
}
inline int Check(int x)
{
return (Child[Parent[x]][]==x)?:;
}
inline void PushUp(int x)
{
Size[x]=Size[Child[x][]]+Size[Child[x][]]+;
Pos[Id[Child[x][]]]=Child[x][];
Pos[Id[Child[x][]]]=Child[x][];
}
inline void Rotate(int x)
{
int y,z,oo;
y=Parent[x];
z=Parent[y];
oo=Check(x);
Child[y][oo]=Child[x][oo^]; Parent[Child[x][oo^]]=y;
Child[z][Check(y)]=x; Parent[x]=z;
Child[x][oo^]=y; Parent[y]=x;
PushUp(x); PushUp(y);
}
inline void Splay(int At,int To)
{
while(Parent[At]!=To)
{
int Father=Parent[At];
if(Parent[Father]==To)
{
Rotate(At);
}
else if(Check(At)==Check(Father))
{
Rotate(Father); Rotate(At);
}
else
{
Rotate(At); Rotate(At);
}
}
Pos[Id[At]]=At;
if(To==) Root=At;
}
inline void Insert(int Val)
{
int Now=Root,Par=;
while(Now)
{
Par=Now;
Now=Child[Now][(Val>Id[Now])?:];
}
Now=++Points;
if(Par) Child[Par][(Val>Id[Par])?:]=Now;
Parent[Now]=Par;
Child[Now][]=Child[Now][]=;
Size[Now]=;
Id[Now]=Val;
Pos[Val]=Now;
Splay(Now,);
}
inline void Remove(int Val)
{
// printf("Val=%d\n",Val);
int Lower=Ask_Lower(Val);
// printf("Lower=%d\n",Lower);
int Upper=Ask_Upper(Val);
// printf("Upper=%d\n",Upper);
Splay(Lower,);
Splay(Upper,Lower);
Pos[Id[Child[Upper][]]]=;
Id[Child[Upper][]]=-;
Child[Upper][]=;
}
inline int Find(int Val)
{
int Now=Root;
while(Now&&(Id[Now]!=Val))
{
Now=Child[Now][(Val>Id[Now])?:];
}
return Now;
}
inline int Ask_Lower(int Val)
{
int Pos=Find(Val);
// printf("Pos=%d\n",Pos);
Splay(Pos,);
// puts("End-Splay");
int Now=Root;
Now=Child[Now][];
while(Child[Now][]) Now=Child[Now][];
return Now;
}
inline int Ask_Upper(int Val)
{
int Pos=Find(Val);
Splay(Pos,);
int Now=Root;
Now=Child[Now][];
while(Child[Now][]) Now=Child[Now][];
return Now;
}
inline void Solve()
{
Init();
while(Q--)
{
int x;
char ch=' '; while(!isupper(ch)) ch=getchar();
switch(ch)
{
case 'D':
R(x);
if(!Instack[x])
{
Stack[++Top]=x;
Instack[x]=;
Insert(x);
}
break;
case 'R':
Instack[Stack[Top]]=;
Remove(Stack[Top--]);
break;
case 'Q':
R(x);
if(Instack[x]) puts("");
else
{
Insert(x);
Wl(Id[Ask_Upper(x)]-Id[Ask_Lower(x)]-);
Remove(x);
}
break;
}
}
}
}
int main()
{
R(n); R(Q);
Pht::Solve();
return ;
}
/*
input
7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4
output
1
0
2
4
*/