题解：P13084 [NOISG 2017] I want to be the very best too! / 宝可梦大师

Ipdtr · 2026-11-13 13:51:08 · 题解

竞选最石带根号做法

由题意不难想到 \text{kruskal} 重构树，随后转成单点修，区间查。

直接分块，做块的桶前缀和，再记 [i,j] 块的答案为 sumn_{i,j}，那么查询是显然做到 O(\sqrt n) 的。

主要难点在修改，发现相当于对部分 i,j 连续的 sumn 修改，上二维树状数组维护即可。

这样即可做到单次 O(\sqrt n)。

#include<bits/stdc++.h>
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug cout<<"debug"<<endl
using namespace std;
int r,c,q;
int a[1000010],cnt,n;
int id[50010],B,tag[250][50010],sumn[250][250],V=5e4;
struct BIT{
    int ch[255][255];
    void add(int x,int y,int k){
        for(int i=x;i<=id[n];i+=i&-i)
            for(int j=y;j<=id[n];j+=j&-j)
                ch[i][j]+=k;
    }
    int ask(int x,int y){
        int sumn=0;
        for(int i=x;i;i-=i&-i)
            for(int j=y;j;j-=j&-j)
                sumn+=ch[i][j];     
        return sumn;
    }
    void add(int l1,int r1,int l2,int r2,int k){
        if(l1>r1||l2>r2) return;
        add(l1,r1,k);
        add(l1,r2+1,-k);
        add(l2+1,r1,-k);
        add(l2+1,r2+1,k);
    }
}S;
vector<vector<int>> l,p;
vector<array<int,3>> e;
int dx[2]={0,1};
int dy[2]={1,0};
vector<int> g[2000010];
int f[2000010],tot,whk[2000010];
int fa[2000010][25],st[2000010],et[2000010];
int find(int k){return f[k]==k?f[k]:f[k]=find(f[k]);}
void merge(int a,int b){f[find(a)]=find(b);}
int temp[50010];
inline int L(int x){return (x-1)*B+1;}
inline int R(int x){return min(n,x*B);}
int hsh(int a,int b){return (a-1)*c+b;}
int antihsh(int k){
    int b=(k-1)%c+1,a=(k-1)/c+1;
    return p[a][b];
}
void dfs(int u){
    if(!g[u].size()){
        cnt++;a[cnt]=u;
        st[u]=et[u]=cnt;
        return;
    }
    st[u]=1e9;
    for(auto v:g[u]){
        dfs(v);fa[v][0]=u;
        st[u]=min(st[u],st[v]);
        et[u]=max(et[u],et[v]);
    }
}
int get(int l,int r,int val){return tag[r][val]-tag[l-1][val];}
int ask(int l,int r){
    int ans=0;
    if(id[l]==id[r]){
        for(int i=l;i<=r;i++){
            if(!temp[a[i]]) ans++;
            temp[a[i]]=1;
        }
        for(int i=l;i<=r;i++) temp[a[i]]=0;
        return ans;
    }
    int x=id[l],y=id[r];
    if(x+1<=y-1) ans=sumn[x+1][y-1]+S.ask(x+1,y-1);
    else ans=0;
    for(int i=l;i<=R(x);i++){
        if(!get(x+1,y-1,a[i])&&!temp[a[i]]) ans++;
        temp[a[i]]=1;
    }
    for(int i=L(y);i<=r;i++){
        if(!get(x+1,y-1,a[i])&&!temp[a[i]]) ans++;
        temp[a[i]]=1;
    }   
    for(int i=l;i<=R(x);i++) temp[a[i]]=0;
    for(int i=L(y);i<=r;i++) temp[a[i]]=0;
    return ans;
}
int solve(int x,int y,int maxn){
    if(l[x][y]>maxn) return 0;
    int pos=hsh(x,y);
    for(int k=20;k>=0;k--) if(whk[fa[pos][k]]<=maxn) pos=fa[pos][k];
    return ask(st[pos],et[pos]);
}
void change(int pos,int val){
    if(val==a[pos]) return;
    int lpos=id[pos],rpos=id[pos];
    while(lpos>=1&&get(lpos,lpos,a[pos])<=(lpos==id[pos])) lpos--;lpos++;
    while(rpos<=id[n]&&get(rpos,rpos,a[pos])<=(rpos==id[pos])) rpos++;rpos--;
    S.add(lpos,id[pos],id[pos],rpos,-1);
    lpos=id[pos],rpos=id[pos];
    while(lpos>=1&&get(lpos,lpos,val)==0) lpos--;lpos++;
    while(rpos<=id[n]&&get(rpos,rpos,val)==0) rpos++;rpos--;
    S.add(lpos,id[pos],id[pos],rpos,1);
    for(int i=id[pos];i<=id[n];i++) tag[i][a[pos]]--;
    for(int i=id[pos];i<=id[n];i++) tag[i][val]++;
    a[pos]=val;
}
signed main(){
    cin>>r>>c>>q;
    l.push_back({});
    for(int i=1;i<=r;i++){
        l.push_back({});l[i].push_back(0); 
        for(int j=1;j<=c;j++){int x;cin>>x;l[i].push_back(x);}  
    }
    p.push_back({});
    for(int i=1;i<=r;i++){
        p.push_back({});p[i].push_back(0); 
        for(int j=1;j<=c;j++){int x;cin>>x;p[i].push_back(x);}  
    }   
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            for(int k=0;k<2;k++){
                int x=i+dx[k],y=j+dy[k];
                if(x<1||y<1||x>r||y>c) continue;
                e.push_back({max(l[x][y],l[i][j]),hsh(x,y),hsh(i,j)});
            }
    sort(e.begin(),e.end());
    for(int i=1;i<=1e6;i++) f[i]=i;tot=r*c;
    for(auto t:e){
        int w=t[0],u=t[1],v=t[2];
        if(find(u)!=find(v)){
            tot++;whk[tot]=w;
            g[tot].push_back(find(u));g[tot].push_back(find(v));
            merge(u,tot);merge(v,tot);
        }
    }   
    dfs(tot);fa[tot][0]=tot;
    for(int k=1;k<=20;k++)
        for(int i=1;i<=tot;i++)
            fa[i][k]=fa[fa[i][k-1]][k-1];
    n=r*c;B=sqrt(n);
    for(int i=1;i<=n;i++) a[i]=antihsh(a[i]);
    for(int i=1;i<=n;i++) id[i]=(i-1)/B+1;
    for(int i=1;i<=id[n];i++){
        for(int j=L(i);j<=R(i);j++) tag[i][a[j]]++;
        for(int j=1;j<=V;j++) tag[i][j]+=tag[i-1][j];
    }
    for(int i=1;i<=id[n];i++){
        int ans=0;
        for(int j=L(i);j<=n;j++){
            if(!temp[a[j]]) ans++;
            temp[a[j]]=1;
            if(j==R(id[j])) sumn[i][id[j]]=ans;
        }
        for(int j=L(i);j<=n;j++) temp[a[j]]=0;
    }
    while(q--){
        int opt,x,y,lk;cin>>opt>>x>>y>>lk;
        swap(x,y);
        if(opt==1) change(st[hsh(x,y)],lk);
        else cout<<solve(x,y,lk)<<endl;
    } 
    return 0;
}