题解：CF811E Vladik and Entertaining Flags

include13_fAKe · 2025-10-10 14:58:05 · 题解

近期的 CF 补累了回来做杂题！

这道题我走了不少弯路，尝试了很多错误的解法，最终才找到正解的。

看到题目之后首先想到的是连通块数等于点数减边数，于是写了一个这样的代码：

#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
int n,m,q;
int a[12][114514];

int qzh1[114514];   //代表列的相同 
int qzh2[114514];   //跨行  
int main(){
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();         
        }
    }
//  for(int i=1;i<=n;i++){
//      for(int j=1;j<=m;j++){
//          cout<<a[i][j]<<' ';
//      }
//      cout<<endl;
//  }
//  cout<<endl;
    for(int i=1;i<=m;i++){
        //以 m 作为宽转移 
        qzh1[i]+=qzh1[i-1],qzh2[i]+=qzh2[i-1];
        for(int j=2;j<=n;j++){
            qzh1[i]+=(a[j][i]==a[j-1][i]);
//          if(a[j][i]==a[j-1][i]){
//              cout<<'!'<<'('<<j<<','<<i<<')'<<' '<<'('<<j-1<<','<<i<<')'<<endl;
//          }
//          else{
//              cout<<'@'<<'('<<j<<','<<i<<')'<<' '<<'('<<j-1<<','<<i<<')'<<endl;
//          }
        } 
        for(int j=1;j<=n;j++){
            qzh2[i]+=(a[j][i]==a[j][i-1]); 
        } 
//      cout<<'#'<<qzh1[i]<<' '<<qzh2[i]<<endl;
    } 
    while(q--){
        int l=read(),r=read();
//      cout<<n*(r-l+1)<<' '<<qzh1[r]-qzh1[l-1]<<' '<<qzh2[r]-qzh2[l]<<endl;
        write2(n*(r-l+1)-(qzh1[r]-qzh1[l-1])-(qzh2[r]-qzh2[l]));
    }
    putchar('\n');
    return 0;
}//2017.5.27~2025.10.10 

发现它会 WA on #2，因为可能出现以下情况：（x 代表矩阵内某一个相同的数）

此时点数为 4，边数（只在相同且相邻的元素之间连边）也为 4。算下来答案为 0，但实际答案为 1。

考虑平面图的欧拉公式：C=V-E+F-1。（V 代表点数，E 代表边数，F 代表边分割之后形成的区域数）我想的是统计有多少个

代表多少个平面。

#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
int n,m,q;
int a[12][114514];

int qzh1[114514];   //代表列的相同 
int qzh2[114514];   //跨行  
int qzh3[114514];   //面数  
int main(){
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();         
        }
    }
//  for(int i=1;i<=n;i++){
//      for(int j=1;j<=m;j++){
//          cout<<a[i][j]<<' ';
//      }
//      cout<<endl;
//  }
//  cout<<endl;
    for(int i=1;i<=m;i++){
        //以 m 作为宽转移 
        qzh1[i]+=qzh1[i-1],qzh2[i]+=qzh2[i-1];
        qzh3[i]+=qzh3[i-1];
        for(int j=2;j<=n;j++){
            qzh1[i]+=(a[j][i]==a[j-1][i]);
            qzh3[i]+=(a[j][i]==a[j-1][i]&&a[j][i]==a[j][i-1]&&a[j][i]==a[j-1][i-1]); 
//          if(a[j][i]==a[j-1][i]){
//              cout<<'!'<<'('<<j<<','<<i<<')'<<' '<<'('<<j-1<<','<<i<<')'<<endl;
//          }
//          else{
//              cout<<'@'<<'('<<j<<','<<i<<')'<<' '<<'('<<j-1<<','<<i<<')'<<endl;
//          }
        } 
        for(int j=1;j<=n;j++){
            qzh2[i]+=(a[j][i]==a[j][i-1]); 
        } 
//      cout<<'#'<<qzh1[i]<<' '<<qzh2[i]<<endl;
    } 
    while(q--){
        int l=read(),r=read();
//      cout<<n*(r-l+1)<<' '<<qzh1[r]-qzh1[l-1]<<' '<<qzh2[r]-qzh2[l]<<' '<<qzh3[r]-qzh3[l-1]<<endl;
        write2(n*(r-l+1)-(qzh1[r]-qzh1[l-1])-(qzh2[r]-qzh2[l])+(qzh3[r]-qzh3[l]));
    }
    putchar('\n');
    return 0;
}//2017.5.27~2025.10.10 

