没有原题链接

题目描述

题解

如果仅仅是动态维护最小生成树的话，那根本没法在线做。但是这题不一样，突破口就在“网格图”上。

原图是每条边连接两个格点，求格点的最小生成树。假设连接格点的不是一棵树，那么一定出现了>1个格点连通块。我们发现每个格点连通块都是被一圈的正方形空白格子（或者边界）包围，而原本断开这一圈格子和边界的那些边一定不是被选的边。如果我们把每个格子也看成一个节点（特别地，四面的边界全部看成一个节点），规定未选的边连接相邻两个格子节点，那么格子节点一定会形成环。

（注：红色是选择的边，蓝色点是格子节点）

再反过来考虑，若格子节点形成了环，那么中间一定有格点被围住，与外界割开，这也就不合法。

所以我们证明，一个连通的格点生成图对应一个格子节点的生成森林，于是一个格点生成树对应一个格子的生成树，一个格点最小生成树就对应着一个格子的最大生成树。（听起来和最大流-最小割一类的问题好像，不会是个线规吧）

于是我们把原问题转化为了一个最大生成树问题😊…可是这不还是一样的不可做吗？

注意到每条边要么在最小生成树中，要么在最大生成树中。在最小生成树问题中，若我们动态修改的边权只会变小，不论修改的边是否在原来的最小生成树上，都是可以用LCT维护的。具体而言只需要挑出路径上的最长边，比较一下，然后插入更优的边即可。类似地，在最大生成树问题中，条件变为了边权只能变大。

把两者结合在一起，不就可以应对所有情况了？

你只需要分类讨论边权是增大还是减小，假设是减小并且不在最小生成树上，那么找最小生成树路径上的最长边，把那条最长边挪到最大生成树上，再把当前修改的边从最大生成树挪到最小生成树上。反过来的情况类似处理。

在线算法，总复杂度 O(nlog⁡n)O(n\log n)O(nlogn)。

代码

