CF13E Holes LCT
2024-09-05 18:26:58
CF13E Holes
双倍经验题,几乎同[HNOI2010]弹飞绵羊,LCT练手题,LG没有LCT题解于是发一波。
从当前点向目标点连边,构成一棵树,带修改就用LCT动态维护答案,由于不用查询修改链上信息,不需要与makeroot有关的函数。分块也可以写。
不会LCT的话可以看看我的LCT总结。
#include<cstdio>
#include<cctype>
#define R register
#define I inline
using namespace std;
const int S=100003;
char buf[1000000],*p1,*p2;
I char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,S,stdin),p1==p2)?EOF:*p1++;}
I int rd(){
R int f=0; R char c=gc();
while(c<48||c>57) c=gc();
while(c>47&&c<58) f=f*10+(c^48),c=gc();
return f;
}
struct splay{int p,d[2],s;}e[S];
I int min(int x,int y){return x<y?x:y;}
I int nrt(int x){return e[e[x].p].d[0]==x||e[e[x].p].d[1]==x;}
I void psu(int x){e[x].s=e[e[x].d[0]].s+e[e[x].d[1]].s+1;}
I void rtt(int x){
R int f=e[x].p,g=e[f].p,b=e[f].d[0]==x,c=e[x].d[b];
if(nrt(f)) e[g].d[e[g].d[1]==f]=x;
if(c) e[c].p=f;
e[x].p=g,e[f].p=x,e[x].d[b]=f,e[f].d[!b]=c,psu(f);
}
I void spl(int x){
for(R int f,g;nrt(x);rtt(x)){
f=e[x].p,g=e[f].p;
if(nrt(f))
rtt((e[g].d[1]==f)^(e[f].d[1]==x)?x:f);
}
psu(x);
}
I void acc(int x){
for(R int y=0;x;x=e[y=x].p)
spl(x),e[x].d[1]=y,psu(x);
}
I void cut(int x){acc(x),spl(x),e[e[x].d[0]].p=0,e[x].d[0]=0,psu(x);}
I int frt(int x){
acc(x),spl(x);
while(e[x].d[0])
x=e[x].d[0];
return x;
}
int main(){
R int n=rd(),m=rd(),i,x,y,z;
for(i=1;i<=n;++i){
x=rd(),z=i+x;
if(z<=n)
e[i].p=z;
}
for(i=1;i<=m;++i){
x=rd(),y=rd();
if(x)
printf("%d ",frt(y)),printf("%d\n",e[y].s);
else{
x=rd(),cut(y),z=x+y;
if(z<=n)
e[y].p=z;
}
}
return 0;
}
最新文章
- MapReduce的ReduceTask任务的运行源码级分析
- TYVJ 1117 BFS
- 问题导向VS目标导向:领导者要倾向哪种?
- SSH环境 jsp url跳转,带中文参数乱码问题
- mysql初识之数据文件及其他文件
- JPA query 基本语法解释
- ecshop物料库存管理
- 【JUnit4.10来源分析】0导航
- greenlet 详解
- String类的实现(4)写时拷贝浅析
- 磁盘配额quota
- python中用xpath匹配文本段落内容的技巧
- TensorFlow 常用函数与方法
- RabbitMQ 1
- python3.x与2.x区别
- hibernate 解决 java.lang.NoClassDefFoundError: org/hibernate/cfg/Configuration
- curl和wget的区别和使用
- centos7 克隆 网卡无法启用
- options.html:1 Refused to load the script &#39;xxxx&#39; because it violates the following Content Security Policy directive: ";script-src &#39;self&#39; blob: filesystem: chrome-extension-resource:";.
- 初级字典树查找在 Emoji、关键字检索上的运用 Part-2
热门文章
- ASP.NET 通过配置hiddenSegment禁止目录下资源通过Url形式访问
- MySql EF6 DBFirst 向导无法生成 edmx 解决方法(同:您的项目引用了最新实体框架;但是,找不到数据链接所需的与版本兼容的实体框架数据库提供程序)
- [翻译] DDExpandableButton
- 《C++ Primer Plus》读书笔记之七—内存模型和名称空间
- matlab 函数句柄@的介绍_什么是函数句柄(转)
- Linux 下shell 编程学习脚手架
- php请求页面将返回的页面发送email
- ASP.NET Web Api vs Node.js Benchmark
- 事后诸葛亮之Alpha十天冲刺之失败总结
- 在web.xml中配置404错误拦截