聽說這道題還能用分塊做。。。 lct的第二題，寫起來磕磕絆絆。主要是因為lct把“原樹”拆成了“輔助樹”，換句話說原樹就是棵虛數，而我做題的時候一直在往原樹上套，套著套著就亂掉了。。。 引用一下這位大神的博客：
http://blog.csdn.net/wzq_qwq/article/details/47397539
他的寫法看起來十分簡單有木有。而且也不用再套上其他的數據結構，是我找到的最好的方法了。 他的做法就是一開始把所有能夠走到的點連起來。雖然看起來不是一棵二叉樹，但是后面access的時候會不斷地調整。（類似于裸lct一開始每個點都是一棵樹，然后不斷access合并重組）本身我對翻轉操作不太熟悉，這個做法在沒有用到翻轉操作的情況下斷鏈重連厲害了啊。 假設出界的節(jié)點是0，詢問的時候查找0的左子樹大小，也就是能夠走到終點的點的個數。
#include<cmath>#include<cstdio>#include<vector>#include <queue>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 2000000000#define mod 1000000007#define N 200010#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)#define mm(x,a) memset(x,a,sizeof(x));using namespace std;int size[N],ch[N][2],fa[N];bool rt[N];int n,m,i,x,y,opt;void pushup(int x) {size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}void rotate(int x) { int y = fa[x]; int kind; if (ch[y][1] == x) kind = 1; else kind = 0;//1左旋0右旋 ch[y][kind] = ch[x][!kind]; fa[ch[y][kind]] = y; fa[x] = fa[y]; fa[y] = x; ch[x][!kind] = y; if (rt[y] > 0) rt[y] = false,rt[x] = true; else ch[fa[x]][ch[fa[x]][1]==y] = x; pushup(y);}void splay(int x){ while (rt[x] == false) { int fa1 = fa[x]; int fa2 = fa[fa1]; if (rt[fa1] > 0) rotate(x); else if ((ch[fa2][1] == fa1) == (ch[fa1][1] == x)) rotate(fa1),rotate(x);//同側 else rotate(x),rotate(x);//異側 } pushup(x);}void Access(int x){ int y = 0; while (x > 0) { splay(x); rt[ch[x][1]] = true;//分裂出右子樹 ch[x][1] = y; rt[ch[x][1]] = false;//前一棵樹連到當前右子樹 pushup(x); y = x; x = fa[x]; }}void c_root(int x){ Access(x); splay(x);}void link(int x,int y){ c_root(x); fa[ch[x][0]] = 0; rt[ch[x][0]] = 1; ch[x][0] = 0; fa[x] = y; pushup(x);}int main(){ scanf("%d",&n); fo(i,1,n) rt[i] = true,size[i] = 1; fo(i,1,n) { scanf("%d",&x); if (i + x <= n) link(i,i+x); } scanf("%d",&m); while (m--) { scanf("%d",&opt); if (opt == 1) {scanf("%d",&x); x++; c_root(x);新聞熱點
疑難解答