但是有一种例外需要注意：

于是原先的方法彻底失效了！

因为 n 很小，m 也只有 10^5，又是无修改的区间查询，考虑并查集+线段树的神奇做法！

线段树的每一个节点维护一段区间 [l,r]，维护 l 列和 r 列的所有位置所在的极大连通块。两块合并时判断两边是否同色，若同色，直接合并。

于是写出了以下代码：

#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
const int MAXN=114514; 
struct SGT{
    int l,r;    //代表这里的左右区间情况  
    int lcol[15],rcol[15];  //代表左右两边的颜色 其实是并查集的参数 
    int col;    //颜色数目  
}tree[MAXN*5],tree1[MAXN*5];    //tree1 代表永久保存版本的 tree  

//vector<int> cal;  //在计算结束之后要还原的位置 

queue<int> cal;

int n,m,q;

int id_[15][MAXN],a[15][MAXN];
int idx=0;  

int fa[15*MAXN];    //代表所有的父亲 并查集 不要求其可撤销  

int col_in_column[MAXN];    //代表一列的情况  

inline int find(int u){
    if(fa[u]==u)    return u;
    return fa[u]=find(fa[u]);
}
void pushup(int id,int mid){
    int L=mid,R=mid+1;  //由这两边的颜色决定  
    //将两边合并 
    tree[id].col=tree[id*2].col+tree[id*2+1].col;
    for(int i=1;i<=n;i++){
        tree[id].lcol[i]=find(tree[id*2].lcol[i]);
        tree[id].rcol[i]=find(tree[id*2+1].rcol[i]);
//      if(a[L][i]==a[R][i]){
//          tree[id].lcol[i]=find(tree[id].lcol[i]);
//          tree[id].rcol[i]=find(tree[id].rcol[i]);
//          if(tree[id].lcol[i]!=tree[id].rcol[i]){
//              fa[tree[id].lcol[i]]=tree[id].rcol[i];
//          }
//      } 
        //仍然是从两边往上上传  
        tree[id*2].rcol[i]=find(tree[id*2].rcol[i]),tree[id*2+1].lcol[i]=find(tree[id*2+1].lcol[i]); 
        if(a[i][L]==a[i][R]){
//          cout<<'#'<<'('<<i<<','<<L<<')'<<' '<<'('<<i<<','<<R<<')'<<endl;
            if(tree[id*2].rcol[i]!=tree[id*2+1].lcol[i]){
//              cout<<'@'<<'('<<i<<','<<L<<')'<<' '<<'('<<i<<','<<R<<')'<<endl;
//              说明两侧颜色不一 需要调整 
                fa[tree[id*2].rcol[i]]=tree[id*2+1].lcol[i];
//              cout<<'%'<<tree[id*2].rcol[i]<<' '<<tree[id*2+1].lcol[i]<<endl;
                tree[id].col--; //代表这里改变了  
            }
        } 
    }  
    for(int i=1;i<=n;i++){
        tree[id].lcol[i]=find(tree[id].lcol[i]);
        tree[id].rcol[i]=find(tree[id].rcol[i]);
        tree1[id].lcol[i]=tree[id].lcol[i],tree1[id].rcol[i]=tree[id].rcol[i];  //tree1 保护 tree 的内层元素  
    } 
    tree1[id].col=tree[id].col;
}
void build(int id,int l,int r){
    tree[id].l=l,tree[id].r=r;
    tree1[id].l=l,tree1[id].r=r; 
    if(l==r){
        for(int i=1;i<=n;i++){
            tree[id].lcol[i]=fa[id_[i][l]];
            tree[id].rcol[i]=fa[id_[i][r]];
//          cout<<'!'<<id<<' '<<l<<' '<<r<<' '<<fa[id_[i][l]]<<' '<<fa[id_[i][r]]<<' '<<tree[id].lcol[i]<<' '<<tree[id].rcol[i]<<endl;
            tree1[id].lcol[i]=tree[id].lcol[i],tree1[id].rcol[i]=tree[id].rcol[i];
        }
        tree[id].col=col_in_column[l];
        return;
    }
    int mid=l+r>>1;
    build(id*2,l,mid),build(id*2+1,mid+1,r);
    pushup(id,mid); //合并左右边界  
}
SGT query(int id,int l,int r){
    int l1=tree[id].l,r1=tree[id].r;
    if(l1>=l&&r1<=r){
        return tree[id];    //直接返回整一个的节点  
    }
    int mid=l1+r1>>1;
    SGT A,B,C;
    int tag=0;
    if(l<=mid)  A=query(id*2,l,r),tag++;
    if(r>mid)   B=query(id*2+1,l,r),tag+=2;
    if(tag==1)  return A;
    if(tag==2)  return B;   //两个区间合并技巧 
    C.col=A.col+B.col;
    int L=mid,R=mid+1; 
    for(int i=1;i<=n;i++){
        C.lcol[i]=find(A.lcol[i]),C.rcol[i]=find(B.rcol[i]);
        A.rcol[i]=find(A.rcol[i]),B.lcol[i]=find(B.lcol[i]);
        if(a[i][L]==a[i][R]){
            if(A.rcol[i]!=B.lcol[i]){
                fa[A.rcol[i]]=B.lcol[i];
                cal.push(A.rcol[i]),cal.push(B.lcol[i]);
                C.col--;
            }
        }
    }
    for(int i=1;i<=n;i++){
        C.lcol[i]=find(C.lcol[i]);
        C.rcol[i]=find(C.rcol[i]);
    }
    return C;
}
int main(){
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            id_[i][j]=++idx,a[i][j]=read();
            if(a[i][j]==a[i-1][j])  fa[id_[i][j]]=fa[id_[i-1][j]];
            else    fa[id_[i][j]]=id_[i][j],col_in_column[j]++; //在这里 
        }
    }
