P3203 [HNOI2010]彈飛綿羊

題目描述

詳見：P3203?[HNOI2010]彈飛綿羊

solution

這是一道LCT的裸題。

但是我并不想用LCT解決此題（In fact 是不會LCT ~QAQ）

于是我們開始大力分塊。

考慮把彈跳裝置分塊，我們每次需要知道在一個塊內需要跳幾次以及跳出這個塊后到達哪一個節點，這樣保證了每一個塊的信息不會對其他塊的信息產生影響，且我們可以用DP在??? 的時間內預處理出上述信息。

查詢時每次跳轉到一個之后的塊中，沿途統計答案。

修改時由于塊與塊之間獨立，因此直接暴力修改需要修改的一塊信息即可。

時間復雜度? ?

Code

#include<bits/stdc++.h> using namespace std; const int MAXN=2e5+50; int a[MAXN],color[MAXN],n,Size; struct fnode{int x,y; } f[MAXN]; inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } void change(int i) //求出i位置的信息 {if (i+a[i]<=n){if (color[i]==color[i+a[i]]) f[i]=(fnode){f[i+a[i]].x,f[i+a[i]].y+1};else f[i]=(fnode){i+a[i],1};}else f[i]=(fnode){-1,1}; } int main() {n=read(),Size=trunc(sqrt(n));for (int i=1;i<=n;i++) a[i]=read(),color[i]=(i-1)/Size+1;for (int i=n;i>=1;i--) change(i); //預處理 //for (int i=1;i<=n;i++) cout<<i<<":"<<f[i].x<<" "<<f[i].y<<endl;int Case=read();while (Case--){int opt=read(),x=read()+1; //標號從0開始 if (opt==1){int ans=0;while (x!=-1) ans+=f[x].y,x=f[x].x; //統計答案 printf("%d\n",ans);}else{int y=read(); a[x]=y;for (int i=color[x]*Size;i>=(color[x]-1)*Size+1;i--) change(i); //用與預處理相同的方法暴力修改 //for (int i=1;i<=n;i++) cout<<i<<":"<<f[i].x<<" "<<f[i].y<<endl;}}return 0; }

?

總結

以上是生活随笔為你收集整理的P3203 [HNOI2010]弹飞绵羊的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。