题解：P10201 [湖北省选模拟 2024] 永恒 / eternity

zyn_ · 2024-10-05 21:38:52 · 题解

单次询问

Part 0

令 P=1145141。(x,y) 处的神之眼的元素力编号为 c_{x,y}。考虑一次询问。如果 (sx,sy),(tx,ty) 不连通（连通是相对于被雷电封锁区阻隔无法互通而言）则答案显然为否；如果 (sx,sy)=(tx,ty) 且 (sx,sy) 周围的四个相邻区域均为雷电封锁区或出了地图边界，那么积蓄的力量只能为 c_{sx,sy}，答案容易得出。

Part 1

如果 (sx,sy),(tx,ty) 连通，则有以下结论成立：若地图黑白交替染色，在 (sx,sy),(tx,ty) 所在的连通块中，以下性质（称作元素性质）满足：所有黑格中的神之眼的元素力不全相同，或者所有白格中的神之眼的元素力不全相同；则答案为是。事实上，此时从 (sx,sy) 移动到 (tx,ty) 积蓄的力量可以为任意 0,1,\dots,P-1 中的值。

下作证明：

由连通块满足元素性质，知连通块中存在 (x_1,y_1),(x_2,y_2),(x_3,y_3)，使 (x_1,y_1) 与 (x_2,y_2) 相邻，(x_2,y_2) 与 (x_3,y_3) 相邻，且 c_{x_1,y_1}\neq c_{x_3,y_3}。考虑如下路径：

其中 r_i=1 或 3。

现在钦定 k_1,k_2，所有 (p_i,q_i),(s_i,t_i)，并令 d=(P-1)^2=1311345619600 为定值。则路径长度已定，故以上路径的第一行部分与第三行部分，对路径积蓄力量的贡献确定。只需证明合理地取 r_i，可以使第二行对积蓄力量的贡献取到 0,1,\dots,P-1 中的任意数。由于模数 P=1145141 为质数，设 f_i=c_{x_i,y_i}，只需证以下数可以取 0 至 P-1 的所有值：

首先，先令所有 r_i=1，得到一个 S_0。考虑调整一些 r_i 为 3。当调整 r_{(P-1)i} 为 3 时（i=1,\dots,P-1），由费马小定理，S 在模 P 意义下增加了

由于 f_1,f_3\in [0,6] 且 f_1\neq f_3 知 P\nmid f_3-f_1。每将一个 r_{(P-1)i} 调整为 3，S 增加 f_3-f_1，且这样的调整有 P-1 次机会。

因此 S 可以取到 S_0+z(f_3-f_1)，其中 z=0,1, \dots,P-1，而这是一个模 P 的完系。

因此 S 可以取 0,1,\dots,P-1 之间的任意自然数。

命题得证。

Part 2

如果这个连通块不满足元素性质，也就是连通块中，所有黑格中的神之眼的元素力全相同，并且所有白格中的神之眼的元素力全相同，那么不妨设 (sx,sy) 为黑格，设 f=c_{sx,sy} 为连通块中黑格的神之眼的元素力编号，g 为白格的神之眼的元素力编号。那么，从 (sx,sy) 到 (tx,ty) 积蓄的力量必然形如 \overline{fg\dots fgf}\bmod P 或 \overline{fg\dots fgfg}\bmod P，取决于 (tx,ty) 为黑格或白格。

对于给定的 f,g，经过奇数或偶数个格子可以积蓄出的力量集合 L_{f,g,0/1} 是可以预处理的。以移动奇数步为例，从 f 开始作为当前数，每次将当前数加入 L_{f,g,1}，然后将当前数乘 100 加 \overline{gf} 作为新的当前数。一旦发现加入了重复的数，则停止。这样的时间复杂度上限为 O(P)，有一个 200 的超大常数，然而时限足够，不是问题。

由于模数为质数，可以证明任何在集合 L_{f,g,0/1} 中的数，都有无穷种不同的步数可以走出它。因此查询时只要判断所需力量的值是否在对应集合中即可。

多次询问，带修

现在带上修改操作，考虑线段树分治。问题转化为，在合并连通块的过程中，维护：

1. 两点之间的连通性。
2. 一个连通块中是否满足元素性质。
3. 一个连通块不满足元素性质时，将地图黑白染色，黑格与白格的神之眼的元素力编号。

