[洛谷1053]鬼子进村

关键词：

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

1
0
2
4

 1 #include<cstdio>
 2 const int maxn=5e4+10;
 3 int rt,ts;
 4 int t[maxn];
 5 int f[maxn],s[maxn][2];
 6 void rot(int x){
 7     int y=f[x],z=f[y],l,r;
 8     l=s[y][0]==x?0:1,r=l^1;
 9     if(y!=rt) s[z][s[z][1]==y]=x;
10     f[x]=z,f[y]=x,f[s[x][r]]=s[x][r]!=0?y:0;
11     s[y][l]=s[x][r],s[x][r]=y;
12 }
13 void splay(int x){
14     int y,z;
15     while(x!=rt){
16         y=f[x],z=f[y];
17         if(y==rt) rot(x),rt=x;
18         else{
19             rot((s[z][0]==y)==(s[y][0]==x)?y:x),rot(x);
20             if(z==rt) rt=x;
21         }
22     }
23 }
24 void ins(int k,int x){
25     int fa=0;
26     while(k&&t[k]!=x) fa=k,k=s[k][x>t[k]];
27     k=s[fa][x>t[fa]]=++ts;
28     t[k]=x,f[k]=fa;
29     splay(k);
30 }
31 void del(int k,int x){
32     while(t[k]!=x) k=s[k][x>t[k]];
33     splay(k);
34     rt=x=s[k][0];
35     while(s[x][1]) x=s[x][1];
36     s[x][1]=s[k][1],f[s[k][1]]=x;
37 }
38 int in_x(int k,int x,int now){
39     if(!k) return now;
40     if(x>t[k]) return in_x(s[k][1],x,t[k]);
41     else return in_x(s[k][0],x,now);
42 }
43 int ax_x(int k,int x,int now){
44     if(!k) return now;
45     if(x<t[k]) return ax_x(s[k][0],x,t[k]);
46     else return ax_x(s[k][1],x,now);
47 }
48 int n,m,x;
49 int q[maxn],top;
50 bool v[maxn];
51 char ch[3];
52 int main(){
53     scanf("%d%d",&n,&m);
54     rt=++ts,t[rt]=n+2,ins(rt,1);
55     while(m--){
56         scanf("%s",ch);
57         if(ch[0]==‘D‘){
58             scanf("%d",&x);
59             v[q[++top]=x]=1;
60             ins(rt,x+1);
61         }
62         if(ch[0]==‘R‘){
63             v[x=q[top--]]=0;
64             del(rt,x+1);
65         }
66         if(ch[0]==‘Q‘){
67             scanf("%d",&x);
68             if(v[x]) puts("0");
69             else printf("%d
",ax_x(rt,x+1,0)-in_x(rt,x+1,0)-1);
70         }
71     }
72     return 0;
73 }

洛谷——p1503鬼子进村

https://www.luogu.org/problemnew/show/P1503题目背景小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。题目描述... 查看详情

p1503鬼子进村(代码片段)

...亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。题目描述描述县城里有n个用地道相连的房子，第i个只与第i-1和第i+1个相连。这是有m个消息依次传来1、消息为Dx：鬼子将x号房... 查看详情

luogup1503鬼子进村(代码片段)

传送门 解题思路平衡树，支持插入，删除，找前驱后继，set水过。 #include<iostream>#include<cstdio>#include<cstring>#include<set>usingnamespacestd;constintMAXN=50005;inlineintrd()intx=0,f=1;charch= 查看详情

luogup1503鬼子进村(代码片段)

嘟嘟嘟 线段树好题。其实挺水的，想暴力怎么做：每一次从这个点开始向两边扩，直到遇到第一个摧毁的房屋。那么把暴力改成倍增，然后线段树查询区间和是否为０。时间复杂度O(nlog2n)。题解好像有线段树的O(nlogn)的做法... 查看详情

题解luogup1503鬼子进村(代码片段)

平衡树好题原题传送门这道题要用Splay，我博客里有对Splay的详细介绍这道题思维有点难，要把被摧毁的节点插入平衡树，而不是把没有摧毁的节点插入先把0和n+1插入平衡树，作为边界操作1：摧毁节点，把该点插入平衡树操作2... 查看详情

洛谷p1053音乐会的等待解题报告(代码片段)

P1823音乐会的等待题目描述\(N\)个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人\(A\)和\(B\)，如果他们是相邻或他们之间没有人比\(A\)或\(B\)高，那么他们是... 查看详情

luogu1503(代码片段)

P1503鬼子进村题目背景小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。题目描述描述县城里有n个用地... 查看详情

真tm操蛋——观《鬼子来了》有感

杀日本人有罪？日本人杀中国人为何无罪？战俘？双手沾满鲜血，仇人，为何杀仇人还要被自己人判刑，被仇人斩首？看了最后结局，我心里只有这两句话，同学说结局不好，我觉得结局恰恰很好，姜文是个很好的导演，他布置... 查看详情

1053.pathofequalweight(30)(代码片段)

1053.PathofEqualWeight(30)Givenanon-emptytreewithrootR,andwithweightWiassignedtoeachtreenodeTi.TheweightofapathfromRtoLisdefinedtobethesumoftheweightsofallthenodesalongthepathfromRtoanyleafnodeL.Nowgi 查看详情

错误1053：服务没有及时响应启动或控制请求？

】错误1053：服务没有及时响应启动或控制请求？【英文标题】：Error1053:Theservicedidnotrespondtothestartorcontrolrequestinatimelyfashion?【发布时间】：2011-03-2800:36:31【问题描述】：我构建了一个Windows服务，但我收到错误1053，但不知道为什... 查看详情

错误1053，服务没有及时响应请求

】错误1053，服务没有及时响应请求【英文标题】：Error1053.Theservicedidnotrespondtotherequestinatimelymanner【发布时间】：2021-03-1301:59:49【问题描述】：安装服务时出现错误。我代表管理员启动控制台，输入命令：ServiceKisTopshelf.exeinstall。... 查看详情

patadvancedlevel1053pathofequalweight(代码片段)

1053PathofEqualWeight(30)（30分）Givenanon-emptytreewithrootR,andwithweightW~i~assignedtoeachtreenodeT~i~.TheweightofapathfromRtoLisdefinedtobethesumoftheweightsofallthenodesalongthepathfromRtoanyleafnod 查看详情

1053.pathofequalweight(30)

Givenanon-emptytreewithrootR,andwithweightWi assignedtoeachtreenodeTi.The weightofapathfromRtoLisdefinedtobethesumoftheweightsofallthenodesalongthepathfromRtoanyleafnodeL.Nowgivenanyweighted 查看详情

cf1053eeulertour构造

正解:构造解题报告:传送门!下午写QAQ? 查看详情

错误 1053 服务没有及时响应启动或控制请求

】错误1053服务没有及时响应启动或控制请求【英文标题】：Error1053theservicedidnotrespondtothestartorcontrolrequestinatimelyfashion【发布时间】：2014-08-0508:52:54【问题描述】：我已经创建并安装了几次服务。最初它工作正常，但是在服务代码... 查看详情

pat1053.pathofequalweight

Givenanon-emptytreewithrootR,andwithweightWiassignedtoeachtreenodeTi.TheweightofapathfromRtoLisdefinedtobethesumoftheweightsofallthenodesalongthepathfromRtoanyleafnodeL.Nowgivenanyweightedtree,youares 查看详情

服务错误 1053：无法及时启动

】服务错误1053：无法及时启动【英文标题】：ServiceError1053:Couldnotstartintimelyfashion【发布时间】：2016-01-0911:11:36【问题描述】：在你问之前，是的，我搜索并搜索了这个问题，尝试了其他人为他们工作的东西，但一无所获。我试... 查看详情

pat1053.pathofequalweight(30)

1053.PathofEqualWeight(30)时间限制100ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueGivenanon-emptytreewithrootR,andwithweightWi assignedtoeachtreenodeTi.The weightofapathfromRtoLisdefinedtobeth 查看详情