[ARC141E] Sliding Edge on Torus 题解

题目链接

点击打开链接

题目解法

比较套路的题
首先画个图，然后把 \(y-x\) 相同的变成一个点（使 \(y>x\)）
然后再两个点之间连有权边

那么问题就变成求新图的每个连通块中形成的原图的连通块数量
手玩几个数据发现，原图的连通块数量即为新图的所有环长的 \(\gcd\)，再和 \(n\) 的 \(\gcd\)
根据有向图所有环的 \(\gcd\) 的求法，不难得出无向图所有环的 \(\gcd\) 求法
即为找到所有的非树边，假设是 \(x,y\)，长度为 \(z\)，记 \(dis_u\) 为 \(u\) 到根的距离，则环长的 \(\gcd\{z-dis_x+dis_y\}\)

上面的式子可以用带权并查集维护

时间复杂度 \(O(n\log n)\)（不算并查集）

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=200100;
int n,m,fa[N],w[N],g[N];
LL ans;
int get_father(int x){
    if(x==fa[x]) return x;
    int ret=get_father(fa[x]);w[x]=(w[x]+w[fa[x]])%n;
    return fa[x]=ret;
}
void merge(int x,int y,int c){
    int fax=get_father(x),fay=get_father(y);
    if(fax==fay){
        ans-=g[fax];
        g[fax]=__gcd(g[fax],(w[x]-w[y]+c+n)%n);
        ans+=g[fax];return;
    }
    ans-=g[fax]+g[fay];
    g[fax]=__gcd(g[fax],g[fay]);
    ans+=g[fax];
    fa[fay]=fax,w[fay]=(c+w[x]-w[y]+n)%n;
}
int main(){
    n=read(),m=read();
    ans=1ll*n*n;
    F(i,0,n-1) fa[i]=i,g[i]=n;
    F(i,1,m){
        int a=read(),b=read(),c=read(),d=read();
        b=(b-a+n)%n,c=(c-a+n)%n,d=(d-a+n)%n;//let a=0
        if(c>d) d+=n;
        int x=b,y=d-c;
        merge(x,y,c);
        printf("%lld\n",ans);
    }
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}