题目大意
有一个 \(n\times n\) 的点阵，将相邻的点连边得到一个 \((n-1)\times(n-1)\) 的网格。\(q\) 次操作，每次删掉一条边，求删掉后边两端的点是否仍在一个连通块内。强制在线。
题解
显然，由于对偶图的性质，原图的一个割对应对偶图中的一个环，所以只需要删掉一条边时在对偶图中连边，若成环就输出 NO。
#include<iostream>
#include<cstdio>
#define maxn 4500005
using namespace std;
int n,q,x,y,u,v,key,num,f[maxn];
int getfa(int p){if(f[p]==p) return p; return f[p]=getfa(f[p]);}
void uni(int p1,int p2){int r1=getfa(p1),r2=getfa(p2); if(r1==r2){printf("NO\n"); return;} printf("YES\n"); key++; f[r2]=r1;}
int main(){
scanf("%d%d",&n,&q); num=(n-1)*(n-1)+1; for(int i=1;i<=num;i++) f[i]=i;
while(q--){
scanf("%d%d%d%d",&x,&y,&u,&v); x=(x+key)%n+1; y=(y+key)%n+1; u=(u+key)%n+1; v=(v+key)%n+1;
if(x==u){
if(x==1) uni(num,(x-1)*(n-1)+min(y,v));
else if(x==n) uni(num,(x-2)*(n-1)+min(y,v));
else uni((x-2)*(n-1)+min(y,v),(x-1)*(n-1)+min(y,v));
}else{
if(y==1) uni(num,(n-1)*(min(x,u)-1)+y);
else if(y==n) uni(num,(n-1)*(min(x,u)-1)+y-1);
else uni((n-1)*(min(x,u)-1)+y-1,(n-1)*(min(x,u)-1)+y);
}
} return 0;
}