题目链接
题目解法
比较套路的题
首先画个图，然后把 \(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;
}