听说这道题还能用分块做。。。 lct的第二题，写起来磕磕绊绊。主要是因为lct把“原树”拆成了“辅助树”，换句话说原树就是棵虚数，而我做题的时候一直在往原树上套，套着套着就乱掉了。。。 引用一下这位大神的博客：
http://blog.csdn.net/wzq_qwq/article/details/47397539
他的写法看起来十分简单有木有。而且也不用再套上其他的数据结构，是我找到的最好的方法了。 他的做法就是一开始把所有能够走到的点连起来。虽然看起来不是一棵二叉树，但是后面access的时候会不断地调整。（类似于裸lct一开始每个点都是一棵树，然后不断access合并重组）本身我对翻转操作不太熟悉，这个做法在没有用到翻转操作的情况下断链重连厉害了啊。 假设出界的节点是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); PRintf("%d/n",size[ch[x][0]]+1);} if (opt == 2) {scanf("%d%d",&x,&y); x++; if (x+y>n) link(x,0); else link(x,x+y);} } return 0;}新闻热点
疑难解答
