题解 P8427 [COI 2020] Paint

· · 题解

终于传上来了，咕咕了两年了属实不容易。

考虑一个很裸的暴力，我们每次 BFS 然后更新染色。时间复杂度显然很劣。

接下来我们考虑根号分治。（下面称相邻的连通块为邻居）

考虑面积 \leq B 的块，我们可以暴力扫描它的邻居然后合并。

考虑面积 >B 的块，我们称之为大块，我们对于所有大块去维护一个哈希表，f(x) 表示这个大块颜色为 x 的所有邻居集合，由于大块个数最多只有 \frac{n}{B} ，所以这里空间复杂度上界为 O(\frac{n^2}{B})（实际常数很小）。

为了支持这个哈希表的更新，我们还必须对于所有块去维护其邻居中大块的集合，所以这里空间复杂度上界同 O(\frac{n^2}{B})（实际常数很小）。

再考虑两个块的合并，我们采用启发式合并，每次将小的集合连向大的集合。

由于每个连通块的合并次数不会超过 \log 次，每次小块寻找邻居的复杂度最多为 B 级别的，大块寻找邻居是 O(\frac{R\times S}{B}) 级别的， 所以复杂度大约是 O(R\times S\times \log(R\times S)+Q\times B+\frac{Q\times R\times S}{B})。即 O(n\sqrt n) 级别的。

实现时细节还是很多的。自己注意下别写错复杂度就行。