用并查集维护。连通性的维护较为简单。对于维护元素性质的部分（第 2,3 条），在一个连通块中钦定这个连通块的代表元格子为黑格，维护类型 tp_i，黑格神之眼的元素力编号 f_i，白格神之眼的元素力编号 g_i。其中，当 tp_i=1 时代表不满足元素性质，此时 f_i,g_i 有效（若当前在并查集中代表元自成一个集合，则 tp_i=1，且 g_i 无效）；tp_i=2 时代表满足元素性质，f_i,g_i 无效。

合并两连通块时：

1. 若有至少一个连通块大小为 1，进行分讨特判，较容易。
2. 若两个连通块大小都 \ge 2，且至少一个连通块的 tp 为 2，则合并后 tp 为 2。
3. 若两个连通块大小都 \ge 2，且 tp 都为 1，此时合并后是否仍不满足元素性质，只取决于两连通块的代表元格子 (x_1,y_1),(x_2,y_2) 与 f_1,g_1,f_2,g_2 的值。若 |x_1-x_2|+|y_1-y_2| 为偶数且 (f_1,g_1)=(f_2,g_2)，或 |x_1-x_2|+|y_1-y_2| 为奇数且 (f_1,g_1)=(g_2,f_2)，则合并后 tp 为 1，f,g 容易得到。否则，合并后 tp 为 2。

本题总时间复杂度 O((nm+q)\log(nm))。

AC code

