在我的心脏停止跳动之前,我依然想继续守护着你 ——《心拍数#0822》

题目背景:

四季映姬·亚玛萨那度(以下简称四季大人)是地狱的最高裁判长。

她平时负责给死者定罪,判断让死者去地狱还是天界,或者别的什么地方。

四季大人当然可以轻松地给死者断罪,但是死者太多了,四季大人需要你帮她断罪,以便腾出时间让她对别人进行说教。


题意描述:

人们的罪恶值$E$由人们生前所做过的事和他的死亡方式来决定.他们做过的坏事都会有一个罪恶值,

这些坏事有可能会并入同一个集合,一个集合的罪恶值为该集合中罪恶值最大的坏事的罪恶值,

而他们一生做过的事会互相影响,我们将他们生前做过的事分为4种,而最后的罪恶值$E$由其中所有集合的罪恶值的和决定。

1.做坏事——有罪恶值,单独为一集合。  

2.做好事——将一件坏事的罪恶值清零。

3.忏悔——将指定集合中,最大罪恶值的事罪恶值减少。

4.认清自己——将两个坏事集合合并。

而死亡方式可分为 自然死亡 、事故死亡 和 自杀 。

1.自然死亡,没什么影响。

2.事故死亡,可以免除最大罪恶的坏事集合。

3.自杀,最大的坏事集合罪恶值翻倍。

输入格式:

第一行三个输入$T$ , $W$ , $K$,代表有$T$个人等待断罪,$W$为死亡方式,与描述序号对应,$K$含义见输出格式。

接下来的$T$组数据, 每组数据第一行两个输入$n$ ,$m$,代表他做过的坏事数量和其他事的数量。

第二行$n$个输入,代表每件坏事的罪恶值。

第3到第$m+2$行,每行有三种输入可能。(请联系题目描述进行理解)
$2$ $A$ 表示做好事,将坏事$A$罪恶值清零 。
$3$ $A$ $B$ 表示忏悔,指定集合为$A$所在的集合,最大罪恶值的事减少$B$,若最大罪恶值比$B$小,则最大罪恶值的事罪恶值清零。
$4$ $A$ $B$ 表示认清自己,将$B$所在集合与$A$所在的集合合并。


输出格式:

对于每一个人,一行输出

若他的罪恶值为$0$则输出$Gensokyo$,

若他的罪恶值大于$K$则输出$Hell$,

否则输出$Heaven$

之后输出它的罪恶值


Input & Output ‘s examples

Input ‘s eg 1

1 1 10
5 2
1 2 3 4 5
2 3
4 2 4

Output ‘s eg 1

Heaven 10

Input ‘s eg 2

2 2 8
5 4
4 8 7 5 6
4 2 4
2 2
4 2 3
3 3 2
3 2
5 1 2
2 2
3 3 2

Output ‘s eg 2

Hell 9
Gensokyo 0

Input ‘s eg 3

2 1 15
5 4
1 2 3 4 5
4 2 3
3 2 100
4 1 4
4 4 1
5 4
1 2 3 4 5
3 2 15
4 2 3
4 1 4
4 3 4

Output ‘s eg 3

Heaven 11
Heaven 9

数据范围和约定

所有数据均在长整型范围内,对于所有数据,均有$m\le nm≤n,1\le K1≤K$,保证输入不存在负数。

由于读入数据可能会很大,建议使用较快的读入。

约定① 对于合并两个集合的操作,至少有一个集合只有一件坏事

约定② 这群人不会做好事

mSzmCQ.jpg


分析

一道毒瘤数据结构题

首先我们简化一下题意

给你$n$个集合与三种操作,操作如下

  1. 单点修改——将指定集合中的某个元素清零
  2. 维护最值——将指定集合中的最大值减少
  3. 合并——合并两个集合。

下面,我们就来看一下各种分数的做法


30分做法

不难看出,第二个操作可以用优先队列轻易实现,而数据中正好有6个点没有1,3操作。