//  cout<<endl;
//  for(int i=1;i<=n;i++){
//      for(int j=1;j<=m;j++){
//          cout<<fa[id_[i][j]]<<' ';
//      }
//      cout<<endl;
//  }
//  cout<<endl;
//  for(int i=1;i<=m;i++){
//      cout<<col_in_column[i]<<' ';
//  }
//  cout<<endl;
    build(1,1,m);   //后面的操作仅需修复相关的并查集即可 
//  for(int i=1;i<=4*m;i++){
//      cout<<"谭总的世界-022"<<endl;
//      cout<<'#'<<i<<' '<<tree1[i].l<<' '<<tree1[i].r<<' '<<tree1[i].col<<endl;
//      for(int j=1;j<=n;j++){
//          cout<<tree1[i].lcol[j]<<' ';
//      }
//      cout<<endl;
//      for(int j=1;j<=n;j++){
//          cout<<tree1[i].rcol[j]<<' ';
//      }
//      cout<<endl<<endl;
//  } 
//  cout<<endl;
    for(int i=1;i<=idx;i++){
        fa[i]=i;    //又把他搞回来  
    }
    while(q--){
        int l=read(),r=read();
        write2(query(1,l,r).col);
        while(!cal.empty()){
            int w=cal.front();
            cal.pop();
            fa[w]=w;
        }
    }
    putchar('\n');
    return 0;
}//2017.5.27  

该代码存在一严重问题：随着合并的不断推进，并查集编号会发生变化，所以需要维护并查集编号的历史值，具体来说再开一颗相同的线段树就够了！

