洛谷3203 弹飞绵羊(LCT)
2024-08-26 01:40:04
据说这个题当年的正解是分块qwq
根据题目所说,对于题目中的弹力系数,就相当于一条边,那么对于“跳出去”这个限制,我们可以选择建造一个新点\(n+1\)表示结束,那么每次,求一个点要多少次跳出去,只需要求\(n+1\)到\(x\)的点数,然后减1就行
直接上代码
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 1e6+1e2;
int size[maxn];
int fa[maxn];
int ch[maxn][3];
int st[maxn];
int n,m;
int rev[maxn];
int a[maxn];
int son(int x)
{
if (ch[fa[x]][0]==x) return 0;
else return 1;
}
bool notroot(int x)
{
return ch[fa[x]][0]==x || ch[fa[x]][1]==x;
}
void update(int x)
{
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void reverse(int x)
{
swap(ch[x][0],ch[x][1]);
rev[x]^=1;
}
void pushdown(int x)
{
if (rev[x])
{
if (ch[x][0]) reverse(ch[x][0]);
if (ch[x][1]) reverse(ch[x][1]);
rev[x]=0;
}
}
void rotate(int x)
{
int y=fa[x],z=fa[y];
int b=son(x),c=son(y);
if (notroot(y)) ch[z][c]=x;
fa[x]=z;
ch[y][b]=ch[x][!b];
fa[ch[x][!b]]=y;
ch[x][!b]=y;
fa[y]=x;
update(y);
update(x);
}
void splay(int x)
{
int y=x,cnt=0;
st[++cnt]=y;
while (notroot(y)) y=fa[y],st[++cnt]=y;
while (cnt) pushdown(st[cnt--]);
while(notroot(x))
{
int y=fa[x],z=fa[y];
int b=son(x),c=son(y);
if (notroot(y))
{
if(b==c) rotate(y);
else rotate(x);
}
rotate(x);
}
update(x);
}
void access(int x)
{
for (int y=0;x;y=x,x=fa[x])
{
splay(x);
ch[x][1]=y;
update(x);
}
}
void makeroot(int x)
{
access(x);
splay(x);
reverse(x);
}
int findroot(int x)
{
access(x);
splay(x);
while (ch[x][0])
{
pushdown(x);
x=ch[x][0];
}
return x;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
void link(int x,int y)
{
makeroot(x);
if (findroot(y)!=x) fa[x]=y;
}
void cut(int x,int y)
{
split(x,y);
if (ch[x][0] || ch[x][1] || fa[x]!=y || ch[y][son(x)^1]) return;
fa[x]=ch[y][0]=0;
}
int main()
{
n=read();
for (int i=1;i<=n;i++) a[i]=read(),link(i,min(i+a[i],n+1));
m=read();
for (int i=1;i<=m;i++)
{
int opt=read();
int x=read()+1;
if (opt==1)
{
split(x,n+1);
printf("%d\n",size[n+1]-1);
}
if (opt==2)
{
int k=read();
cut(x,min(x+a[x],n+1));
a[x]=k;
link(x,min(x+a[x],n+1));
}
}
return 0;
}
最新文章
- 【译】PHP的变量实现(给PHP开发者的PHP源码-第三部分)
- Fort.js – 时尚、现代的表单填写进度提示效果
- jquery的$.extend、$.fn.extend、 jQuery.extend( target, object1, [objectN])作用及区别
- Kafka简要图解
- POJ - 1422 Air Raid 二分图最大匹配
- 接口设计ie常见的问题
- Android 音乐播放
- Windows下MYSQL读取文件为NULL
- Postman----模拟服务器返回数据
- leetcode — combinations
- matlab 下标类型
- word2vec:基本的安装及使用简介
- Android笔记:Button
- Linux巩固记录(8) Hbase shell 基本使用
- 实验吧—Web——WP之 头有点大
- 直接new一个对象出来
- 关于Netty的学习前总结
- CentOS7 修改网卡名称
- wpf 窗口最小化后,触发某事件弹出最小化窗口并置顶
- 【转】snmpwalk常用用法