题解：P13084 [NOISG 2017] I want to be the very best too! / 宝可梦大师
2026.5.12 upd：代码都没放代码框里也能过审啊，修了一下。
调试能力是棍木。
还以为是直接忽略掉起点的人，调了一个小时告诉我起点的人也要打（）。
首先这个修改操作我们发现只改颜色不改等级，于是直接建出 Kruskal 重构树。具体的把每个点按
于是数颜色成了在重构树的一颗子树上数。转化到 dfn 序上，变成区间数颜色单点改，直接跑带修莫队就行了。
代码并不难写，没读题调试棍木才是最难点。
::::success[code] /*
——我们的时间，就这样开始了。
海风吹拂着面颊……纯白色的羽毛从天空中降下。
我们手牵着手仰望着天空，立下要去恋爱的誓言————
*/
#include<bits/stdc++.h>
//#pragma GCC optimize(1,2,3,"Ofast","inline")
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define fi first
#define se second
#define inf 2000000000
#define mod 998244353
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
int n,m,q;
int dx[5]={0,0,0,-1,1},dy[5]={0,1,-1,0,0};
#define w(x,y) (x-1)*m+y
int L[200010],P[200010];
int p[200010];
int a[200010];
struct node{int L,x,y;}d[200010];
inline bool cmpd(node x,node y){return x.L<y.L;}
int h;
int LL[200010],RR[200010];
int fa[200010],ff[200010];
int fb[200010][31];
int son[200010][2];
inline int find(int x){
if(ff[x]==x)return x;
return ff[x]=find(ff[x]);
}
inline void bing(int x,int y){
x=find(x),y=find(y);
ff[x]=y;
}
int s[200010];
int cnt,dfn[200010];
inline void dfs(int x){
fb[x][0]=fa[x];
for(int i=1;i<=19;i++)fb[x][i]=fb[fb[x][i-1]][i-1];
dfn[x]=++cnt;
p[cnt]=x;
a[cnt]=P[x];
LL[x]=cnt;
RR[x]=cnt;
if(x<=h)return ;
dfs(son[x][0]);dfs(son[x][1]);
RR[x]=cnt;
return ;
}
inline int fqry(int x,int k){
for(int i=19;i>=0&&x!=2*h-1;i--)if(L[fb[x][i]]<=k)x=fb[x][i];
return x;
}
int lq,lc;
int ans[200010];
int B,bel[200010];
struct C{int x,y,z;}c[200010];
struct Q{int o,l,r,t,id,qwq;}qs[200010];
inline bool cmpQ(Q x,Q y){
if(bel[x.l]!=bel[y.l])return x.l<y.l;
if(bel[x.r]!=bel[y.r]){
if(bel[x.l]&1)return x.r>y.r;
return x.r<y.r;
}
if(bel[x.l]&1)return x.t>y.t;
return x.t<y.t;
}
int pp[200010];
int sum=0;
int l=1,r=0,t=0;
inline void add(int x){
if(p[x]>h)return ;
if(!s[a[x]])sum++;
s[a[x]]++;
}
inline void del(int x){
if(p[x]>h)return ;
s[a[x]]--;
if(!s[a[x]])sum--;
}
inline void addt(){
int x=c[t].x,y=c[t].y;
if(l<=x&&x<=r){
// cout<<l<<" "<<r<<'\n';
s[a[x]]--;
if(!s[a[x]])sum--;
a[x]=y;
if(!s[a[x]])sum++;
s[a[x]]++;
}
a[x]=y;
}
inline void delt(){
int x=c[t].x,y=c[t].z;
if(l<=x&&x<=r){
// cout<<l<<" "<<r<<'\n';
s[a[x]]--;
if(!s[a[x]])sum--;
a[x]=y;
if(!s[a[x]])sum++;
s[a[x]]++;
}
a[x]=y;
}
signed main(){
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x=read();
L[w(i,j)]=x;
d[++h]={x,i,j};
}
}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)P[w(i,j)]=read(),pp[w(i,j)]=P[w(i,j)];
sort(d+1,d+h+1,cmpd);
for(int i=1;i<2*h;i++)fa[i]=i,ff[i]=i;
int cnt=h;
for(int i=1;i<=h;i++){
int x=d[i].x,y=d[i].y;
for(int j=4;j>=1;j--){
int xx=x+dx[j],yy=y+dy[j];
if(xx==0||xx==n+1||yy==0||yy==m+1)continue;
int u=find(w(x,y)),v=find(w(xx,yy));
if(u!=v&&L[w(x,y)]>=L[w(xx,yy)]){
++cnt;
fa[u]=fa[v]=cnt;
son[cnt][0]=u,son[cnt][1]=v;
L[cnt]=L[w(x,y)];
bing(u,cnt);bing(v,cnt);
if(cnt==2*h-1)break;
}
}
if(cnt==2*h-1)break;
}
dfs(2*h-1);
for(int i=1;i<=q;i++){
int opt=read();
int xx=read(),yy=read(),y=read();
int x=w(yy,xx);
if(opt==1){
c[++lc]={dfn[x],y,pp[x]};
// cout<<"QwQ "<<x<<" "<<y<<" "<<pp[x]<<'\n';
pp[x]=y;
}
else {
int o=x;
x=fqry(x,y);
qs[++lq]={o,LL[x],RR[x],lc,lq,y};
}
}
B=sqrt(h*2-1);
for(int i=1;i<=h*2-1;i++)bel[i]=(i-1)/B+1;
sort(qs+1,qs+lq+1,cmpQ);
for(int i=1;i<=lq;i++){
while(l>qs[i].l)l--,add(l);
while(r<qs[i].r)r++,add(r);
while(l<qs[i].l)del(l),l++;
while(r>qs[i].r)del(r),r--;
while(t<qs[i].t)t++,addt();
while(t>qs[i].t)delt(),t--;
if(L[qs[i].o]>qs[i].qwq)ans[qs[i].id]=0;
else ans[qs[i].id]=sum;
}
for(int i=1;i<=lq;i++)cout<<ans[i]<<'\n';
return 0;
}::::