于是我们可以用STL的优先队列模拟这个过程,最后加起来即可。


60分做法

写过30分做法之后,我们就要尝试实现单点修改。

但STL中的优先队列不支持单点修改啊

那怎么办?

手写堆呗QAQ

我们可以通过手写堆来模拟这个过程,但由于我们不确定每个堆的大小,因此不能直接开2000000个堆,要用链表实现或数组模拟

这样我们就可以过掉所有满足特殊约定的点。

对于不满足特殊约定的点也可以暴力合并,但时间复杂度极高,为$O((n1+n2)log(n1+n2))$ 。

因此,我们需要想办法优化我们的合并操作


满分做法

那我们该怎么优化我们的合并操作呐?

在这里,我们引入一个新的数据结构:左偏树

左偏树是一种具有左偏性质的堆状二叉树,因此优先队列的操作都可以中左偏树实现。

而且左偏树具有十分强大的合并操作,可以在$O(nlogn)$的时间复杂度下合并两个优先队列。

想了解左偏树的同学们请点击这里O(≧▽≦)O

学过之后你会发现这是一道模板题……直接修改一下pop操作就过啦


Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<iomanip>
#include<cstdlib>
#include<cmath>

#define N 2000001
#define ll long long
#define int long long

using namespace std;

int tem;

namespace Left_tree{
struct Node{
int pre;
int left;
int right;
int dis;
int far;
}node[N];

int find(int root){
if(node[root].pre == root){
return root;
}
else{
return node[root].pre = find(node[root].pre);
}
}

int merge(int x , int y){
if(!x || !y){
return x + y ;
}
if(node[x].dis < node[y].dis){
swap(x , y);
}
node[x].right = merge(node[x].right , y);
node[node[x].right].pre = x;
node[x].far = (node[x].right == 0) ? 0 : node[node[x].right].far + 1;
if(node[node[x].left].far < node[node[x].right].far){
swap(node[x].left , node[x].right);
}
return x;
}

/*
void pop(int x){
int l = node[x].left;
int r = node[x].right;
node[x].dis = 0;
node[l].pre = l;
node[r].pre = r;
node[x].pre = merge(l , r);
}
*/

void Delete(const int &A , const int &dis , bool flag){
node[A].dis -= dis;
if(node[A].dis < 0){
node[A].dis = 0;
}
node[node[A].left].pre = node[A].left;
node[node[A].right].pre = node[A].right;
int l = node[A].left;
int r = node[A].right;
node[A].left = node[A].right = node[A].far = 0;
tem = merge(l , r);
if(flag){
merge(find(A) , tem);
}
else{
merge(tem , A);
}
}
}

using namespace Left_tree;

ll t , w , k;
ll n , m;
ll opt , A , B;
bool vis[N];


signed main(){
scanf("%d%d%d" , &t , &w , &k);
while(t --){
scanf("%d%d" , &n , &m);
for(int i = 1; i <= n; i ++){
node[i].pre = i;
scanf("%d" , &node[i].dis);
node[i].left = node[i].right = node[i].far = 0;
vis[i] = false;
}
for(int i = 1; i <= m; i ++){
scanf("%d%d" , &opt , &A);
if(opt == 2){
Delete(A , node[A].dis , true);
}
if(opt == 3){
scanf("%d" , &B);
Delete(find(A) , B , false);
}
if(opt == 4){
scanf("%d", &B);
merge(find(A) , find(B));
}
}
ll ans = 0;
B = 0;
for(int i = 1; i <= n; i ++){
A = find(i);
if(!vis[A]){
vis[A] = true;
B = max(B , node[A].dis);
ans += node[A].dis;
}
}
if(w == 2){
ans -= B;
}
else if(w == 3){
ans += B;
}
if(ans == 0){
printf("Gensokyo ");
}
else if((ll)ans <= k){
printf("Heaven ");
}
else{
printf("Hell ");
}
printf("%d\n" , ans);
}
return 0;
}

THE END