P1503 鬼子进村
2024-08-25 08:49:47
题目背景
小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》,剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队,于是独立团与鬼子展开游击战。
题目描述
描述 县城里有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
说明
若士兵被围堵在摧毁了的房子中,那只能等死了。。。。。。
Solution:
本题无旋treap。
实现过程略为繁琐,但是思路很简单:
初始时该序列就是一棵treap,每删除一个节点等价于将该节点放到根并分离左右子树(注意判断一个节点重复被删的情况),用栈记录下每次分离后的两棵新树,那么查询就是当前节点所在树的大小,修复节点就是个弹栈合并子树的过程。
代码:
/*Code by 520 -- 10.3*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=;
int n,m,stk[N],top,lsx[N],lsy[N];
bool vis[N];
int cnt,root,siz[N],ch[N][],fa[N],date[N],rnd[N]; il int newnode(int v){siz[++cnt]=,fa[cnt]=,date[cnt]=v,rnd[cnt]=rand();return cnt;} il void up(int rt){
siz[rt]=siz[ch[rt][]]+siz[ch[rt][]]+;
if(ch[rt][]) fa[ch[rt][]]=rt;
if(ch[rt][]) fa[ch[rt][]]=rt;
} int merge(int x,int y){
if(!x||!y) return x+y;
if(rnd[x]<rnd[y]) {ch[x][]=merge(ch[x][],y),up(x);return x;}
else {ch[y][]=merge(x,ch[y][]),up(y);return y;}
} void split(int rt,int v,int &x,int &y){
if(!rt) {x=y=;return;}
if(date[rt]<=v) x=rt,split(ch[rt][],v,ch[x][],y),up(x);
else y=rt,split(ch[rt][],v,x,ch[y][]),up(y);
} il void ins(int v){int x=,y=;split(root,v,x,y);root=merge(merge(x,newnode(v)),y);} int find(int x){return !fa[x]?x:find(fa[x]);} int main(){
scanf("%d%d",&n,&m);
For(i,,n) ins(i);
char opt[];
int x,y;
For(i,,m){
scanf("%s",opt);
if(opt[]=='D') {
scanf("%d",&x);
stk[++top]=x;vis[x]=;
split(find(x),x,lsx[top],lsy[top]);
split(lsx[top],x-,lsx[top],y);
fa[lsx[top]]=,fa[lsy[top]]=;
}
else if(opt[]=='R') merge(merge(lsx[top],stk[top]),lsy[top]),vis[stk[top--]]=;
else {
scanf("%d",&x);
if(vis[x]) {printf("0\n");continue;}
y=siz[find(x)];
printf("%d\n",y);
}
}
return ;
}
最新文章
- NHibernate简单使用介绍
- 烂泥:php5.6源码安装及php-fpm配置与nginx集成
- Flex调用java webservice
- SQL 大数据查询如何进行优化?
- R语言简单聚类分析
- linux挂载文件
- ASP.NET Core 菜鸟之路:从Startup.cs说起
- python识别html主要文本框
- Python线程:线程的调度-守护线程
- 20175223 《Java程序设计》 第八周学习总结
- idea使用svn出现问题解决办法
- 机器学习算法总结(五)——聚类算法(K-means,密度聚类,层次聚类)
- js string to date
- 重新看halcon模板匹配
- [No0000151]菜鸟理解.NET Framework中的CLI,CLS,CTS,CLR,FCL,BCL
- loj#6491. zrq 学反演
- 22.天眼查cookie模拟登陆采集数据
- Spring事务控制和回滚
- Dubbo创建提供者&;消费者工程
- django多对多中间表详解
热门文章
- 基于Cocos2d-x-1.0.1的飞机大战游戏迁移到Cocos2d-x-3.0版本,并移植到Android平台成功运行
- hdu1546Idiomatic Phrases Game(floyd+map)
- 文字排版 - bootStrap4常用CSS笔记
- dvwa学习笔记之xss
- webpack构建Vue项目引入jQ时发生“&#39;$&#39; is defined but never used”的处理
- Algorithm - 贪心算法使用场景 ( LEETCODE —— Best Time to Buy and Sell Stock II)
- 7.openldap使用ssl加密认证
- [BUAA OO]第三次博客作业
- Java实验五(客户端)
- 2017-2018-20172311 暑期编程作业:APP