这里没有水表
这几天连树剖和LCT都不会写了
所以放下总结两篇
LCT是一个通过链剖分和Splay的使用,在无根树上维护路径信息的有效算法
其单次操作时间复杂度为O(logn),常数巨大
Splay
需要先学Splay(不会的我可不管),于是跳过Splay部分;
主要结构和思路
讲的就交给书予大佬了
这里是一些无关紧要的压行
il void access(int x){for(RG int y=0;x;y=x,x=fa[x])splay(x),s[1][x]=y,update(x);}
il int findroot(int x){access(x);splay(x);while(s[0][x])x=s[0][x];return x;}
il void makeroot(int x){access(x);splay(x);reverse(x);}
il void link(int x,int y){makeroot(x);fa[x]=y;}
il void split(int x,int y){makeroot(x);access(y);splay(y);}
il void cut(int x,int y){split(x,y);fa[x]=s[0][y]=0;}
注意一个Splay的reverse(区间翻转)操作
节点上有懒标记的时候这个节点是不是已经被修改过了?
是吧所以我们需要一个reverse的函数再pushdown
il void reverse(int i){if(!i)return;swap(s[0][i],s[1][i]);rv[i]^=1;}
il void pushdown(int i){
if(rv[i]){reverse(s[0][i]);reverse(s[1][i]);rv[i]=0;}
}
[luoguP3690] 【模板】Link Cut Tree （动态树）
注意：
split请务必保证两个点联通
cut请务必保证两个点直接相连
link请务必保证两个点不联通
不然出现玄学错误谁都救不了你了
--摘自书予大佬
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define RG register
using namespace std;
const int N=300010;
int Orz,n,m,x,y;
int s[2][N],fa[N],sum[N],val[N],rv[N];
int cal[N],top;
inline void update(int i){
sum[i]=sum[s[0][i]]^sum[s[1][i]]^val[i];}
inline void pushdown(int i){if(!rv[i])return;rv[i]^=1;rv[s[0][i]]^=1;rv[s[1][i]]^=1;swap(s[1][i],s[0][i]);}
inline bool isroot(int i){
return s[0][fa[i]]!=i&&s[1][fa[i]]!=i;}
inline bool isr(int i){return s[1][fa[i]]==i;}
inline void rot(int i){
RG int j=fa[i],k=fa[j];
RG bool b=isr(i);
fa[i]=k;
if(!isroot(j))s[isr(j)][k]=i;
s[b][j]=s[!b][i];
if(s[!b][i])fa[s[!b][i]]=j;
s[!b][i]=j;fa[j]=i;
update(j);
}
inline void splay(int i){
cal[++top]=i;
for(RG int x=i;!isroot(x);x=fa[x])cal[++top]=fa[x];//
while(top)pushdown(cal[top--]);//
for(RG int j=fa[i];!isroot(i);rot(i),j=fa[i])
if(!isroot(j))isr(i)^isr(j)?rot(i):rot(j);
update(i);
}
inline void access(int x){for(RG int y=0;x;y=x,x=fa[x])splay(x),s[1][x]=y,update(x);}
inline void makeroot(int x){access(x);splay(x);rv[x]^=1;}
inline int findroot(int x){access(x);splay(x);while(s[0][x])x=s[0][x];return x;}
inline void split(int x,int y){makeroot(x);access(y);splay(y);}//
inline void cut(int x,int y){split(x,y);fa[x]=s[0][y]=0;}//
inline void link(int x,int y){makeroot(x);fa[x]=y;}
inline void print(int i){
if(s[0][i])print(s[0][i]);
printf("%d ",val[i]);
if(s[1][i])print(s[1][i]);
}
int main()
{
scanf("%d%d",&n,&m);
for(RG int i=1;i<=n;i++)scanf("%d",&val[i]);
while(m--){
scanf("%d%d%d",&Orz,&x,&y);
if(!Orz){split(x,y);printf("%d
",sum[y]);}
if(Orz==1)if(findroot(x)!=findroot(y))link(x,y);//
if(Orz==2)if(findroot(x)==findroot(y))cut(x,y);
if(Orz==3){access(x);splay(x);val[x]=y;update(x);}
}
return 0;
}
[luoguP1501] [国家集训队]Tree II
这里是带修改的LCT
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
#define isr(i) (s[1][fa[i]]==i)
#define isroot(i) (s[0][fa[i]]!=i&&s[1][fa[i]]!=i)
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=51061;
const int N=100010;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
il void file(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
ll n,q;char c;
ll fa[N],s[2][N],sz[N],val[N],rv[N],sum[N],add[N],times[N],cal[N],top;
il void update(int i){
sum[i]=(sum[s[0][i]]+sum[s[1][i]]+val[i])%mod;
sz[i]=sz[s[0][i]]+sz[s[1][i]]+1;
}
il void reverse(int i){
if(!i)return;swap(s[0][i],s[1][i]);rv[i]^=1;
}
il void modify(int i,int t,int a){
sum[i]=(sum[i]*t+a*sz[i])%mod;
val[i]=(val[i]*t+a)%mod;
times[i]=times[i]*t%mod;
add[i]=(add[i]*t+a)%mod;
}
il void pushdown(int i){
if(rv[i]){reverse(s[0][i]);reverse(s[1][i]);rv[i]=0;}
if(add[i]||times[i]!=1){
if(s[0][i])modify(s[0][i],times[i],add[i]);
if(s[1][i])modify(s[1][i],times[i],add[i]);
add[i]=0;times[i]=1;
}
}
il void rot(int i){
RG int j=fa[i],k=fa[j];
RG bool b=isr(i);
if(!isroot(j))s[isr(j)][k]=i;fa[i]=k;
if(s[!b][i])fa[s[!b][i]]=j;s[b][j]=s[!b][i];
s[!b][i]=j;fa[j]=i;
update(j);
}
il void splay(int i){
cal[++top]=i;
for(RG int x=i;!isroot(x);x=fa[x])cal[++top]=fa[x];
while(top)pushdown(cal[top--]);
for(RG int j=fa[i];!isroot(i);rot(i),j=fa[i])
if(!isroot(j))(isr(i)^isr(j))?rot(i):rot(j);
update(i);
}
il void access(int x){for(RG int y=0;x;y=x,x=fa[x])splay(x),s[1][x]=y,update(x);}
il int findroot(int x){access(x);splay(x);while(s[0][x])x=s[0][x];return x;}
il void makeroot(int x){access(x);splay(x);reverse(x);}
il void link(int x,int y){makeroot(x);fa[x]=y;}
il void split(int x,int y){makeroot(x);access(y);splay(y);}
il void cut(int x,int y){split(x,y);fa[x]=s[0][y]=0;}
il void modify_add(){
RG int u=read(),v=read(),c=read()%mod;
split(u,v);modify(v,1,c);
}
il void update_line(){
RG int u1=read(),v1=read(),u2=read(),v2=read();
cut(u1,v1);link(u2,v2);
}
il void modify_times(){
RG int u=read(),v=read(),c=read()%mod;
split(u,v);modify(v,c,0);
}
il void query(){
RG int u=read(),v=read();split(u,v);
printf("%lld
",sum[v]);
}
int main()
{
n=read();q=read();
for(RG int i=1;i<=n;i++)modify(i,1,1),sz[i]=1;
for(RG int i=1,u,v;i<n;i++){
u=read();v=read();link(u,v);
}
for(RG int i=1;i<=q;i++){
c=0;while(c!='+'&&c!='-'&&c!='*'&&c!='/')c=getchar();
if(c=='+')modify_add();
if(c=='-')update_line();
if(c=='*')modify_times();
if(c=='/')query();
}
return 0;
}
[luoguP4172] [WC2006]水管局长
其实离线+倒序处理询问就变成魔法森林(动态维护最小生成树)了
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
#define isr(i) (s[1][fa[i]]==i)
#define isroot(i) (s[0][fa[i]]!=i&&s[1][fa[i]]!=i)
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int N=100010;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
il void file(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int n,m,q,tot=1;
int fa[N<<1],s[2][N<<1],val[N<<1],rv[N<<1],mx[N<<1],pmx[N<<1];
il void update(int i){
mx[i]=val[i];pmx[i]=i;
if(s[0][i]&&mx[s[0][i]]>mx[i]){
mx[i]=mx[s[0][i]];pmx[i]=pmx[s[0][i]];
}
if(s[1][i]&&mx[s[1][i]]>mx[i]){
mx[i]=mx[s[1][i]];pmx[i]=pmx[s[1][i]];
}
}
il void reverse(int i){swap(s[0][i],s[1][i]);rv[i]^=1;}
il void pushdown(int i){
if(!rv[i])return;
reverse(s[0][i]);reverse(s[1][i]);
rv[i]=0;
}
il void rot(int i){
RG int j=fa[i],k=fa[j];
RG bool b=isr(i);
if(!isroot(j))s[isr(j)][k]=i;fa[i]=k;
if(s[!b][i])fa[s[!b][i]]=j;s[b][j]=s[!b][i];
s[!b][i]=j;fa[j]=i;
update(j);
}
int cal[N<<1],top;
il void splay(int i){
cal[++top]=i;
for(RG int x=i;!isroot(x);x=fa[x])cal[++top]=fa[x];
while(top)pushdown(cal[top--]);
for(RG int j=fa[i];!isroot(i);rot(i),j=fa[i])
if(!isroot(j))(isr(i)^isr(j))?rot(i):rot(j);
update(i);
}
int f[N<<1];
il void access(int x){for(RG int y=0;x;y=x,x=fa[x])splay(x),s[1][x]=y,update(x);}
il void makeroot(int x){access(x);splay(x);reverse(x);}
il int find(int x){return f[x]?f[x]=find(f[x]):x;}
il void split(int x,int y){makeroot(x);access(y);splay(y);}
il void link(int x,int y){
makeroot(x);fa[x]=y;
}
il void cut(int x,int y){
split(x,y);fa[x]=s[0][y]=0;
}
int l[N],r[N],cnt;
il int query(int u,int v){
split(u,v);
return pmx[v];
}
il void add(int u,int v,int w){
if(find(u)!=find(v)){
cnt++;val[n+cnt]=w;l[cnt]=u;r[cnt]=v;
link(u,n+cnt);link(n+cnt,v);
f[find(u)]=find(v);
}
else{
RG int i=query(u,v);
if(val[i]>w){
cut(i,l[i-n]);cut(i,r[i-n]);
l[i-n]=u;r[i-n]=v;val[i]=w;
link(u,i);link(i,v);
}
}
}
struct edge{
int u,v,t,id;
bool operator <(const edge b)const{
return (u==b.u)?v<b.v:u<b.u;
}
}E[N];
bool cmp(edge a,edge b){return a.id>b.id;}
struct qry{int u,v,ans;}Q[N];
int main()
{
n=read();m=read();q=read();
for(RG int i=1,x,y,w;i<=m;i++){
x=read();y=read();w=read();if(x>y)swap(x,y);
E[i]=(edge){x,y,w,0};
}
sort(E+1,E+m+1);
for(RG int i=1,k,x,y;i<=q;i++){
k=read();x=read();y=read();if(x>y)swap(x,y);
if(k==1)Q[++tot]=(qry){x,y,0};
if(k==2){
E[lower_bound(E+1,E+m+1,(edge){x,y,0,0})-E].id=tot;
}
}
for(RG int i=1;i<=m;i++)if(!E[i].id)E[i].id=tot;
sort(E+1,E+m+1,cmp);
for(RG int i=tot,l=1;i>=2;i--){
while(E[l].id==i&&l<=m){add(E[l].u,E[l].v,E[l].t);l++;}
Q[i].ans=val[query(Q[i].u,Q[i].v)];
}
for(RG int i=2;i<=tot;i++)printf("%d
",Q[i].ans);
return 0;
}