【BZOJ4764】弹飞大爷 LCT
生活随笔
收集整理的這篇文章主要介紹了
【BZOJ4764】弹飞大爷 LCT
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
【BZOJ4764】彈飛大爺
Description
自從WC退役以來,大爺是越來越懶惰了。為了幫助他活動筋骨,也是受到了彈飛綿羊一題的啟發,機房的小伙伴們決定齊心合力構造一個下面這樣的序列。這個序列共有N項,每項都代表了一個小伙伴的力量值,如果大爺落到了第i個小伙伴的手里,那么第i個小伙伴會把大爺彈到第i+ai個小伙伴手里,其中ai就是第i個小伙伴的力量值,也就是序列的第i項。然而,因為大爺太沉了,所以有些小伙伴不能撐到鍛(you)煉(xi)結束,所以我們中途會替換一些小伙伴,也就是改變序列的某些項。而且,因為大爺太沉了,所以有些小伙伴不能把大爺扔向前方,而是會把大爺往反方向扔,也就是序列中的一些項會是負的(當然,也可能是零嘍)。現在機智的大爺通過在空中的觀察,已經知道小伙伴們的所有活動——即初始序列、所有更改操作,他想請你算一算,如果他在某時刻落到了某個位置,那么他會在幾次彈起之后落到小伙伴序列之外(畢竟摔在地上還是蠻疼的)。Input
第一行為兩個整數N和M,代表序列長度和操作次數。 第二行為N個整數,代表初始的小伙伴序列。 接下來有M行,每行代表一個操作。 如果這一行的第一個數是1,代表該操作是一個詢問操作,接下來一個數X,代表詢問此時大爺從X處,經過幾次彈起會摔在地上。如果永遠不會摔在地上,請輸出-1。 如果這一行的第一個數是2,代表該操作是一個更改操作,接下來兩個數X,Y,代表將序列的第X項改為Y。 N,M <= 200000 ?|Ai| < NOutput
對于每次詢問操作,輸出彈起次數或-1。Sample Input
3 191 1 1
1 1
1 2
1 3
2 1 2
1 1
1 2
1 3
2 3 -1
1 1
1 2
1 3
2 2 233
1 1
1 2
1 3
2 2 -233
1 1
1 2
1 3
Sample Output
32
1
2
2
1
-1
-1
-1
3
1
2
3
1
2
題解:題中所給的顯然是一片基環內向樹森林,那么我們先不考慮環,用LCT維護所有樹。新建一個點n+1,表示序列外面。在詢問時,如果一個點的根不是n+1,則輸出-1,否則輸出那個點的深度即可。在修改時,我們需要進行如下分類討論:
首先是拆開原來的邊,如果原來的邊是非樹邊,那么不用管,否則如果這條邊是環上的邊,那么我們要將環邊link上。然后cut。
然后是連新邊,如果新邊已經連通,則不連,否則link。
?
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn=200010; int n,m; int to[maxn]; struct node {int fa,ch[2],siz; }s[maxn]; inline bool isr(int x) {return x!=s[s[x].fa].ch[0]&&x!=s[s[x].fa].ch[1];} inline void pushup(int x) {s[x].siz=s[s[x].ch[0]].siz+s[s[x].ch[1]].siz+1; } inline void rotate(int x) {int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);if(!isr(y)) s[z].ch[y==s[z].ch[1]]=x;s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];if(s[x].ch[d^1]) s[s[x].ch[d^1]].fa=y;s[x].ch[d^1]=y;pushup(y),pushup(x); } inline void splay(int x) {while(!isr(x)){int y=s[x].fa,z=s[y].fa;if(!isr(y)){if((x==s[y].ch[0])^(y==s[z].ch[0])) rotate(x);else rotate(y);}rotate(x);} } inline void access(int x) {for(int y=0;x;splay(x),s[x].ch[1]=y,pushup(x),y=x,x=s[x].fa); } inline int findr(int x) {access(x),splay(x);while(s[x].ch[0]) x=s[x].ch[0];return x; } inline int rd() {int ret=0,f=1; char gc=getchar();while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();return ret*f; } int main() {n=rd(),m=rd();int i,a,b;for(i=1;i<=n;i++) a=i+rd(),to[i]=(a>n||a<1)?n+1:a,s[i].siz=1;s[n+1].siz=1;for(i=1;i<=n;i++){if(findr(to[i])!=i) splay(i),s[i].fa=to[i];}for(i=1;i<=m;i++){if(rd()==1){a=rd(),b=findr(a);if(b!=n+1) printf("-1\n");else printf("%d\n",s[s[a].ch[0]].siz);}else{a=rd(),b=findr(a);s[s[a].ch[0]].fa=0,s[a].ch[0]=0,pushup(a);if(b!=n+1&&findr(to[b])!=b) splay(b),s[b].fa=to[b];b=a+rd(),to[a]=(b>n||b<1)?n+1:b;if(findr(to[a])!=a) splay(a),s[a].fa=to[a];/*s[s[a].ch[0]].fa=0,s[a].ch[0]=0,pushup(a);splay(b);if(b!=n+1&&a!=b&&findr(to[b])!=b) s[b].fa=to[b],splay(to[b]);b=a+rd(),to[a]=(b>n||b<1)?n+1:b;b=findr(to[a]),splay(b);if(b!=a) s[a].fa=to[a];*/}}return 0; }//3 10 1 1 1 2 1 2 2 3 -1 2 2 233 1 1 1 2 1 3 2 2 -233 1 1 1 2 1 3?
轉載于:https://www.cnblogs.com/CQzhangyu/p/7898508.html
總結
以上是生活随笔為你收集整理的【BZOJ4764】弹飞大爷 LCT的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: HDU 4323 Magic Numbe
- 下一篇: Google Maglev 牛逼的网络负