时间复杂度 O(nm\log m\alpha (n)+q\log m\alpha (n))。

#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
const int MAXN=114514; 
struct SGT{
    int l,r;    //代表这里的左右区间情况  
    int lcol[15],rcol[15];  //代表左右两边的颜色 其实是并查集的参数 
    int col;    //颜色数目  
}tree[MAXN*5],tree1[MAXN*5];    //tree1 代表永久保存版本的 tree  

//vector<int> cal;  //在计算结束之后要还原的位置 

queue<int> cal;

int n,m,q;

int id_[15][MAXN],a[15][MAXN];
int idx=0;  

int fa[15*MAXN];    //代表所有的父亲 并查集 不要求其可撤销  

int col_in_column[MAXN];    //代表一列的情况  

inline int find(int u){
    if(fa[u]==u)    return u;
    return fa[u]=find(fa[u]);
}
void pushup(int id,int mid){
    int L=mid,R=mid+1;  //由这两边的颜色决定  
    //将两边合并 
    tree[id].col=tree[id*2].col+tree[id*2+1].col;
    for(int i=1;i<=n;i++){
        tree[id].lcol[i]=find(tree[id*2].lcol[i]);
        tree[id].rcol[i]=find(tree[id*2+1].rcol[i]);
//      if(a[L][i]==a[R][i]){
//          tree[id].lcol[i]=find(tree[id].lcol[i]);
//          tree[id].rcol[i]=find(tree[id].rcol[i]);
//          if(tree[id].lcol[i]!=tree[id].rcol[i]){
//              fa[tree[id].lcol[i]]=tree[id].rcol[i];
//          }
//      } 
        //仍然是从两边往上上传  
        tree[id*2].rcol[i]=find(tree[id*2].rcol[i]),tree[id*2+1].lcol[i]=find(tree[id*2+1].lcol[i]); 
        if(a[i][L]==a[i][R]){
//          cout<<'#'<<'('<<i<<','<<L<<')'<<' '<<'('<<i<<','<<R<<')'<<endl;
            if(tree[id*2].rcol[i]!=tree[id*2+1].lcol[i]){
//              cout<<'@'<<'('<<i<<','<<L<<')'<<' '<<'('<<i<<','<<R<<')'<<endl;
//              说明两侧颜色不一 需要调整 
                fa[tree[id*2].rcol[i]]=tree[id*2+1].lcol[i];
//              cout<<'%'<<tree[id*2].rcol[i]<<' '<<tree[id*2+1].lcol[i]<<endl;
                tree[id].col--; //代表这里改变了  
            }
        } 
    }  
    for(int i=1;i<=n;i++){
        tree[id].lcol[i]=find(tree[id].lcol[i]);
        tree[id].rcol[i]=find(tree[id].rcol[i]);
        tree1[id].lcol[i]=tree[id].lcol[i],tree1[id].rcol[i]=tree[id].rcol[i];  //tree1 保护 tree 的内层元素  
    } 
    tree1[id].col=tree[id].col;
}
void build(int id,int l,int r){
    tree[id].l=l,tree[id].r=r;
    tree1[id].l=l,tree1[id].r=r; 
    if(l==r){
        for(int i=1;i<=n;i++){
            tree[id].lcol[i]=fa[id_[i][l]];
            tree[id].rcol[i]=fa[id_[i][r]];
//          cout<<'!'<<id<<' '<<l<<' '<<r<<' '<<fa[id_[i][l]]<<' '<<fa[id_[i][r]]<<' '<<tree[id].lcol[i]<<' '<<tree[id].rcol[i]<<endl;
            tree1[id].lcol[i]=tree[id].lcol[i],tree1[id].rcol[i]=tree[id].rcol[i];
        }
        tree[id].col=col_in_column[l];
        tree1[id].col=tree[id].col;
        return;
    }
    int mid=l+r>>1;
    build(id*2,l,mid),build(id*2+1,mid+1,r);
    pushup(id,mid); //合并左右边界  
}
SGT query(int id,int l,int r){
//  cout<<'*'<<id<<' '<<l<<' '<<r<<endl;
    int l1=tree[id].l,r1=tree[id].r;
    if(l1>=l&&r1<=r){
        return tree1[id];   //直接返回整一个的节点  
    }
    int mid=l1+r1>>1;
    SGT A,B,C;
    int tag=0;
    if(l<=mid)  A=query(id*2,l,r),tag++;
    if(r>mid)   B=query(id*2+1,l,r),tag+=2;
    if(tag==1){
//      cout<<'A'<<' '<<l<<' '<<r<<' '<<A.col<<endl;
        return A;
    }   
    if(tag==2){
//      cout<<'B'<<' '<<l<<' '<<r<<' '<<B.col<<endl;
        return B;   //两个区间合并技巧 
    }
    C.col=A.col+B.col;
//  cout<<"col"<<' '<<A.col<<' '<<B.col<<endl;
    int L=mid,R=mid+1; 
//  cout<<'C'<<' '<<id<<endl;
//  for(int i=1;i<=n;i++){
//      cout<<'!'<<A.lcol[i]<<' '<<A.rcol[i]<<endl;
//  }
//  for(int i=1;i<=n;i++){
//      cout<<'@'<<B.lcol[i]<<' '<<B.rcol[i]<<endl;
//  }
    for(int i=1;i<=n;i++){
        C.lcol[i]=find(A.lcol[i]),C.rcol[i]=find(B.rcol[i]);
        A.rcol[i]=find(A.rcol[i]),B.lcol[i]=find(B.lcol[i]);
        if(a[i][L]==a[i][R]){
            if(A.rcol[i]!=B.lcol[i]){
                fa[A.rcol[i]]=B.lcol[i];
//              cout<<A.rcol[i]<<" "<<B.lcol[i]<<endl;
                cal.push(A.rcol[i]),cal.push(B.lcol[i]);
                C.col--;
//              cout<<'&'<<i<<endl;
//              cout<<"谭总的世界-035"<<endl;
            }
        }
    }
    for(int i=1;i<=n;i++){
        C.lcol[i]=find(C.lcol[i]);
        C.rcol[i]=find(C.rcol[i]);
//      cout<<'!'<<C.lcol[i]<<' '<<C.rcol[i]<<endl;
    }
    return C;
}
int main(){
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            id_[i][j]=++idx,a[i][j]=read();
            if(a[i][j]==a[i-1][j])  fa[id_[i][j]]=fa[id_[i-1][j]];
            else    fa[id_[i][j]]=id_[i][j],col_in_column[j]++; //在这里 
        }
    }