#include<bits/stdc++.h>//JZM yyds!!#define ll long long#define uns unsigned#define END putchar('\n')#define fi first#define se second#define IF (it->fi)#define IS (it->se)#define lowbit(x) ((x)&-(x))using namespace std;const int MAXN=800005;inline ll read(){ll x=0;bool f=1;char s=getchar();while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();return f?x:-x;}int ptf[50],lpt;inline void print(ll x,char c='\n'){if(x<0)putchar('-'),x=-x;ptf[lpt=1]=x%10;while(x>9)x/=10,ptf[++lpt]=x%10;while(lpt)putchar(ptf[lpt--]^48);if(c>0)putchar(c);}#define pii pair<int,int>int R,C,A,B,n,m,k;pii ea[MAXN],eb[MAXN];ll val[MAXN],sum;bool on[MAXN];const ll MX=2e9;inline void decode(char ch, int &x, int &y, int &w, ll lstans) {static int mask = 0xfffff;w = (int) ((w ^ lstans) & mask);if(ch == '-') x = (x + lstans - 1) % R + 1, y = (y + lstans - 1) % (C - 1) + 1;if(ch == '|') x = (x + lstans - 1) % (R - 1) + 1, y = (y + lstans - 1) % C + 1;}//LCT beginstruct itn{int x;ll y;itn(){}itn(int X,ll Y){x=X,y=Y;}inline bool operator<(const itn&b)const{if(y^b.y)return y<b.y;else return x<b.x;}};struct spl{int fa,h[2];itn a,s;bool lz;spl(){}spl(int X,ll Y){fa=h[0]=h[1]=0,a=s=itn(X,Y),lz=0;}}t[MAXN];inline void cover(int x){if(!x)return;t[x].lz^=1,swap(t[x].h[0],t[x].h[1]);}inline void pushd(int x){if(t[x].lz)cover(t[x].h[0]),cover(t[x].h[1]),t[x].lz=0;}inline void update(int x){t[x].s=max(t[x].a,max(t[t[x].h[0]].s,t[t[x].h[1]].s));}inline bool sd(int x){return x==t[t[x].fa].h[1];}inline bool isroot(int x){return x!=t[t[x].fa].h[sd(x)];}inline void lin(int x,int y,bool f){if(x)t[x].h[f]=y;if(y)t[y].fa=x;}inline void rott(int x){if(!t[x].fa||isroot(x))return;bool f1=sd(x),f2=sd(t[x].fa);int fa=t[x].fa,ff=t[fa].fa,sn=t[x].h[f1^1];if(isroot(fa))t[x].fa=ff;else lin(ff,x,f2);lin(fa,sn,f1),lin(x,fa,f1^1);update(fa),update(x),update(ff);}inline void pushtag(int x){if(!isroot(x))pushtag(t[x].fa);pushd(x);}inline void splay(int x){pushtag(x);while(!isroot(x)){if(!isroot(t[x].fa)){if(sd(x)==sd(t[x].fa))rott(t[x].fa);else rott(x);}rott(x);}}inline void access(int x){for(int y=0;x;y=x,x=t[x].fa)splay(x),t[x].h[1]=y,update(x);}inline void makeroot(int x){access(x),splay(x),cover(x);}inline void LINK(int x,int y){if(x==y)return;makeroot(x),access(y),splay(y);if(t[x].fa==0)lin(y,x,1),update(y);}inline void CUT(int x,int y){makeroot(x),access(x),splay(y);if(!t[y].h[0]&&t[y].fa==x)t[y].fa=0;}inline int query(int x,int y){makeroot(x),access(y),splay(x);return t[x].s.x;}//LCT endint Q;bool O;inline int eid(char ch,int x,int y){if(ch=='-')return (x-1)*(C-1)+y;else return R*(C-1)+(x-1)*C+y;}inline int aid(int x,int y){return (x-1)*C+y;}inline int bid(int x,int y){if(x<1||x>=R||y<1||y>=C)return 1;return (x-1)*(C-1)+y+1;}inline void dele(int i){if(on[i])CUT(A+B+i,ea[i].fi),CUT(A+B+i,ea[i].se),sum-=val[i];else CUT(A+B+i,eb[i].fi),CUT(A+B+i,eb[i].se);}inline void adde(int i){if(on[i]){t[A+B+i]=spl(i,val[i]);LINK(A+B+i,ea[i].fi);LINK(A+B+i,ea[i].se),sum+=val[i];}else{t[A+B+i]=spl(i,MX-val[i]);LINK(A+B+i,eb[i].fi);LINK(A+B+i,eb[i].se);}}int main(){freopen("channel.in","r",stdin);freopen("channel.out","w",stdout);O=read();R=read(),C=read(),Q=read();A=R*C,B=(R-1)*(C-1)+1,m=R*C*2-C-R,n=A+B+m;for(int i=1;i<=R;i++)for(int j=1;j<C;j++){int x=eid('-',i,j);ea[x]=pii(aid(i,j),aid(i,j+1));eb[x]=pii(A+bid(i-1,j),A+bid(i,j));on[x]=1;}for(int i=1;i<R;i++)for(int j=1;j<=C;j++){int x=eid('|',i,j);ea[x]=pii(aid(i,j),aid(i+1,j));eb[x]=pii(A+bid(i,j-1),A+bid(i,j));if(j==1)on[x]=1;}for(int i=1;i<=A+B;i++)t[i]=spl(0,0);for(int i=1;i<=m;i++)adde(i);while(Q--){char ch=getchar();while(ch!='-'&&ch!='|')ch=getchar();int x=read(),y=read(),w=read();if(O)decode(ch,x,y,w,sum);int i=eid(ch,x,y);if(w^val[i]){if(w<val[i]&&!on[i]){int u=ea[i].fi,v=ea[i].se,j=query(u,v);val[i]=w;if(val[j]>val[i]){dele(i),dele(j);on[i]=1,on[j]=0;adde(i),adde(j);}else splay(A+B+i),t[A+B+i].a=itn(i,MX-val[i]),update(A+B+i);}else if(w>val[i]&&on[i]){int u=eb[i].fi,v=eb[i].se,j=query(u,v);sum-=val[i],val[i]=w,sum+=val[i];if(val[j]<val[i]){dele(i),dele(j);on[i]=0,on[j]=1;adde(i),adde(j);}else splay(A+B+i),t[A+B+i].a=itn(i,val[i]),update(A+B+i);}else{if(on[i])sum-=val[i];val[i]=w;if(on[i])sum+=val[i];splay(A+B+i);if(on[i])t[A+B+i].a=itn(i,val[i]);else t[A+B+i].a=itn(i,MX-val[i]);update(A+B+i);}}print(sum);}return 0;}