P4971 断罪者

· · 题解

题目修改， 更新题解

原题链接

浏览这道题，可以看到几个关键词，“ 最大罪恶值 ”，“ 集合 ”，“ 合并 ”。 所以很容易联想到 堆 ， 平衡树 等结构。 再考虑数据范围 T≤10，n≤2*10^6 ,时间限制 1.00s ~ 2.00s .(常数大的平衡树果断排除）。

考虑 nlogn 的 可并堆 ，最常见的可并堆是 左偏树 ，lg 也有专门的 模板题，所以我们选择左偏树 。

1.合并

代码：

int merge(int x,int y){
    if(!x||!y)return x+y
    if(val[x]<val[y])swap(x,y);
    r[x]=merge(r[x],y);if(dis[l[x]]<dis[r[x]])swap(l[x],r[x]);
    fa[l[x]]=fa[r[x]]=fa[x]=x,dis[x]=dis[r[x]]+1;
    return x;
}

2.删除

敲重点

在P3377中，我们使用的是 Pop（仅删除堆顶），但这里是 Extract（支持删除堆中任意节点）。

具体实现见代码：

inline void extract(register int x){
    register int L=l[x],R=r[x];
    fa[L]=L,fa[R]=R,l[x]=r[x]=dis[x]=0;
    merge(merge(L,R),get(x));//合并x节点的两个儿子，和它所在集合代表元素。
}

这样操作你就会发现 x 节点不见了。

接下来就是简单模拟了。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 2000100
using namespace std;
int t,m,n,w;
bool v[maxn]; 
int fa[maxn],l[maxn],r[maxn],dis[maxn];
long long k,val[maxn];
inline int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(val[x]<val[y]||val[x]==val[y]&&x>y)swap(x,y);
    r[x]=merge(r[x],y);if(dis[l[x]]<dis[r[x]])swap(l[x],r[x]);
    fa[l[x]]=fa[r[x]]=fa[x]=x,dis[x]=dis[r[x]]+1;
    return x;
}
inline void extract(register int x){
    register int L=l[x],R=r[x];
    fa[L]=L,fa[R]=R,l[x]=r[x]=dis[x]=0;
    merge(merge(L,R),get(x));
}
inline void clear(){
    fa[0]=dis[0]=l[0]=r[0]=0;
    memset(v,0,sizeof(v));
}
int main(){
    scanf("%d%d%d",&t,&w,&k);
    while(t--){
        clear(); 
        scanf("%d%d",&n,&m);
        for(register int i=1;i<=n;i++){
            scanf("%lld",&val[i]);
            fa[i]=i,r[i]=l[i]=dis[i]=0;
        }
        while(m--){
            register int f,a,b;
            scanf("%d",&f);
            if(f==2){scanf("%d",&a);val[a]=0;extract(a);}
            else if(f==3){scanf("%d%d",&a,&b);a=get(a);val[a]-=val[a]>b?b:val[a];extract(a);}
            else{
                scanf("%d%d",&a,&b);a=get(a);b=get(b);
                if(a==b)continue;
                merge(a,b);
            }
        }
        long long sum=0,cmax=0;
        for(int i=1;i<=n;i++){
            register int root=get(i);
            if(v[root])continue;v[root]=1;
            cmax=max(cmax,val[root]);
            sum+=val[root];
        }
        if(w==2)sum-=cmax;
        if(w==3)sum+=cmax;
        if(sum==0)printf("Gensokyo 0\n");
        else if(sum<=k)printf("Heaven %lld\n",sum);
        else printf("Hell %lld\n",sum);
    }
    return 0;
}

数组存左偏树，码风可能比较特别，请见谅