关键词：
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条。
输出格式：
对于每一个被围堵的士兵，输出该士兵能够到达的房子数。
输入输出样例
说明
若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。
sol：对于R显然可以用一个栈来搞一搞。难点是另两个
对于每个D，如果那个点不在栈里就插入那个点
对于A，我们查询那个点的后继和前驱，减一下就可以了
Ps：说起来容易，写起来真操蛋
#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() ll s=0; bool f=0; char ch=‘ ‘; while(!isdigit(ch)) f|=(ch==‘-‘); ch=getchar(); while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); return (f)?(-s):(s); #define R(x) x=read() inline void write(ll x) if(x<0) putchar(‘-‘); x=-x; if(x<10) putchar(x+‘0‘); return; write(x/10); putchar((x%10)+‘0‘); return; #define W(x) write(x),putchar(‘ ‘) #define Wl(x) write(x),putchar(‘ ‘) const int N=50005; int n,Q; namespace Pht int Points=0,Root; int Child[N][2],Parent[N]; int Size[N]; int Pos[N]; //Pos[i]表示标号为i的节点在平衡树上的位置 int Id[N]; //Id[i]表示树上的节点i的标号为i int Stack[N],Top=0; 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=0; Insert(0); Insert(n+1); inline int Check(int x) return (Child[Parent[x]][0]==x)?0:1; inline void PushUp(int x) Size[x]=Size[Child[x][0]]+Size[Child[x][1]]+1; Pos[Id[Child[x][0]]]=Child[x][0]; Pos[Id[Child[x][1]]]=Child[x][1]; inline void Rotate(int x) int y,z,oo; y=Parent[x]; z=Parent[y]; oo=Check(x); Child[y][oo]=Child[x][oo^1]; Parent[Child[x][oo^1]]=y; Child[z][Check(y)]=x; Parent[x]=z; Child[x][oo^1]=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==0) Root=At; inline void Insert(int Val) int Now=Root,Par=0; while(Now) Par=Now; Now=Child[Now][(Val>Id[Now])?1:0]; Now=++Points; if(Par) Child[Par][(Val>Id[Par])?1:0]=Now; Parent[Now]=Par; Child[Now][0]=Child[Now][1]=0; Size[Now]=1; Id[Now]=Val; Pos[Val]=Now; Splay(Now,0); inline void Remove(int Val) // printf("Val=%d ",Val); int Lower=Ask_Lower(Val); // printf("Lower=%d ",Lower); int Upper=Ask_Upper(Val); // printf("Upper=%d ",Upper); Splay(Lower,0); Splay(Upper,Lower); Pos[Id[Child[Upper][0]]]=0; Id[Child[Upper][0]]=-1; Child[Upper][0]=0; inline int Find(int Val) int Now=Root; while(Now&&(Id[Now]!=Val)) Now=Child[Now][(Val>Id[Now])?1:0]; return Now; inline int Ask_Lower(int Val) int Pos=Find(Val); // printf("Pos=%d ",Pos); Splay(Pos,0); // puts("End-Splay"); int Now=Root; Now=Child[Now][0]; while(Child[Now][1]) Now=Child[Now][1]; return Now; inline int Ask_Upper(int Val) int Pos=Find(Val); Splay(Pos,0); int Now=Root; Now=Child[Now][1]; while(Child[Now][0]) Now=Child[Now][0]; 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]=1; Insert(x); break; case ‘R‘: Instack[Stack[Top]]=0; Remove(Stack[Top--]); break; case ‘Q‘: R(x); if(Instack[x]) puts("0"); else Insert(x); Wl(Id[Ask_Upper(x)]-Id[Ask_Lower(x)]-1); Remove(x); break; int main() R(n); R(Q); Pht::Solve(); return 0; /* input 7 9 D 3 D 6 D 5 Q 4 Q 5 R Q 4 R Q 4 output 1 0 2 4 */
luogup1503鬼子进村(代码片段)
传送门 解题思路平衡树，支持插入，删除，找前驱后继，set水过。 #include<iostream>#include<cstdio>#include<cstring>#include<set>usingnamespacestd;constintMAXN=50005;inlineintrd()intx=0,f=1;charch= 查看详情
[luogu]方差(代码片段)
https://www.luogu.org/problemnew/show/P1471线段树维护区间数的平方之和与和#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;#defineDBdouble#definegcgetchar()#definelsonjd<<1#definersonjd<<1| 查看详情
[luogu]奶酪(代码片段)
https://www.luogu.org/problemnew/show/P3958连边bfs/并查集#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>usingnamespacestd;constintN=1010;#definegcgetchar()struc 查看详情
[luogu]树(代码片段)
https://www.luogu.org/problemnew/show/P4092树剖+线段树区间修改，单点查询#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;inlineintread()intret;scanf("%d",&ret);returnret;intn,T;intnow=1,head[N] 查看详情
[luogu4556]雨天的尾巴(代码片段)
[luogu4556]雨天的尾巴luogu发现是一顿子修改然后再询问,那么把修改树上差分一下再线段树合并但是...如果你只有35分...https://www.luogu.org/discuss/show/88259#include<bits/stdc++.h>usingnamespacestd;constint_=1e5+5;intre()intx=0,w=1;charch=get 查看详情
[luogu]计数(代码片段)
https://www.luogu.org/problemnew/show/P3130#include<cstdio>#include<iostream>usingnamespacestd;constintN=2e5+10;#defineLLlonglongLLW[N<<2],Min[N<<2],Size[N<<2],F[N<< 查看详情
[luogu]魔法树(代码片段)
https://www.luogu.org/problemnew/show/P3833树链剖分+线段树为啥会RE？？不解#include<iostream>#include<cstdio>usingnamespacestd;constintN=1e5+10;#defineLLlonglongintn,T,now=1,tim;inttop[N],tree[N],lst[N], 查看详情
hdu1503lcs(字符串合并输出)(代码片段)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1503题目大意：给两个字符串，组成一个长度尽可能小的字符串，它包含上述两个字符串，且原字符串中的字符在该串中的相对位置不变。SampleInputapplepeachananasbananapearpeach SampleOutputap... 查看详情
[luogu]火柴排队(代码片段)
https://www.luogu.org/problemnew/show/P1966离散化树状数组求逆序对个数#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;constintMod=99999997;structNodeintnum,wher;G_1[N],G_2[N];intn;intMap1[N],Map2[ 查看详情
[luogu]逛公园(代码片段)
https://www.luogu.org/problemnew/show/P3953 #include<cstdio>#include<cstring>#include<cctype>usingnamespacestd;constintN=1e5+1,K=51;intn,m,k,p,tot,ans=0;intfirst[N],next[N 查看详情
[luogu]矩形覆盖(代码片段)
https://www.luogu.org/problemnew/show/P1034数据太水爆搜过掉#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>constintN=55;intn,K,Use[N],A[N],Answer=1e7;intMaxx,Minx 查看详情
[luogu4315]月下“毛景树”(代码片段)
[luogu4315]月下“毛景树”luogu联赛前复习一发树剖.不会告诉你WA了4发#definelsx<<1,l,mid#definersx<<1|1,mid+1,r#include<bits/stdc++.h>usingnamespacestd;constint_=1e5+5;intre()intx=0,w=1;charch=getchar();whil 查看详情
[luogu]mayan游戏(代码片段)
https://www.luogu.org/problemnew/show/P1312太恶心了#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<string>#include<iostream>usingnamespacest 查看详情
[luogu5172sum(代码片段)
luogu5172Sum\[\beginaligned\sum_d=1^n(-1)^\lfloord\sqrtr\rfloor=&\sum_d=1^n(-1)^\lfloord\sqrtr\rfloor\mod\2\=&\sum_d=1^n1-2(\lfloord\sqrtr\rfloor\mod\2)\=&n-\sum_d=1^n2(\lflo 查看详情
最长公共子序列hdu1503(代码片段)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1503题意：给你两个字符串，把这两个字符串合并，使合并之后的字符串最短，并且合并之后的字符之间的相对位置和在原字符串中的相对位置相同，其实意思就是叫我们求最长公共子... 查看详情
[luogu]聪明的质监员(代码片段)
https://www.luogu.org/problemnew/show/P1314满足单调性所以，二分W，进行检验#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>usingnamespacestd;constintN=2e5+10;#defineLLlongl 查看详情
luogup1503鬼子进村(代码片段)
嘟嘟嘟 线段树好题。其实挺水的，想暴力怎么做：每一次从这个点开始向两边扩，直到遇到第一个摧毁的房屋。那么把暴力改成倍增，然后线段树查询区间和是否为０。时间复杂度O(nlog2n)。题解好像有线段树的O(nlogn)的做法... 查看详情
luogu1144(代码片段)
最短路计数#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10,M=2e6+10;constintoo=(1<<30);#definegcgetchar()inlineintread()intx=0;charc=gc;while(c<‘0‘||c>‘9‘)c=gc;while(c>=‘0‘&a 查看详情