题目概述

EOJ4120

解题报告

本题难点就在于快速选出海拔 $\le L$ 的连通块，可以利用Kruskal重构树：

• 网格按照海拔从小到大考虑
• 对于 $(x,y)$ ，向相邻海拔低的网格连边，注意连边连向的是一个连通块的根节点（即海拔最高点，用并查集维护）

这样连边就形成了一棵树，每次找连通块就是找 $(x,y)$ 最上面的海拔 $\le L$ 的祖先 $p$ ，$p$ 的子树就是海拔 $\le L$ 的连通块。

接下来就是经典问题，区间（DFS序）上询问多少种不同的颜色，由于有修改，所以用set维护 $last$ 指针，然后树套树解决。

示例程序

#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=50000,LOG=16,maxt=3e7;
const int dif[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int n,m,te,h[maxn+5],a[maxn+5],p[maxn+5],fat[maxn+5];
int E,lnk[maxn+5],nxt[maxn+5],son[maxn+5];
int Lt[maxn+5],Rt[maxn+5],ST[maxn+5][LOG+1];
set<int> s[maxn+5];set<int>::iterator it,pre,suf;
int c[maxn+5],lst[maxn+5];
int pl,ro[maxn+5],ls[maxt+5],rs[maxt+5],sum[maxt+5];

#define ID(i,j) (((i)-1)*m+(j))
inline bool cmp(const int &i,const int &j) {return h[i]<h[j];}
int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
inline void Add(int x,int y) {son[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void DFS(int x,int pre=0){
    Lt[x]=++Lt[0];ST[x][0]=pre;
    for (int j=1;j<=LOG;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j]) DFS(son[j],x);
    Rt[x]=Lt[0];
}
void Insert(int &p,int pos,int k,int l=0,int r=Lt[0]-1){
    if (!p) p=++pl;if (l==r) {sum[p]+=k;return;}
    int mid=l+(r-l>>1);
    pos<=mid?Insert(ls[p],pos,k,l,mid):Insert(rs[p],pos,k,mid+1,r);
    sum[p]=sum[ls[p]]+sum[rs[p]];
}
void Add(int x,int p,int y) {for (;x<=Lt[0];x+=x&-x) Insert(ro[x],p,y);}
int Ask(int p,int L,int R,int l=0,int r=Lt[0]-1){
    if (!p) return 0;if (L==l && r==R) return sum[p];
    int mid=l+(r-l>>1);
    if (R<=mid) return Ask(ls[p],L,R,l,mid); else if (L>mid) return Ask(rs[p],L,R,mid+1,r);
    else return Ask(ls[p],L,mid,l,mid)+Ask(rs[p],mid+1,R,mid+1,r);
}
int Sum(int x,int p) {int sum=0;for (;x;x-=x&-x) sum+=Ask(ro[x],0,p);return sum;}
int Find(int x,int z) {for (int j=LOG;~j;j--) if (h[ST[x][j]]<=z) x=ST[x][j];return x;}
int main(){
    scanf("%d%d%d",&n,&m,&te);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&h[ID(i,j)]);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&a[ID(i,j)]);
    for (int i=1;i<=n*m;i++) p[i]=i,fat[i]=i;
    h[0]=2e9;sort(p+1,p+1+n*m,cmp);
    for (int i=1;i<=n*m;i++){
        int x=(p[i]-1)/m+1,y=(p[i]-1)%m+1;
        for (int f=0;f<4;f++){
            int xx=x+dif[f][0],yy=y+dif[f][1];
            if (1<=xx && xx<=n && 1<=yy && yy<=m && h[ID(xx,yy)]<h[p[i]]){
                if (p[i]==getfa(ID(xx,yy))) continue;
                Add(p[i],getfa(ID(xx,yy)));
                fat[getfa(ID(xx,yy))]=p[i];
            }
        }
    }
    DFS(p[n*m]);
    for (int i=1;i<=Lt[0];i++) c[Lt[i]]=a[i];
    for (int i=1;i<=Lt[0];i++){
        if (s[c[i]].size()) it=s[c[i]].end(),it--,lst[i]=*it;
        s[c[i]].insert(i);
    }
    for (int i=1;i<=Lt[0];i++) Add(i,lst[i],1);
    for (int t=1;t<=te;te--){
        int tp,x,y,z;scanf("%d%d%d%d",&tp,&x,&y,&z);swap(x,y);
        if (tp==1){
            int id=Lt[ID(x,y)];
            Add(id,lst[id],-1);
            it=s[c[id]].lower_bound(id);suf=it;suf++;
            if (suf!=s[c[id]].end()){
                Add(*suf,lst[*suf],-1);
                if (it!=s[c[id]].begin()) pre=it,pre--,lst[*suf]=*pre; else lst[*suf]=0;
                Add(*suf,lst[*suf],1);
            }
            s[c[id]].erase(id);
            c[id]=z;suf=s[z].upper_bound(id);
            if (suf!=s[z].begin()) pre=suf,pre--,lst[id]=*pre; else lst[id]=0;
            if (suf!=s[z].end()) Add(*suf,lst[*suf],-1),Add(*suf,lst[*suf]=id,1);
            Add(id,lst[id],1);
            s[c[id]].insert(id);
        } else {
            if (h[ID(x,y)]>z) {puts("0");continue;}
            int id=Find(ID(x,y),z),L=Lt[id],R=Rt[id];
            printf("%d\n",Sum(R,L-1)-Sum(L-1,L-1));
        }
    }
    return 0;
}