关键词：
平衡树好题
原题传送门
这道题要用Splay，我博客里有对Splay的详细介绍
这道题思维有点难，要把被摧毁的节点插入平衡树，而不是把没有摧毁的节点插入
先把0和n+1插入平衡树，作为边界
操作1：摧毁节点，把该点插入平衡树
操作2：修复最后一个被摧毁节点的位置的可以用栈来求出，并把该点位置从平衡树中删除
操作三：搞一个vis数组，记录是否被摧毁，如果被摧毁了，直接输出0，没被摧毁的话，输出该点后继的位置-该点前驱的位置-1，这应该也很好理解qaq
剩下就没什么问题了（除了代码有点长）
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define root tree[0].ch[1]
#define inf 1000000005
using namespace std;
inline int read()
register int x=0,f=1;register char ch=getchar();
while(ch<‘0‘||ch>‘9‘)if(ch==‘-‘)f=-1;ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();
return x*f;
inline void write(register int x)
if(!x)putchar(‘0‘);if(x<0)x=-x,putchar(‘-‘);
static int sta[36];int cnt=0;
while(x)sta[cnt++]=x%10,x/=10;
while(cnt)putchar(sta[--cnt]+48);
inline int Min(register int a,register int b)
return a<b?a:b;
inline int Max(register int a,register int b)
return a>b?a:b;
struct Splay
int fa,ch[2],v,sum,rec;
tree[50005];
int tot=0;
inline bool findd(register int x)
return x==tree[tree[x].fa].ch[0]?0:1;
inline void connect(register int x,register int fa,register int son)
tree[x].fa=fa;
tree[fa].ch[son]=x;
inline void update(register int x)
tree[x].sum=tree[tree[x].ch[0]].sum+tree[tree[x].ch[1]].sum+tree[x].rec;
inline void rotate(register int x)
int Y=tree[x].fa;
int R=tree[Y].fa;
int Yson=findd(x);
int Rson=findd(Y);
int B=tree[x].ch[Yson^1];
connect(B,Y,Yson);
connect(Y,x,Yson^1);
connect(x,R,Rson);
update(Y),update(x);
inline void splay(register int x,register int to)
to=tree[to].fa;
while(tree[x].fa!=to)
int y=tree[x].fa;
if(tree[y].fa==to)
rotate(x);
else if(findd(x)==findd(y))
rotate(y),rotate(x);
else
rotate(x),rotate(x);
inline int newpoint(register int v,register int fa)
tree[++tot].v=v;
tree[tot].fa=fa;
tree[tot].sum=tree[tot].rec=1;
return tot;
inline void Insert(register int x)
int now=root;
if(root==0)
newpoint(x,0);
root=tot;
else
while(19260817)
++tree[now].sum;
if(x==tree[now].v)
++tree[now].rec;
splay(now,root);
return;
int nxt=x<tree[now].v?0:1;
if(!tree[now].ch[nxt])
int p=newpoint(x,now);
tree[now].ch[nxt]=p;
splay(p,root);
return;
now=tree[now].ch[nxt];
inline int find(register int x)
int now=root;
while(19260817)
if(x==tree[now].v)
splay(now,root);
return now;
int nxt=x<tree[now].v?0:1;
if(!tree[now].ch[nxt])
return 0;
now=tree[now].ch[nxt];
inline void delet(register int x)
int pos=find(x);
if(!pos)
return;
if(tree[pos].rec>1)
--tree[pos].rec;
--tree[pos].sum;
else
if(!tree[pos].ch[0]&&!tree[pos].ch[1])
root=0;
else if(!tree[pos].ch[0])
root=tree[pos].ch[1];
tree[root].fa=0;
else
int left=tree[pos].ch[0];
while(tree[left].ch[1])
left=tree[left].ch[1];
splay(left,tree[pos].ch[0]);
connect(tree[pos].ch[1],left,1);
connect(left,0,1);
update(left);
inline int lower(register int v)
int now=root,ans=-inf;
while(now)
if(tree[now].v<v&&tree[now].v>ans)
ans=tree[now].v;
if(tree[now].v>v)
now=tree[now].ch[0];
else
now=tree[now].ch[1];
return ans;
inline int upper(register int v)
int now=root,ans=inf;
while(now)
if(tree[now].v>v&&tree[now].v<ans)
ans=tree[now].v;
if(tree[now].v>v)
now=tree[now].ch[0];
else
now=tree[now].ch[1];
return ans;
bool vis[50005];
int stac[50005],top=-1;
int main()
memset(vis,false,sizeof(vis));
int n=read(),m=read();
Insert(0);
Insert(n+1);
while(m--)
char ch=getchar();
while(ch!=‘D‘&&ch!=‘R‘&&ch!=‘Q‘)
ch=getchar();
if(ch==‘D‘)
int x=read();
vis[x]=true;
stac[++top]=x;
Insert(x);
else if(ch==‘R‘)
vis[stac[top]]=false;
delet(stac[top--]);
else
int x=read();
if(vis[x])
puts("0");
else
write(upper(x)-lower(x)-1);
printf("
");
return 0;
luogup1503鬼子进村(代码片段)
传送门 解题思路平衡树，支持插入，删除，找前驱后继，set水过。 #include<iostream>#include<cstdio>#include<cstring>#include<set>usingnamespacestd;constintMAXN=50005;inlineintrd()intx=0,f=1;charch= 查看详情
p1503鬼子进村(代码片段)
...亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。题目描述描述县城里有n个用地道相连的房子，第i个只与第i-1和第i+1个相连。这是有m个消息依次传来1、消息为Dx：鬼子将x号房... 查看详情
洛谷p1503鬼子进村
P1503鬼子进村题目背景小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。题目描述描述县城里有n个用地... 查看详情
洛谷——p1503鬼子进村
...亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。题目描述描述县城里有n个用地道相连的房子，第i个只与第i-1和第i+1个相连。这是有m个消息依次传来1、消息为Dx：鬼子将x号房... 查看详情
luogu1503(代码片段)
P1503鬼子进村题目背景小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。题目描述描述县城里有n个用地... 查看详情
[洛谷1053]鬼子进村
...亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。题目描述描述县城里有n个用地道相连的房子，第i个只与第i-1和第i+1个相连。这是有m个消息依次传来1、消息为Dx：鬼子将x号房... 查看详情
luogup1084疫情控制(题解)(搜索+贪心)(代码片段)
luoguP1084疫情控制题目#include<iostream>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#defineilinline#definergregister#definelllongl 查看详情
luogup1452题解(代码片段)
管理备注：虽然此题解为乱搞，但是本乱搞是非常有意义的经典乱搞，故保留在题解区中供学习与参考。我们充分发扬人类智慧：将所有点全部绕原点旋转同一个角度，然后按\\(x\\)坐标排序。根据数学直觉，在随机旋转后，答... 查看详情
luogup1343地震逃生题解(代码片段)
题目链接：https://www.luogu.org/problemnew/show/P1343菜#include<queue>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;constintmaxn=10000 查看详情
luogup1549棋盘问题题解(代码片段)
luoguP1549棋盘问题（2）题解题目描述在(N*N)的棋盘上((1≤N≤10))，填入(1,2,…,N^2)共(N^2)个数，使得任意两个相邻的数之和为素数。例如：当(N=2)时，有：其相邻数的和为素数的有：(1+2,1+4,4+3,2+3)当(N=4)时，一种可以填写的方案如下：... 查看详情
luogup1456monkeyking题解(代码片段)
题目链接：https://www.luogu.org/problemnew/show/P1456左偏树并查集不加路径压缩吧...#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;constintmaxn=100000+10;s 查看详情
luogup2245星际导航题解(代码片段)
题目链接：https://www.luogu.org/problemnew/show/P2245=货车运输被逼着写过mst+lca后来成了mst+树剖#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;constintmaxn= 查看详情
luogup1003铺地毯题解(noip2011)(代码片段)
luoguP1003铺地毯 题目#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;inlineintread()intsum= 查看详情
luogup1111公路修建题解(代码片段)
题目链接：https://www.luogu.org/problemnew/show/P1111考察并查集，运用kruskal的思想很好做。注意几个小问题即可。1#include<iostream>2#include<cstdio>3#include<algorithm>4usingnamespacestd;5intn,m,fa[1000010];6intans 查看详情
luogup1312mayan游戏题解(noip2011)(代码片段)
luoguP1312Mayan游戏题目#include<bits/stdc++.h>#definelllonglong#definergregister#defineilinline#defineinf1<<30;usingnamespacestd;inta[10][10],b[6][10][10];inttmp[10][10];intway[10][3];intn,ans 查看详情
luogup8207题解(代码片段)
在暴力建边的情况下可以kruskal求生成树。但是这样是\\(O(n^2)\\)的。因为\\(lcm(x,y)=x\\timesy/\\gcd(x,y)\\)。所以\\(\\gcd(x,y)\\)越大我们的答案越优。但是枚举\\(x\\)和\\(y\\)求\\(\\gcd(x,y)\\)也是会超时的。但是我们用正难则反的思想，对于... 查看详情
luogup1307数字反转题解(代码片段)
题目链接：https://www.luogu.org/problemnew/show/P1307刚入门的一道字符串模拟，分四种情况讨论来做比较好。1#include<iostream>2#include<cstdio>3#include<cstring>4usingnamespacestd;5intmain()67chara[1001];8cin>> 查看详情
luogup1144最短路计数题解(代码片段)
题目链接：https://www.luogu.org/problemnew/show/P11441#include<iostream>2#include<cstdio>3#include<algorithm>4#include<queue>5#include<vector>6usingnamespacestd;7constintmod=1 查看详情