LCT 填坑系列

首页 > 代码库 > LCT 填坑系列

2024-09-04 05:09:01 212人阅读

清华冬令营 T1用了LCT 这个东西以前有写过然而并不熟练发现没了板子根本就不会写只能填一填坑辣

BZOJ 2843 LCT

  1 #include <bits/stdc++.h>
  2 #define N 30010
  3 #define ls c[x][0]
  4 #define rs c[x][1]
  5 using namespace std;
  6 
  7 inline int read()
  8 {
  9     int x=0,f=1; char ch=getchar();
 10     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
 11     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
 12     return x*f;
 13 }
 14 int n,m,val[N];
 15 struct link_cut_tree
 16 {
 17     int c[N][2],fa[N],sum[N];
 18     bool rev[N];
 19     bool isroot(int x)
 20     {
 21         return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
 22     }
 23     void updata(int x)
 24     {
 25         if(!x) return ;
 26         sum[x]=sum[c[x][0]]+sum[c[x][1]]+val[x];
 27     }
 28     void reverse(int x)
 29     {
 30         if(!x) return ;
 31         rev[x]^=1;
 32         swap(c[x][0],c[x][1]);
 33     }
 34     void pushdown(int x)
 35     {
 36         if(rev[x])
 37         {
 38             reverse(c[x][0]);
 39             reverse(c[x][1]);
 40             rev[x]=0;
 41         }
 42     }
 43     void rotate(int x)
 44     {
 45         int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1;
 46         if(!isroot(y)) c[z][c[z][1]==y]=x;
 47         if(c[x][r]) fa[c[x][r]]=y;
 48         fa[y]=x;fa[x]=z;
 49         c[y][l]=c[x][r];c[x][r]=y;
 50         updata(y); updata(x);
 51     }
 52     void relax(int x)
 53     {
 54         if(!isroot(x)) relax(fa[x]);
 55         pushdown(x);
 56     }
 57     void splay(int x)
 58     {
 59         relax(x);
 60         while(!isroot(x))
 61         {
 62             int y=fa[x],z=fa[y];
 63             if(!isroot(y))
 64             {
 65                 if((c[y][0]==x)^(c[z][0]==y)) rotate(y);
 66                 else rotate(x);
 67             }
 68             rotate(x);
 69         }
 70     }
 71     void access(int x)
 72     {
 73         for(int p=0;x;p=x,x=fa[x])
 74         {
 75             splay(x); c[x][1]=p; if(p) fa[p]=x; updata(x);
 76         }
 77     }
 78     void makeroot(int x)
 79     {
 80         access(x); splay(x); 
 81         reverse(x);
 82     }
 83     void link(int x,int y)
 84     {
 85         makeroot(x); fa[x]=y;
 86     }
 87     int find(int x)
 88     {
 89         while(fa[x]) x=fa[x];
 90         return x;
 91     }
 92     int query(int x,int y)
 93     {
 94         makeroot(x); access(y); splay(y);
 95         return sum[y];
 96     }
 97 }T; 
 98 int main()
 99 {
100     //freopen("read.in","r",stdin);
101     //freopen("wro.out","w",stdout);
102     n=read();for(int i=1;i<=n;i++) val[i]=read();
103     m=read();while(m--)
104     {
105         char sd[100]; scanf("%s",sd);
106         int u=read(),v=read();
107         if(sd[0]==‘e‘)
108         {
109             if(T.find(u)==T.find(v))
110                 printf("%d\n",T.query(u,v));
111             else printf("impossible\n");
112         }
113         if(sd[0]==‘b‘)
114         {
115             if(T.find(u)==T.find(v))
116                 printf("no\n");
117             else T.link(u,v),printf("yes\n");
118         }
119         if(sd[0]==‘p‘)
120         {
121             val[u]=v; T.access(u);
122         }
123     }
124     return 0;
125 }

View Code

LCT？我是先用离线的树链剖分先A了这题发现LCT 实现起来比树剖更短而且稍快（但是你一个log（LCT）跟人家俩log（树剖）跑得差不多是不是不太好）

不在意。。QAQ

