本文共 8685 字，大约阅读时间需要 28 分钟。
第一行有三个整数N、M和R，分别表示树的节点数、指令和询问总数，以及X国的据点。
接下来N-1行，每行两个整数X和Y，表示Katharon国的一条道路。
接下来M行，每行描述一个指令或询问，格式见题目描述。
对于每个询问操作，输出所求的值。
1<=N,M<=50000.且对于运送操作1<=W<=1000
链修改、查询链上点权和、查询链上最大最小点权，这些操作直接用树链剖分+线段树就能解决。
重点是链翻转，这显然不能用线段树这种静态数据结构，所以将线段树维护$dfs$序换成平衡树动态维护$dfs$序。
对于链翻转操作，我们将每一段重链在$dfs$序上的区间都从$treap$中断裂出来，然后将这些重链断裂出来的$treap$再合并到一起，将根节点打上翻转标记，然后再将这些重链合并成的$treap$断裂开分别插入回原来$dfs$序上的位置即可。
因为树链剖分是从下往上找重链，在$dfs$序上就是从后往前找区间，所以合并和分裂还原时都要倒着操作(也就是从$dfs$序上靠前的区间开始操作)，这样才能保证每次找$dfs$序上对应位置是正确的。
注意在链修改打标记时要立即下传一层，否则查询时可能会有查询点仍有标记未下传的情况。
#include #include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;ll z;ll ans;int x,y;int n,m;int cnt;int tot;int res;int rot;int miku;int root;int a,b,c,e;char ch[20];int s[50010];int t[50010];int L[50010];int R[50010];int r[50010];int f[50010];int d[50010];ll mn[50010];ll mx[50010];ll sum[50010];ll num[50010];int ls[50010];int rs[50010];int son[50010];int top[50010];int siz[50010];int rev[50010];int val[50010];int to[100010];int size[50010];int head[50010];int next[100010];ll INF=1ll<<60;void add(int x,int y){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y;}void dfs(int x){ d[x]=d[f[x]]+1; siz[x]=1; for(int i=head[x];i;i=next[i]) { if(to[i]!=f[x]) { f[to[i]]=x; dfs(to[i]); siz[x]+=siz[to[i]]; if(siz[to[i]]>siz[son[x]]) { son[x]=to[i]; } } }}void dfs2(int x,int tp){ top[x]=tp; s[x]=++res; if(son[x]) { dfs2(son[x],tp); } for(int i=head[x];i;i=next[i]) { if(to[i]!=f[x]&&to[i]!=son[x]) { dfs2(to[i],to[i]); } }}int build(){ int rt=++cnt; size[rt]=1; mn[rt]=INF; r[rt]=rand(); return rt;}void pushup(int rt){ size[rt]=size[ls[rt]]+size[rs[rt]]+1; mn[rt]=val[rt]; mx[rt]=val[rt]; sum[rt]=val[rt]; if(ls[rt]) { mx[rt]=max(mx[rt],mx[ls[rt]]); mn[rt]=min(mn[rt],mn[ls[rt]]); sum[rt]+=sum[ls[rt]]; } if(rs[rt]) { mx[rt]=max(mx[rt],mx[rs[rt]]); mn[rt]=min(mn[rt],mn[rs[rt]]); sum[rt]+=sum[rs[rt]]; }}void pushdown(int rt){ if(num[rt]) { num[ls[rt]]+=num[rt]; num[rs[rt]]+=num[rt]; sum[ls[rt]]+=size[ls[rt]]*num[rt]; sum[rs[rt]]+=size[rs[rt]]*num[rt]; mn[ls[rt]]+=num[rt]; mn[rs[rt]]+=num[rt]; mx[ls[rt]]+=num[rt]; mx[rs[rt]]+=num[rt]; val[ls[rt]]+=num[rt]; val[rs[rt]]+=num[rt]; num[rt]=0; } if(rev[rt]) { rev[ls[rt]]^=1; rev[rs[rt]]^=1; rev[rt]^=1; swap(ls[rt],rs[rt]); }}int merge(int x,int y){ pushdown(x); pushdown(y); if(!x||!y) { return x+y; } if(r[x] =k) { y=rt; split(ls[rt],x,ls[y],k); pushup(rt); } else { x=rt; split(rs[rt],rs[x],y,k-size[ls[rt]]-1); pushup(rt); }}void change(int x,int y,ll z){ while(top[x]!=top[y]) { if(d[top[x]] d[y]) { swap(x,y); } split(root,a,b,s[y]); split(a,a,c,s[x]-1); num[c]+=z; sum[c]+=size[c]*z; mn[c]+=z; mx[c]+=z; val[c]+=z; root=merge(merge(a,c),b);}void rotate(int x,int y){ res=0; while(top[x]!=top[y]) { if(d[top[x]] d[y]) { swap(x,y); } split(root,a,b,s[y]); split(a,a,c,s[x]-1); t[++res]=c; L[res]=s[x]; R[res]=s[y]; root=merge(a,b); for(int i=res;i>=1;i--) { miku=merge(miku,t[i]); } rev[miku]^=1; for(int i=res;i>=1;i--) { split(miku,a,b,R[i]-L[i]+1); miku=b; split(root,c,e,L[i]-1); root=merge(merge(c,a),e); }}ll query_max(int x,int y){ ans=0; while(top[x]!=top[y]) { if(d[top[x]] d[y]) { swap(x,y); } split(root,a,b,s[y]); split(a,a,c,s[x]-1); ans=max(ans,mx[c]); root=merge(merge(a,c),b); return ans;}ll query_min(int x,int y){ ans=INF; while(top[x]!=top[y]) { if(d[top[x]] d[y]) { swap(x,y); } split(root,a,b,s[y]); split(a,a,c,s[x]-1); ans=min(ans,mn[c]); root=merge(merge(a,c),b); return ans;}ll query_sum(int x,int y){ ans=0; while(top[x]!=top[y]) { if(d[top[x]] d[y]) { swap(x,y); } split(root,a,b,s[y]); split(a,a,c,s[x]-1); ans+=sum[c]; root=merge(merge(a,c),b); return ans;}int main(){ scanf("%d%d%d",&n,&m,&rot); for(int i=1;i
做法与之前的类似，我们将路径看成两条从上往下的直链(即分成$lca->x$与$lca->y$两部分)，可以肯定一条链的$dfs$序一定在另一条链的$dfs$序之前，那么为了确保在取出第一条链时不影响第二条链的$dfs$序，我们先对整条链$dfs$序较大的一条链进行操作再取出另一条链。这里有一点需要注意的就是$lca$所在重链的分配：如果操作链不是直链，那么$lca$所在重链分配给dfs序较小的一条链；否则分配给$dfs$序较大的一条链。这样我们就得到了树上两个开头相连的序列，显然是无法直接将两个序列连到一起就翻转的。我们将一个序列先翻转再接在另一个序列的前面，然后将整个序列一起翻转，将翻转后的序列拆分成原来的两部分并将第一部分翻转回来，最后分别插入回原$treap$，同样为了保证第二个插入的链的$dfs$序是对的，要先插入$dfs$序较小的链。
#include #include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;int r[50010];int ls[50010];int rs[50010];ll sum[50010];int val[50010];int num[50010];int mx[50010];int mn[50010];int rev[50010];int size[50010];int sz[50010];int son[50010];int top[50010];int dep[50010];int f[50010];int s[50010];int dfn;int l1[50010];int len1[50010];int l2[50010];int len2[50010];int s1,s2;int n,m;char ch[10];int cnt;int tot;int head[50010];int nex[100010];int to[100010];int q[100010];int x,y,z;int root;void add_edge(int x,int y){ tot++; nex[tot]=head[x]; head[x]=tot; to[tot]=y;}void dfs(int x){ size[x]=1; for(int i=head[x];i;i=nex[i]) { if(to[i]!=f[x]) { f[to[i]]=x; dep[to[i]]=dep[x]+1; dfs(to[i]); size[x]+=size[to[i]]; if(size[to[i]]>size[son[x]]) { son[x]=to[i]; } } }}void dfs2(int x,int tp){ top[x]=tp; s[x]=++dfn; q[dfn]=x; if(son[x]) { dfs2(son[x],tp); } for(int i=head[x];i;i=nex[i]) { if(to[i]!=f[x]&&to[i]!=son[x]) { dfs2(to[i],to[i]); } }}int newnode(int x){ int rt=++cnt; val[rt]=x; r[rt]=rand(); size[rt]=1; mx[rt]=mn[rt]=x; sum[rt]=1ll*x; return rt;}void pushup(int rt){ size[rt]=1; mx[rt]=mn[rt]=val[rt]; sum[rt]=1ll*val[rt]; if(ls[rt]) { sum[rt]+=sum[ls[rt]]; mx[rt]=max(mx[rt],mx[ls[rt]]); mn[rt]=min(mn[rt],mn[ls[rt]]); size[rt]+=size[ls[rt]]; } if(rs[rt]) { sum[rt]+=sum[rs[rt]]; mx[rt]=max(mx[rt],mx[rs[rt]]); mn[rt]=min(mn[rt],mn[rs[rt]]); size[rt]+=size[rs[rt]]; }}void flip(int rt){ rev[rt]^=1; swap(ls[rt],rs[rt]);}void add(int rt,int value){ num[rt]+=value; sum[rt]+=1ll*size[rt]*value; mx[rt]+=value; mn[rt]+=value; val[rt]+=value;}void pushdown(int rt){ if(rev[rt]) { rev[rt]=0; flip(ls[rt]); flip(rs[rt]); } if(num[rt]) { add(ls[rt],num[rt]); add(rs[rt],num[rt]); num[rt]=0; }}int merge(int x,int y){ if(!x||!y) { return x+y; } pushdown(x); pushdown(y); if(r[x] =k) { y=rt; split(ls[rt],x,ls[y],k); pushup(rt); } else { x=rt; split(rs[rt],rs[x],y,k-size[ls[rt]]-1); pushup(rt); }}void change(int x,int y,int value){ int a=0,b=0,c=0; while(top[x]!=top[y]) { if(dep[top[x]] dep[y]) { swap(x,y); } split(root,a,c,s[y]); split(a,a,b,s[x]-1); add(b,value); root=merge(merge(a,b),c);}ll query_sum(int x,int y){ int a=0,b=0,c=0; ll res=0ll; while(top[x]!=top[y]) { if(dep[top[x]] dep[y]) { swap(x,y); } split(root,a,c,s[y]); split(a,a,b,s[x]-1); res+=sum[b]; root=merge(merge(a,b),c); return res;}int query_max(int x,int y){ int a=0,b=0,c=0; int res=0; while(top[x]!=top[y]) { if(dep[top[x]] dep[y]) { swap(x,y); } split(root,a,c,s[y]); split(a,a,b,s[x]-1); res=max(res,mx[b]); root=merge(merge(a,b),c); return res;}int query_min(int x,int y){ int a=0,b=0,c=0; int res=2147483647; while(top[x]!=top[y]) { if(dep[top[x]] dep[y]) { swap(x,y); } split(root,a,c,s[y]); split(a,a,b,s[x]-1); res=min(res,mn[b]); root=merge(merge(a,b),c); return res;}void turn_round(int x,int y){ int a=0,b=0,c=0,d=0; s1=s2=0; int fx=x,fy=y; while(top[x]!=top[y]) { if(dep[top[x]]>dep[top[y]]) { l1[++s1]=s[top[x]]; len1[s1]=s[x]; x=f[top[x]]; } else { l2[++s2]=s[top[y]]; len2[s2]=s[y]; y=f[top[y]]; } } if(dep[x]>dep[y]) { swap(x,y); } if((s[fx] s[fy]&&fy==x)) { l1[++s1]=s[x]; len1[s1]=s[y]; } else if((s[fx] s[fy]&&fy!=x)) { l2[++s2]=s[x]; len2[s2]=s[y]; } int rot1=0; int rot2=0; int leng=0; if(s[fx] =1;i--) { split(rot1,a,b,len1[i]-l1[i]+1); rot1=b; split(root,c,d,l1[i]-1); root=merge(merge(c,a),d); } for(int i=s2;i>=1;i--) { split(rot2,a,b,len2[i]-l2[i]+1); rot2=b; split(root,c,d,l2[i]-1); root=merge(merge(c,a),d); } } else { for(int i=1;i<=s1;i++) { split(root,a,c,len1[i]); split(a,a,b,l1[i]-1); root=merge(a,c); rot1=merge(b,rot1); } for(int i=1;i<=s2;i++) { split(root,a,c,len2[i]); split(a,a,b,l2[i]-1); root=merge(a,c); rot2=merge(b,rot2); leng+=len2[i]-l2[i]+1; } flip(rot2); rot2=merge(rot2,rot1); flip(rot2); split(rot2,a,b,leng); flip(a); rot2=a,rot1=b; for(int i=s2;i>=1;i--) { split(rot2,a,b,len2[i]-l2[i]+1); rot2=b; split(root,c,d,l2[i]-1); root=merge(merge(c,a),d); } for(int i=s1;i>=1;i--) { split(rot1,a,b,len1[i]-l1[i]+1); rot1=b; split(root,c,d,l1[i]-1); root=merge(merge(c,a),d); } }}int main(){ srand(12378); scanf("%d%d",&n,&m); for(int i=1;i
转载于:https://www.cnblogs.com/Khada-Jhin/p/9985945.html