#include<bits/stdc++.h>
using namespace std;
#define y1 y1_ //......
#define N 507
#define Q 200009
#define P 1145141
#define pii pair<int,int>
#define fi first
#define sc second
#define mpr make_pair
int n,m,q,a[N][N],lst[N][N],op[Q],x1[Q],y1_[Q],x2[Q],y2[Q],v[Q];
char c[N][N],d[10];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
bool ok[P][10][10];
struct sg{int x,y,l,r,v;}k[Q<<2];int cnt;
inline int cv(char c){return c=='#'?-1:c-48;}
inline int co(int x,int y){return (x-1)*m+y;}
inline int clr(int x,int y){return (x+y)&1;}
inline int clr(int a){return ((a-1)/m+(a-1)%m)&1;}
int pa[N*N],h[N*N],f[N*N],g[N*N],t[N*N],siz[N*N];
//t==1, f!=-1 and g==-1: one grid
//t==2, f!=-1 and g!=-1: the two elements on the two color of grids
//t==3, f==-1 and g==-1: different elements on a color of grid
//f is element on its grid, g is element on other grids
int find(int p){
    while(pa[p]!=p)p=pa[p];
    return p;
}
struct mdf{char c;int p,n;};
struct data{
    int x,y,v;
    vector<mdf> s;
}ds[Q<<3];int num;
#define nwd ds[num]
#define ins ds[num].s.push_back
void merge(int a,int b,int i){//i is true means a and b have different color
    if(h[a]<h[b])a^=b^=a^=b;
    ins({'p',pa[b],b});pa[b]=a;
    if(h[a]==h[b])ins({'h',h[a],a}),++h[a];
    if(t[b]==1){
        if(t[a]==1){
            if(f[a]!=f[b]){
                if(siz[a]==1&&siz[b]==1)ins({'g',g[a],a}),g[a]=f[b],ins({'t',t[a],a}),t[a]=2;
                else ins({'t',t[a],a}),t[a]=3;
            }
            //else do nothing;
        }
        else if(siz[b]!=1||(i==0&&f[a]!=f[b])||(i==1&&g[a]!=f[b]))ins({'t',t[a],a}),t[a]=3;
        ins({'s',siz[a],a});siz[a]+=siz[b]; 
        return;
    }
    if(i==1){if(t[b]==3||f[a]!=g[b]||g[a]!=f[b])ins({'t',t[a],a}),t[a]=3;}
    else{if(t[b]==3||f[a]!=f[b]||g[a]!=g[b])ins({'t',t[a],a}),t[a]=3;}
    ins({'s',siz[a],a});siz[a]+=siz[b];
}
void add(int x,int y,int v){
    ++num;
    ds[num].x=x,ds[num].y=y,ds[num].v=v;
    ds[num].s.clear();
    static int z;z=co(x,y);
    pa[z]=z,h[z]=1,f[z]=v,g[z]=-1,t[z]=1,siz[z]=1;
    static int nx,ny;
    static int p1,p2;
    for(int i=0;i<4;++i){
        nx=x+dx[i],ny=y+dy[i];
        if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&a[nx][ny]!=-1){
            p1=find(z),p2=find(co(nx,ny));
            if(p1!=p2)merge(p1,p2,clr(p1)^clr(p2));         
        }
    }
    a[x][y]=v;
}
void undo(){
    a[nwd.x][nwd.y]=-1;
    static mdf i;
    while(nwd.s.size()){
        i=nwd.s.back();
        if(i.c=='p')pa[i.n]=i.p;
        if(i.c=='h')h[i.n]=i.p;
        if(i.c=='g')g[i.n]=i.p;
        if(i.c=='t')t[i.n]=i.p;
        if(i.c=='f')f[i.n]=i.p;
        if(i.c=='s')siz[i.n]=i.p;
        nwd.s.pop_back();
    }
    --num;
}
int state(int d,int b,int v){
    //a and b disconnect: 0
    //a and b connect, same element on same color grid: 1 if has solution else -1
    //otherwise: 2 
    static int cd,cb;cd=find(d),cb=find(b);
    if(cd!=cb)return 0;
    if(t[cd]==3)return 2;
    static int x,y;x=(cd-1)/m+1,y=(cd-1)%m+1;
    if((a[x][y-1]==-1||y==1)&&(a[x][y+1]==-1||y==m)&&(a[x+1][y]==-1||x==n)&&(a[x-1][y]==-1||x==1)){
        //Special! A grid alone.
        if(a[x][y]==v)return 1;
        return -1;
    }
    if(t[cd]==2){
        if(clr(d)^clr(b)){
            if(clr(d)^clr(cd))return ok[v][g[cd]][f[cd]]?1:-1;
            else return ok[v][f[cd]][g[cd]]?1:-1;
        }
        else{
            if(clr(d)^clr(cd))return ok[(v-g[cd]+P)*1030627ll%P][g[cd]][f[cd]]?1:-1;
            else return ok[(v-f[cd]+P)*1030627ll%P][f[cd]][g[cd]]?1:-1;
        }
    }
    else{//t[cd]==1
        if(clr(d)^clr(b))return ok[v][f[cd]][f[cd]]?1:-1;
        else return ok[(v-f[cd]+P)*1030627ll%P][f[cd]][f[cd]]?1:-1;
    }
}
vector<sg> vc[Q<<2];
void upd(int pl,int pr,int p,sg s){
    if(s.l<=pl&&pr<=s.r){vc[p].push_back({s.x,s.y,pl,pr,s.v});return;}
    int mid=(pl+pr)>>1;
    if(s.l<=mid)upd(pl,mid,p<<1,s);
    if(s.r>mid)upd(mid+1,pr,p<<1|1,s);
}
void solve(int l,int r,int p){
    //1. update all changes in v[p]
    //2. if on segtree's leaf, calc answer
    //3. otherwise get into deeper level
    //4. undo the updates
    for(sg st:vc[p])add(st.x,st.y,st.v);
    if(l==r){
        if(op[l]==2)puts(state(co(x1[l],y1[l]),co(x2[l],y2[l]),v[l])>=1?"Yes":"No");
    }
    else{
        int mid=(l+r)>>1;
        solve(l,mid,p<<1);solve(mid+1,r,p<<1|1);
    }
    for(sg st:vc[p])undo();
}
int main(){
    //Inazuma is the country of Eternity.
    {
        int i,p;
        for(int j=0;j<=9;++j)for(int k=0;k<=9;++k){
            p=j*10+k;
            i=p;
            while(!ok[i][j][k])ok[i][j][k]=1,i=(i*100+p)%P;
        }
    }//prework
    scanf("%d%d%d%*d",&n,&m,&q);
    for(int i=1;i<=n;++i){
        scanf("%s",c[i]+1);
        for(int j=1;j<=m;++j){
            a[i][j]=cv(c[i][j]);
            lst[i][j]=(a[i][j]==-1?-1:0);
        }
    }
    for(int i=1;i<=q;++i){
        scanf("%d%d%d",&op[i],&x1[i],&y1[i]);
        if(op[i]==1)scanf("%s",d),v[i]=cv(d[0]);
        else scanf("%d%d%d",&x2[i],&y2[i],&v[i]);
    }
    for(int i=1;i<=q;++i)if(op[i]==1){
        if(lst[x1[i]][y1[i]]!=-1)k[++cnt]={x1[i],y1[i],lst[x1[i]][y1[i]],i-1,a[x1[i]][y1[i]]};
        if(v[i]!=-1)lst[x1[i]][y1[i]]=i;
        else lst[x1[i]][y1[i]]=-1;
        a[x1[i]][y1[i]]=v[i];
    }
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(lst[i][j]!=-1)k[++cnt]={i,j,lst[i][j],q,a[i][j]};
    for(int i=1;i<=cnt;++i)upd(0,q,1,k[i]);
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)a[i][j]=-1;
    solve(0,q,1);
    return 0;
}