BZOJ 2843 树剖

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 inline int read()
  6 {
  7     int x=0,f=1;char ch=getchar();
  8     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
  9     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
 10     return x*f;
 11 }
 12 int st[30010],ee;
 13 struct edge
 14 {
 15     int u,v,next;
 16 }vs[60010];
 17 int vl[30010],Fa[30010],lastadd;
 18 struct que
 19 {
 20     int dps;
 21     int u,v,tp;
 22 }Q[100010];
 23 int getfa(int x){return (Fa[x]==x)? x: Fa[x]=getfa(Fa[x]);}
 24 inline void addedge(int u,int v)
 25 {
 26     vs[++ee].v=v;vs[ee].u=u;vs[ee].next=st[u];st[u]=ee;
 27 }
 28 int fa[30010],dep[30010],size[30010],son[30010],top[30010];
 29 int pl[30010],bl[30010],tree[30010<<2],n,m,vis[30010];
 30 void dfs1(int rt)
 31 {
 32     size[rt]=1; vis[rt]=1;
 33     for(int i=st[rt];i;i=vs[i].next)
 34     {
 35         if(fa[rt]==vs[i].v) continue;
 36         fa[vs[i].v]=rt;
 37         dep[vs[i].v]=dep[rt]+1;
 38         dfs1(vs[i].v);
 39         if(size[son[rt]]<size[vs[i].v])
 40             son[rt]=vs[i].v;
 41     }
 42 }
 43 void dfs2(int rt)
 44 {
 45     pl[rt]=++lastadd; bl[lastadd]=rt;
 46     vis[rt]=1;
 47     if(son[rt])
 48     {
 49         top[son[rt]]=top[rt];
 50         dfs2(son[rt]);
 51     }
 52     for(int i=st[rt];i;i=vs[i].next)
 53     {
 54         if(fa[rt]==vs[i].v||vs[i].v==son[rt]) continue;
 55         dfs2(vs[i].v);
 56     }
 57 }
 58 inline void updata(int rt)
 59 {
 60     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
 61 }
 62 void built(int l,int r,int rt)
 63 {
 64     if(l==r)
 65     {
 66         tree[rt]=vl[bl[l]];
 67         return ;
 68     }
 69     int mid=(l+r)>>1;
 70     built(l,mid,rt<<1); built(mid+1,r,rt<<1|1);
 71     updata(rt);
 72 }
 73 int query(int L,int R,int l,int r,int rt)
 74 {
 75     if(L<=l&&r<=R) return tree[rt];
 76     int mid=(l+r)>>1;
 77     if(mid>=R) return query(L,R,l,mid,rt<<1);
 78     if(mid<L) return query(L,R,mid+1,r,rt<<1|1);
 79     return query(L,R,l,mid,rt<<1)+query(L,R,mid+1,r,rt<<1|1);
 80 }
 81 void modify(int x,int y,int l,int r,int rt)
 82 {
 83     if(l==r)
 84     {
 85         tree[rt]=y;
 86         return ;
 87     }
 88     int mid=(l+r)>>1;
 89     if(mid>=x) modify(x,y,l,mid,rt<<1);
 90     else modify(x,y,mid+1,r,rt<<1|1);
 91     updata(rt);
 92 }
 93 inline int cal(int u,int v)
 94 {
 95     int ans=0;
 96     int f1=top[u],f2=top[v];
 97     if(dep[f1]>dep[f2]) swap(u,v),swap(f1,f2);
 98     while(f1!=f2)
 99     {
100         ans+=query(pl[f2],pl[v],1,n,1);
101         v=fa[f2]; f2=top[v];
102         if(dep[f1]>dep[f2]) swap(u,v),swap(f1,f2);
103     }
104     if(dep[u]>dep[v]) swap(u,v);
105     ans+=query(pl[u],pl[v],1,n,1);
106     return ans;
107 }
108 int main()
109 {
110     //freopen("read.in","r",stdin);
111     //freopen("wro.out","w",stdout);
112     n=read();
113     for(int i=1;i<=n;i++) vl[i]=read(),Fa[i]=i;
114     m=read();
115     for(int i=1;i<=m;i++)
116     {
117         char sd[1000];
118         scanf("%s",sd);
119         int u=read(),v=read();
120         if(sd[0]==‘e‘)
121         {
122             Q[i].dps=1; Q[i].tp=0;
123             if(getfa(u)!=getfa(v))
124                 Q[i].tp=1;
125         }
126         else if(sd[0]==‘b‘)
127         {
128             Q[i].dps=2;
129             int f1=getfa(u),f2=getfa(v);
130             if(f1!=f2)
131             {
132                 Q[i].tp=1;
133                 Fa[f1]=f2;
134                 addedge(u,v);addedge(v,u);
135             }
136         }
137         else Q[i].dps=3;
138         Q[i].u=u; Q[i].v=v;
139     }
140     for(int i=1;i<=n;i++) top[i]=i;
141     //dfs1(1); dfs2(1);
142     for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
143     memset(vis,0,sizeof vis);
144     for(int i=1;i<=n;i++) if(!vis[i]) dfs2(i);
145     built(1,n,1);
146     for(int i=1;i<=m;i++)
147     {
148         if(Q[i].dps==2)
149         {
150             if(Q[i].tp==1) printf("yes\n");
151             else printf("no\n");
152         }
153         else if(Q[i].dps==1)
154         {
155             if(Q[i].tp==1) printf("impossible\n");
156             else printf("%d\n",cal(Q[i].u,Q[i].v));
157         }
158         else if(Q[i].dps==3)
159             modify(pl[Q[i].u],Q[i].v,1,n,1);
160     }
161     return 0;
162 }

