P10665 [AMPPZ2013] Bytehattan

Rigel · 2025-09-29 11:28:09 · 题解

思路

由于本题强制在线，时光倒流无法进行。

换个角度思考，删边等于将格子合并。n \times n 个格点形成的网格图中有 (n-1) \times (n-1) 个格子，以及一个代表网格图外部的虚拟格子。

考虑在什么情况下，边两端的格点会由连通变为不连通。

若在合并格子前，即将被合并的两个格子已经属于同一连通块，那么合并后必然会形成环，而这个环必然会将环内外的格点分开，使对应边两端的格点不连通；否则边两端的格点仍然连通。

并查集维护格子的连通情况即可。

时间复杂度为 \mathcal{O}(k \alpha(n^2))，即 \mathcal{O}(n^2 \alpha(n^2))。

Code

#include<bits/stdc++.h>
#define int long long

const int N=1510;

using namespace std;

int n,q,lst=1,fa[N*N],siz[N*N],id[N][N];

int x,y;

char op;

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}

inline char read1(){
    char ch=getchar();
    while(ch!='N'&&ch!='E')ch=getchar();
    return ch;
}

void _init(){
    for(int i=1;i^n;i++)for(int j=1;j^n;j++)id[i][j]=(i-1)*n+j;
    for(int i=1;i^n;i++)for(int j=1;j^n;j++)fa[id[i][j]]=id[i][j],siz[id[i][j]]=1;
}

int getfa(int x){
    return (fa[x]==x)?x:(fa[x]=getfa(fa[x]));
}

void _uni(int x,int y){
    if(siz[x]>siz[y])swap(x,y);
    fa[x]=y;
    siz[y]+=siz[x];
}

void add(int x,int y,int _x,int _y){
    int u=id[x][y],v=id[_x][_y];
    int fx=getfa(u),fy=getfa(v);
    if(fx^fy)lst=1,_uni(fx,fy);
    else lst=0;
}

signed main(){
    n=read(),q=read();
    _init();
    while(q--){
        if(lst){
            x=read(),y=read(),op=read1();
            read(),read(),read1();
        }else{
            read(),read(),read1();
            x=read(),y=read(),op=read1();
        }
        if(op=='N')add(x,y,x-1,y);
        else add(x,y,x,y-1);
        if(lst)printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}