//QwQcOrZ yyds!!!
#include<bits/stdc++.h>
#define ll long long
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define R(i,a,b) for (int i=(a);i<(b);++i)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define go(i,x) for (int i=head[x];i;i=e[i].nx)
#define mp make_pair
#define pb push_back
#define pa pair < int,int >
#define fi first
#define se second
#define re register
#define be begin()
#define en end()
#define sqr(x) ((x)*(x))
#define ret return puts("-1"),0;
#define put putchar('\n')
#define inf 1000000005
#define mod 998244353
//#define int ll
#define N 200005
using namespace std;
inline char gc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
//#define gc getchar
inline ll read(){char c=gc();ll su=0,f=1;for (;c<'0'||c>'9';c=gc()) if (c=='-') f=-1;for (;c>='0'&&c<='9';c=gc()) su=su*10+c-'0';return su*f;}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
int n,m,Q,fa[N],neg[N],xx,yy,col,ID,cnt;
const int c[]={0,0,0,-1,1},d[]={0,-1,1,0,0};
const int B=0;
vector<vector<int> >a,bel;
struct
{
    int large,col;
    vector<pa>nod;
    vector<int>bignb;
    map<int,vector<int>>lis;
}S[N];
int gf(int x)
{
    if (x==fa[x]) return x;
    return gf(fa[x]);
}
void dfs(int x,int y)
{
    S[cnt].nod.push_back({x,y});
    bel[x][y]=cnt;
    for (int i=1;i<=4;++i)
    {
        int u=x+c[i],v=y+d[i];
        if (u>=1&&u<=n&&v>=1&&v<=m)
        {
            if (a[u][v]==a[x][y]&&!bel[u][v])
            {
                dfs(u,v);
            }
        }
    }
}
inline void turn_to_big(int now)
{
    S[now].large=1;
    vector<int>nowb;
    ID++;
    for (auto u:S[now].nod)
    {
        for (int j=1;j<=4;++j)
        {
            int x=u.fi+c[j],y=u.se+d[j];
            if (x>=1&&x<=n&&y>=1&&y<=m)
            {
                if (bel[x][y]==now) continue;
                int v=bel[x][y];
                if (neg[v]==ID) continue;
                neg[v]=ID;
                S[v].bignb.push_back(now);
                S[now].lis[S[v].col].push_back(v);
            }
        }
    }
}
inline int merge(int x,int y)
{
    if (!S[x].large&&S[y].large) turn_to_big(x);
    else
    if (S[x].large&&!S[y].large) turn_to_big(y);

    if (S[x].nod.size()>S[y].nod.size()) swap(x,y);
    fa[x]=y;
    for (auto u:S[x].nod)
    {
        bel[u.fi][u.se]=y;
        S[y].nod.push_back(u);
    }
    vector<pa>().swap(S[x].nod);

    if (S[x].bignb.size()>S[y].bignb.size()) 
        S[x].bignb.swap(S[y].bignb);
    for (auto u:S[x].bignb)
    {
        S[y].bignb.push_back(u);
    }
    vector<int>().swap(S[x].bignb);
    re vector<int>nownb;
    ID++;
    for (auto u:S[y].bignb)
    {
        int uu=gf(u);
        if (uu!=y&&neg[uu]!=ID)
        {
            neg[uu]=ID;
            nownb.push_back(uu);
        }
    }
    vector<int>().swap(S[y].bignb);
    S[y].bignb=nownb;
    for (auto u:S[x].lis)
    {
        int nowcol=u.fi;
        auto &lis1=u.se;
        auto &lis2=S[y].lis[nowcol];
        if (lis1.size()>lis2.size()) lis1.swap(lis2);
        for (auto v:lis1)
        {
            lis2.push_back(v);
        }
        vector<int>().swap(lis1);
    }
    S[x].lis.clear();
    if (!S[y].large&&S[y].nod.size()>B) turn_to_big(y);
    return y;
}
signed main()
{
    n=read(),m=read();
    a.resize(n+10);
    for (re int i=1;i<=n;++i) a[i].resize(m+10);
    bel.resize(n+10);
    for (re int i=1;i<=n;++i) bel[i].resize(m+10);
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            a[i][j]=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            if (!bel[i][j]) 
            {
                bel[i][j]=++cnt;
                S[cnt].large=0;
                S[cnt].nod.clear();
                S[cnt].bignb.clear();
                S[cnt].lis.clear();
                S[cnt].col=a[i][j];
                dfs(i,j);
            }
    for (re int i=1;i<=cnt;++i)
    {
        ID++;
        for (auto u:S[i].nod)
        {
            for (re int j=1;j<=4;++j)
            {
                int x=u.fi+c[j],y=u.se+d[j];
                if (x>=1&&x<=n&&y>=1&&y<=m)
                {
                    if (bel[x][y]==i) continue;
                    int v=bel[x][y];
                    if (neg[v]==ID) continue;
                    neg[v]=ID;
                    if (S[v].nod.size()>B) S[i].bignb.push_back(v);
                    if (S[i].nod.size()>B)
                        S[i].lis[S[v].col].push_back(v);
                }
            }
        }
    }
    for (re int i=1;i<=cnt;++i)
    {
        if (S[i].nod.size()>B) turn_to_big(i);
        fa[i]=i;
    }
//  return 0;
    Q=read();
    while (Q--)
    {
        xx=read(),yy=read(),col=read();
        re int now=bel[xx][yy];
//      cout<<now<<" "<<S[now].large<<endl;
        if (!S[now].large)
        {
            re vector<int>nowb;
            ID++;
            for (auto u:S[now].nod)
            {
                for (re int j=1;j<=4;++j)
                {
                    int x=u.fi+c[j],y=u.se+d[j];
                    if (x>=1&&x<=n&&y>=1&&y<=m)
                    {
                        if (bel[x][y]==now) continue;
                        int v=bel[x][y];
                        if (neg[v]==ID) continue;
                        neg[v]=ID;
                        if (S[v].col==col) nowb.push_back(v);
                    }
                }
            }
            for (auto u:nowb)
            {
                now=merge(now,u);
            }

            nowb.clear();
            ID++;
            for (auto u:S[now].bignb)
            {
                int uu=gf(u);
                if (uu!=now&&neg[uu]!=ID)
                {
                    neg[uu]=ID;
                    nowb.push_back(uu);
                }
            }
            S[now].bignb.clear();
            S[now].bignb=nowb;
            S[now].col=col;
            for (auto u:S[now].bignb)
            {
                S[u].lis[S[now].col].push_back(now);
            }
        }
        else
        {
            re vector<int>nowb;
            ++ID;
            for (auto u:S[now].lis[col])
            {
                int uu=gf(u);
                if (uu!=now&&neg[uu]!=ID)
                {
                    neg[uu]=ID;
                    if (S[uu].col==col) nowb.push_back(uu);
                }
            }
            S[now].lis[col].clear();
            S[now].lis[col]=nowb;
//          cout<<"!"<<endl;
            for (auto u:nowb)
            {
//              cout<<u<<endl;
                now=merge(now,u);
            }
            nowb.clear();
            ID++;
            for (auto u:S[now].bignb)
            {
                int uu=gf(u);
                if (uu!=now&&neg[uu]!=ID)
                {
                    neg[uu]=ID;
                    nowb.push_back(uu);
                }
            }
            S[now].bignb.clear();
            S[now].bignb.swap(nowb);

            S[now].col=col;
            for (auto u:S[now].bignb)
            {
                S[u].lis[S[now].col].push_back(now);
            }
        }
    }
    for (re int i=1;i<=n;++i)
    {
        for (re int j=1;j<=m;++j)
            writesp(S[bel[i][j]].col);
        puts("");
    }
}