View Code

注意点：： LCT中 0号节点也会用于更新树的值要时刻维护其fa、c为0 否则就会爆掉！！感谢 Cicada

例：

1     void rotate(int x)
2     {
3         int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1;
4         if(!isroot(y)) c[z][c[z][1]==y]=x;
5         if(c[x][r])/*!!!*/ fa[c[x][r]]=y; /* EXCITING!!*/
6         fa[y]=x;fa[x]=z;
7         c[y][l]=c[x][r];c[x][r]=y;
8         updata(y); updata(x);
9     }

BZOJ 4025

  1 #include <bits/stdc++.h>
  2 #define ls c[x][0]
  3 #define rs c[x][1]
  4 #define inf 0x7fffffff
  5 using namespace std;
  6 
  7 inline int read()
  8 {
  9     int x=0,f=1; char ch=getchar();
 10     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
 11     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
 12     return x*f;
 13 }
 14 struct events
 15 {
 16     int u,v,start,end;
 17 }E[200010];
 18 struct Mt
 19 {
 20     int bl,tp;
 21 }Gs[400010];
 22 int sign[200010],tot;
 23 inline int timcatch(Mt a)
 24 {
 25     return (a.tp==1)? E[a.bl].start: E[a.bl].end;
 26 }
 27 inline bool cmp(const Mt a,const Mt b)
 28 {
 29     return timcatch(a)==timcatch(b)? a.tp<b.tp:timcatch(a)<timcatch(b);
 30 }
 31 int n,m,tt,mxx,val[400010];
 32 struct link_cut_tree
 33 {
 34     int mi[400010],sum[400010],vl[400010];
 35     int c[400010][2],fa[400010],rev[400010];
 36     inline bool isroot(int x)
 37     {
 38         return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
 39     }
 40     inline void updata(int x)
 41     {
 42         mi[x]=x; sum[x]=1;
 43         if(ls)
 44         {
 45             if(val[mi[x]]>val[mi[ls]]) mi[x]=mi[ls];
 46             sum[x]+=sum[ls];
 47         }
 48         if(rs)
 49         {
 50             if(val[mi[x]]>val[mi[rs]]) mi[x]=mi[rs];
 51             sum[x]+=sum[rs];
 52         }
 53     }
 54     void rever(int x)
 55     {
 56         if(!x) return ;
 57         rev[x]^=1; swap(ls,rs);
 58     }
 59     void pushdown(int x)
 60     {
 61         if(rev[x])
 62         {
 63             rever(ls); rever(rs);
 64             rev[x]^=1;
 65         }
 66     }
 67     void rotate(int x)
 68     {
 69         int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1;
 70         if(!isroot(y)) c[z][c[z][1]==y]=x;
 71         if(c[x][r]) fa[c[x][r]]=y;
 72         fa[y]=x; fa[x]=z;
 73         c[y][l]=c[x][r]; c[x][r]=y;
 74         updata(y); updata(x);
 75     }
 76     void relax(int x)
 77     {
 78         if(!isroot(x)) relax(fa[x]);
 79         pushdown(x);
 80     }
 81     void splay(int x)
 82     {
 83         relax(x);
 84         while(!isroot(x))
 85         {
 86             int y=fa[x],z=fa[y];
 87             if(!isroot(y))
 88             {
 89                 if((c[y][0]==x)^(c[z][0]==y)) rotate(y);
 90                 else rotate(x);
 91             }
 92             rotate(x);
 93         }
 94     }
 95     void access(int x)
 96     {
 97         for(int p=0;x;p=x,x=fa[x])
 98         {
 99             splay(x); c[x][1]=p; 
100             if(p) fa[p]=x;
101             updata(x);
102         }
103     }
104     void makeroot(int x)
105     {
106         access(x); splay(x); rever(x);
107     }
108     void link(int x,int y)
109     {
110         makeroot(x); fa[x]=y;
111     }
112     void cut(int x,int y)
113     {
114         makeroot(x); access(y);splay(y);
115         c[y][0]=fa[x]=0;
116     }
117 
118     int find(int x)
119     {
120         while(fa[x]) x=fa[x]; return x;
121     }
122     void insert(int x)
123     {
124         sign[x]=1; link(E[x].u,x+n); link(E[x].v,x+n);
125     }
126     void delet(int x)
127     {
128         sign[x]=0; cut(E[x].u,x+n); cut(E[x].v,x+n);
129     }
130     void flod(int x,int y,int t)
131     {
132         makeroot(x); access(y);splay(y);
133         if((sum[y]>>1)&1) delet(mi[y]-n),insert(t);
134         else 
135         {
136             int x=mi[y];
137             if(val[x]>val[t+n]) mxx=max(mxx,val[t+n]);
138             else mxx=max(mxx,val[x]),delet(mi[y]-n),insert(t);
139         }
140     }
141 }T;
142 
143 void doin(int x)
144 {
145     if(Gs[x].tp==-1&&sign[Gs[x].bl])
146         T.delet(Gs[x].bl);
147     if(Gs[x].tp==1&&!sign[Gs[x].bl])
148     {
149         if(T.find(E[Gs[x].bl].u)!=T.find(E[Gs[x].bl].v))
150             T.insert(Gs[x].bl);
151         else T.flod(E[Gs[x].bl].u,E[Gs[x].bl].v,Gs[x].bl);
152     }
153 }
154 int main()
155 {
156     //freopen("read.in","r",stdin);
157     //freopen("wro.out","w",stdout);
158     n=read();m=read();tt=read();
159     for(int i=1;i<=n;i++) val[i]=inf;
160     for(int i=1;i<=m;i++)
161     {
162         E[i].u=read();E[i].v=read();
163         E[i].start=read();
164         E[i].end=read();
165         Gs[++tot].bl=i; Gs[tot].tp=1;
166         Gs[++tot].bl=i; Gs[tot].tp=-1;
167         val[i+n]=E[i].end;
168     }
169     sort(Gs+1,Gs+1+tot,cmp);
170     /*  for(int i=1;i<=tot;i++)
171     {
172         printf("%d %d %d %d\n",E[Gs[i].bl].u,E[Gs[i].bl].v,Gs[i].tp,timcatch(Gs[i]));
173     }  */
174     for(int i=1,j=1;i<=tt;i++)
175     {
176         while(timcatch(Gs[j])<i&&j<=tot) doin(j),j++;
177         //printf("%d ",mxx);
178         if(mxx>=i) printf("No\n");
179         else printf("Yes\n");
180     }
181 }

View Code

感谢 GhostReach

发现当图中存在奇环时就不再是二分图那么在LCT上维护两个信息边消失的时间以及从一个点到另一个点的距离

每次按出现的时间顺序加入一条边

1、边的两个顶点在两颗不同的树中—— 直接link

2、边的两个顶点在同一颗树中

　　（i）加入后形成奇环—— 更新‘no’ 持续的时间并删去环上消失时间最早的边

　　（ii）加入后形成偶环—— 直接删去环上消失时间最早的边

ps：LCT的信息在边上新开点维护

View Code

LCT 填坑系列

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > LCT 填坑系列

LCT 填坑系列

看完仍有疑问？有类似问题直接问程序猿