相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4573
数据生成器:http://paste.ubuntu.com/24208883/
神犇题解Ⅰ:http://blog.csdn.net/werkeytom_ftd/article/details/56671440
神犇题解Ⅱ:http://sxy-cnyali.logdown.com/posts/1398090-zjoi2016
解题报告
这题似乎有三种做法?我们这里只讨论$LCT$的做法
首先将询问离线,对于每一次0/1号操作,都新建一个结点
并且挂到它之前的最后一个1号操作对应的节点下
我们考虑对于第$i$棵树的某个结点$j$
在最终形态中,其一定是在对在$i$树有效最后一个$1$号操作指定的点下面
所以我们对于一个$1$号操作的结点,若其生效了,那么将其整个子树全部移到指定结点
若其失效了,我们将其整个子树移到它之前的最晚一个$1$号操作对应的节点下
这样显然就可以回答询问了,搞几次$access$操作即可
于是问题变成如何动态维护一棵树,要求移动子树、询问根到某个点的路径上权值和
这个显然可以无脑$LCT$,于是我们就在$O(n \log n)$的时间复杂度内解决这个问题啦!
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 300009; int n,m,num[N],l[N],r[N],last[N],to[N],ans[N],id[N]; vector<int> ins[N],del[N],q[N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } class Link_Cut_Tree{ struct Node{int val,sum,fa,ch[2];}p[N]; int cnt; public: inline int NewNode(int v) { p[cnt+1].sum = p[cnt+1].val = v; return ++cnt; } inline void modify(int w, int t) { cut(num[w]); if (t == 1) link(num[w], id[to[w]]); else link(num[w], last[w]); } inline int query(int x) { int u = id[l[N-x]], v = id[r[N-x]], ret; access(u); splay(u); ret = p[u].sum; x = access(v); splay(v); ret += p[v].sum; access(x); splay(x); ret -= p[x].sum << 1; return abs(ret); } inline void link(int a, int b) { splay(a); p[a].fa = b; } inline void cut(int x) { access(x); splay(x); p[x].ch[0] = p[p[x].ch[0]].fa = 0; maintain(x); } private: inline void maintain(int w) { p[w].sum = p[w].val + p[p[w].ch[0]].sum + p[p[w].ch[1]].sum; } inline bool IsRoot(int w) { return !p[w].fa || (p[p[w].fa].ch[0] != w && p[p[w].fa].ch[1] != w); } inline void rotate(int x) { int y=p[x].fa,z=p[y].fa,t=p[y].ch[1]==x; if (!IsRoot(y)) p[z].ch[p[z].ch[1]==y] = x; p[y].ch[t] = p[x].ch[t^1]; p[p[x].ch[t^1]].fa = y; p[x].ch[t^1] = y; p[x].fa = z; p[y].fa = x; maintain(y); maintain(x); } inline void splay(int x) { for (int f,ff;!IsRoot(x);) { f = p[x].fa; ff = p[f].fa; if (IsRoot(f)) rotate(x); else { if ((p[ff].ch[0]==f)^(p[f].ch[0]==x)) rotate(x),rotate(x); else rotate(f),rotate(x); } } } inline int access(int x) { for (int last=0;;last=x,x=p[x].fa) if (x) splay(x), p[x].ch[1] = last, maintain(x); else return last; } }lct; int main() { n = read(); m = read(); int pre = lct.NewNode(0); id[1] = lct.NewNode(1); lct.link(pre, id[1]); l[1] = 1; r[1] = n; for (int i=1,opt,ll,rr,x,tot=1;i<=m;i++) { if (!(opt=read())) { id[++tot] = lct.NewNode(1); l[tot] = read(); r[tot] = read(); lct.link(id[tot], pre); } else if (opt == 1) { ll = read(); rr = read(); to[i] = x = read(); ll = max(ll, l[x]); rr = min(rr, r[x]); if (ll <= rr) { ins[ll].push_back(i), del[rr].push_back(i); num[i] = lct.NewNode(0); lct.link(num[i], pre); last[i] = pre; pre = num[i]; } } else { x = read(); l[N-i] = read(); r[N-i] = read(); q[x].push_back(i); } } memset(ans,-1,sizeof(ans)); for (int i=1;i<=n;i++) { for (int j=ins[i].size()-1;~j;j--) lct.modify(ins[i][j], 1); for (int j=q[i].size()-1;~j;j--) ans[q[i][j]] = lct.query(q[i][j]); for (int j=del[i].size()-1;~j;j--) lct.modify(del[i][j], -1); } for (int i=1;i<=m;i++) (~ans[i])? printf("%d\n",ans[i]),1: 0; return 0; }
709387 48520A person essentially assist to make seriously articles I would state. This really is the very first time I frequented your site page and thus far? I surprised with the research you produced to make this specific publish incredible. Fantastic job! 18619
5964 255589If you are nonetheless on the fence: grab your favorite earphones, head down to a Best Buy and ask to plug them into a Zune then an iPod and see which one sounds much better to you, and which interface makes you smile a lot more. Then you will know which is proper for you. 586247
762110 496497I genuinely prize your function , Fantastic post. 995820
660301 182516Ive applied the valuable points from this page and I can certainly tell that it gives lots of assistance with my present jobs. I would be extremely pleased to keep getting back in this web page. Thank you. 56199
830870 493174Straight to the point and well written! Why cant everybody else be like this? 645459
265954 875873Rattling clean internet internet site , thanks for this post. 896387
890209 431493Quite interesting subject , appreciate it for putting up. 490059
438314 875725I adore reading and I conceive this website got some genuinely utilitarian stuff on it! . 62219
82393 915240I basically could not go away your website prior to suggesting that I actually enjoyed the normal details an individual supply to your visitors? Is gonna be again continuously to be able to check out new posts 60099
992961 829815I undoubtedly did not realize that. Learnt something new today! Thanks for that. 288625
316486 567791I dugg some of you post as I thought they were extremely helpful handy 168479
I am often to blogging and i really appreciate your content. The article has really peaks my interest. I am going to bookmark your site and keep checking for new information.
Hi there, just became aware of your blog through Google, and found that it is truly informative. I am going to watch out for brussels. I will appreciate if you continue this in future. Many people will be benefited from your writing. Cheers!