题解：P13084 [NOISG 2017] I want to be the very best too! / 宝可梦大师
语文神题
P13084
转换题意：
- 给定一个网格
R 行C 列的网格，每个点有权值L_{i,j} 与颜色P_{i,j} ，相邻格子权值高的向权值低的连边形成树T ，给定T 上一点(X_p,Y_p) 求出子树内颜色个数。 - 单点修改节点颜色。
why 这道题目可以这样转换？
我们可以给每个点
其次每次走的方向是四周权值比当前格低的，如果我们按照权值大小关系连边，那么最终连出来的将是一颗树，因为它总是不会连出一个环。
那么这启发我们使用克鲁斯卡尔重构树与倍增维护连通块点权最大点，具体实现为：
void kru() {
for(int t=1; t<=n; t++) {
int i=id[t];
for(int k=1; k<=4; k++) {
int xx=ID[i].fi+dx[k], yy=ID[i].se+dy[k];
if(xx<1||xx>r||yy<1||yy>c) continue;
int fv=find(com(xx,yy));
if(L[fv]>L[i] || i==fv) continue;
g[i].push_back(fv);
fa[fv]=i;
}
}
}
void dfs(int u,int f) {
fat[0][u]=f;
dfn[u]=++dfn_cnt;
siz[u]=1;
for(int i=1; i<=20; i++) fat[i][u]=fat[i-1][fat[i-1][u]];
for(int v:g[u]) if(v!=f) dfs(v,u), siz[u]+=siz[v];
}
int jump(int u,int lim) {
for(int i=20; i>=0; i--) if(fat[i][u] && L[fat[i][u]]<=lim) u=fat[i][u];
return u;
}然后问题就美美转化为了单点修改，查询子树内颜色个数（因为你可以回走到你走到过的点）。
然后子树 dfs 序是一个序列，可以使用带修莫队直接解决，或者选择二维数点，这里提供一个树套树二维数点的解法。
CODE：
#include<bits/stdc++.h>
using namespace std;
#define N 300010
#define pi pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define int long long
int r,c,q,n;
int com(int i,int j) { return (i-1)*c+j; }
pi ID[N];
int id[N],rt;
int fa[N],L[N],p[N];
bool cmp(int x,int y) { return L[x]<L[y]; }
int dx[5]={0,0,0,1,-1}, dy[5]={0,1,-1,0,0};
int find(int x) {
while(x!=fa[x]) x=fa[x]=fa[fa[x]];
return x;
}
vector<int> g[N];
void kru() {
for(int t=1; t<=n; t++) {
int i=id[t];
for(int k=1; k<=4; k++) {
int xx=ID[i].fi+dx[k], yy=ID[i].se+dy[k];
if(xx<1||xx>r||yy<1||yy>c) continue;
int fv=find(com(xx,yy));
if(L[fv]>L[i] || i==fv) continue;
g[i].push_back(fv);
fa[fv]=i;
}
}
}
int fat[21][N],dfn[N],siz[N],dfn_cnt;
int w[N];
void dfs(int u,int f) {
fat[0][u]=f;
dfn[u]=++dfn_cnt;
siz[u]=1;
for(int i=1; i<=20; i++) fat[i][u]=fat[i-1][fat[i-1][u]];
for(int v:g[u]) if(v!=f) dfs(v,u), siz[u]+=siz[v];
}
int jump(int u,int lim) {
for(int i=20; i>=0; i--) if(fat[i][u] && L[fat[i][u]]<=lim) u=fat[i][u];
return u;
}
const int MAXC = 80010;
set<int> col_pos[MAXC];
int pre[N], col_at[N];
int len = dfn_cnt;
int bit_rt[N];
int seg_tot;
struct SegNode {
int ls, rs, v;
} seg[N*100];
inline void seg_chg(int &u, int l, int r, int k, int x) {
if(!u) u = ++seg_tot;
seg[u].v += x;
if(l == r) return;
int mid = (l+r)>>1;
if(k <= mid) seg_chg(seg[u].ls, l, mid, k, x);
else seg_chg(seg[u].rs, mid+1, r, k, x);
}
inline int seg_sum(int u, int l, int r, int ql, int qr) {
if(!u || ql>r || qr<l) return 0;
if(ql<=l && r<=qr) return seg[u].v;
int mid = (l+r)>>1;
return seg_sum(seg[u].ls, l, mid, ql, qr) + seg_sum(seg[u].rs, mid+1, r, ql, qr);
}
struct BIT {
inline int lb(int x) { return x&(-x); }
inline void add(int x, int y, int val) {
for(int i=x; i<=dfn_cnt; i+=lb(i))
seg_chg(bit_rt[i], 1, dfn_cnt, y, val);
}
inline int sum(int x, int y) {
int res=0;
for(int i=x; i; i-=lb(i))
res += seg_sum(bit_rt[i], 1, dfn_cnt, 1, y);
return res;
}
inline int range(int l, int r, int y) {
return sum(r, y) - sum(l-1, y);
}
} tre;
void insert_color(int pos, int c) {
auto s = col_pos[c];
auto it = s.lower_bound(pos);
int pre_pos = (it!=s.begin()) ? *prev(it) : 0;
int nxt_pos = (it!=s.end()) ? *it : 0;
if(nxt_pos) {
tre.add(nxt_pos, pre[nxt_pos], -1);
pre[nxt_pos] = pos;
tre.add(nxt_pos, pre[nxt_pos], 1);
}
pre[pos] = pre_pos;
tre.add(pos, pre[pos], 1);
s.insert(pos);
}
void erase_color(int pos, int c) {
auto s = col_pos[c];
auto it = s.find(pos);
if(it==s.end()) return;
auto nxt = next(it);
auto prv = (it!=s.begin()) ? prev(it) : s.end();
tre.add(pos, pre[pos], -1);
if(nxt != s.end()) {
int nxt_pos = *nxt;
tre.add(nxt_pos, pre[nxt_pos], -1);
pre[nxt_pos] = (prv!=s.end()) ? *prv : 0;
tre.add(nxt_pos, pre[nxt_pos], 1);
}
s.erase(it);
}
int read() {
int x=0,k=1; char ch=getchar();
while(!isdigit(ch)) { if(ch=='-')k=-1; ch=getchar(); }
while(isdigit(ch)) { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x*k;
}
signed main() {
r=read(),c=read(),q=read();
n=r*c;
L[0]=1e18;
for(int i=1; i<=r; i++) for(int j=1; j<=c; j++) {
int u=com(i,j);
ID[u]={i,j};
L[u]=read();
fa[u]=id[u]=u;
}
sort(id+1,id+n+1,cmp);
for(int i=1; i<=n; i++) p[i]=read();
kru();
for(int i=1;i<=n;i++) if(find(i)==i) {
g[0].push_back(i);
fa[i]=0;
}
rt=0;
dfs(rt,0);
for(int i=1; i<=n; i++) {
int pos = dfn[i];
int color = p[i];
col_at[pos] = color;
insert_color(pos, color);
}
for(int i=1;i<=q;i++) {
int op=read(),x=read(),y=read(),v=read();
int u=com(y,x);
if(op==1) {
int pos = dfn[u];
int oldc = col_at[pos];
if(oldc != v) {
erase_color(pos, oldc);
insert_color(pos, v);
col_at[pos] = v;
}
} else {
if(L[u] > v) puts("0");
else {
int t = jump(u, v);
int l = dfn[t], r = dfn[t]+siz[t]-1;
printf("%lld\n", tre.range(l, r, l-1));
}
}
}
}