题解：P2266 爱的供养

· · 题解

？kruskal 重构树秒了。

直接建重构树，倍增找到子树大小合法的最深点，答案找到了。

时间复杂度单 log，做完了。

我没读错题吧？写一下等会挂了就好笑了。

绷不住了，重构树的非叶子是虚点，警钟长鸣。

#include<bits/stdc++.h>
#define ll long long
#define N 750005
using namespace std;
int kuai;
int a[N],b[N<<1];
int n,m,Q;
int ID(int x,int y){
    return (x-1)*m+y;
}
struct fish{
    int u,v,w;
};
bool cmp(fish x,fish y){
    return x.w<y.w;
}
vector<fish>ev;
int fa[N<<1];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
vector<int>ve[N<<1];
ll f[N<<1];
int l[N<<1];
int r[N<<1];
int dfn[N<<1],dfnn;
int ta[N<<1],ta2[N<<1];
int fath[25][N<<1];
int siz[N<<1];
void dfs(int x){
    dfn[x]=++dfnn;
    ta2[dfnn]=ta[dfnn]=b[x];
    l[x]=dfnn;
    for(int i:ve[x])dfs(i),fath[0][i]=x,siz[x]+=siz[i];
    r[x]=dfnn;
}
int ans[N<<1];
struct que{
    int l,r,t,id;
};
struct update{
    int id,x,y;
};
bool pmc(que x,que y){
    if(x.l/kuai!=y.l/kuai)return x.l<y.l;
    if(x.r/kuai!=y.r/kuai)return x.r<y.r;
    return x.t<y.t;
}
int t[N];
int flc;
void ins(int x){
    if(x<=0)return;
    if(t[x]==0)flc++;
    t[x]++;
}
void del(int x){
    if(x<=0)return;
    t[x]--;
    if(t[x]==0)flc--;
}
int L=1,R=0,T=0;
void Upd(update x){
    if(x.id>=L&&x.id<=R){
        del(x.x);
        ins(x.y);
    }
    ta[x.id]=x.y;
}
signed main(){
    int twt;
    cin>>n>>m>>twt;
    int nn=n,mm=m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        int id=ID(i,j);
        cin>>a[id];
        siz[id]=1;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        int id=ID(i,j);
        b[id]=id;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<m;j++)
    ev.push_back({ID(i,j),ID(i,j+1),abs(a[ID(i,j)]-a[ID(i,j+1)])});
    for(int i=1;i<n;i++)
    for(int j=1;j<=m;j++)
    ev.push_back({ID(i,j),ID(i+1,j),abs(a[ID(i,j)]-a[ID(i+1,j)])});
    sort(ev.begin(),ev.end(),cmp);
    n=n*m;
    for(int i=1;i<=n+n;i++)fa[i]=i;
    for(int i=n+1;i<=n+n;i++)b[i]=-1;
    for(fish i:ev){
        if(find(i.u)==find(i.v))continue;
        i.u=find(i.u);
        i.v=find(i.v);
        n++;
        ve[n].push_back(i.u);
        ve[n].push_back(i.v);
        fa[i.u]=n;
        fa[i.v]=n;
        f[n]=i.w;
    }
    dfs(n);
    for(int i=1;i<=20;i++)
    for(int j=1;j<=n;j++)
    fath[i][j]=fath[i-1][fath[i-1][j]];
    ll ret=0;
    n=nn,m=mm;
    for(int x=1;x<=n;x++)
    for(int y=1;y<=m;y++){
        int op;
        cin>>op;
        if(!op)continue;
        int id=ID(x,y);
        for(int j=20;j>=0;j--)
        if(fath[j][id]&&siz[fath[j][id]]<twt)
        id=fath[j][id];
        if(siz[id]<twt)
        id=fath[0][id];
        ret+=f[id];
    }
    cout<<ret;
    return 0;
}
// 那已经是很久之前发生的事了。
// 理由什么的已经无关紧要了吧。

// 人是不会为了无关紧要的事情拼上性命的。

// 老夫只是在守护妻子最爱的村子。

// 我妻子是人类。
// 老夫只不过是一直在遵守着那个在遥远的过去许下的承诺罢了。

// 很可笑，对吧。
// 这么多年来，老夫只不过是一直在遵守着与死者的承诺罢了。

// 是这样呢。
// 不过，我觉得那个女性，一定会因为您一直守护着与她的约定，而由衷的感到开心。

// 辛美尔，你是一位优秀的勇者。
// 想必一定可以击败魔王吧。
// 老夫的妻子也一直期盼着魔王被击败，和平时代能够到来的那一天。
// 名为辛美尔的伟大勇者的回忆，就由老夫带去未来吧。

什么你问为啥代码里有一车和一位的东西？问就是，从双倍经验粘的。

什么，你问的是注释？那你猜。