//  cout<<endl;
//  for(int i=1;i<=n;i++){
//      for(int j=1;j<=m;j++){
//          cout<<fa[id_[i][j]]<<' ';
//      }
//      cout<<endl;
//  }
//  cout<<endl;
//  for(int i=1;i<=m;i++){
//      cout<<col_in_column[i]<<' ';
//  }
//  cout<<endl;
    build(1,1,m);   //后面的操作仅需修复相关的并查集即可 
//  for(int i=1;i<=4*m;i++){
//      cout<<"谭总的世界-022"<<endl;
//      cout<<'#'<<i<<' '<<tree1[i].l<<' '<<tree1[i].r<<' '<<tree1[i].col<<endl;
//      for(int j=1;j<=n;j++){
//          cout<<tree1[i].lcol[j]<<' ';
//      }
//      cout<<endl;
//      for(int j=1;j<=n;j++){
//          cout<<tree1[i].rcol[j]<<' ';
//      }
//      cout<<endl<<endl;
//  } 
//  cout<<endl;
    for(int i=1;i<=idx;i++){
        fa[i]=i;    //又把他搞回来  
    }
    while(q--){
        int l=read(),r=read();
        write2(query(1,l,r).col);
        while(!cal.empty()){
            int w=cal.front();
            cal.pop();
            fa[w]=w;
        }
    }
    putchar('\n');
    return 0;
}//2017.5.27