在我的心脏停止跳动之前，我依然想继续守护着你 ——《心拍数#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 |
Output ‘s eg 1
Heaven 10 |
Input ‘s eg 2
2 2 8 |
Output ‘s eg 2
Hell 9
Gensokyo 0
Hell 9 |
Input ‘s eg 3
2 1 15 |
Output ‘s eg 3
Heaven 11 |
数据范围和约定
所有数据均在长整型范围内，对于所有数据，均有$m\le nm≤n,1\le K1≤K$，保证输入不存在负数。
由于读入数据可能会很大，建议使用较快的读入。
约定① 对于合并两个集合的操作，至少有一个集合只有一件坏事
约定② 这群人不会做好事
分析
一道毒瘤数据结构题
首先我们简化一下题意
给你$n$个集合与三种操作，操作如下
- 单点修改——将指定集合中的某个元素清零
- 维护最值——将指定集合中的最大值减少
- 合并——合并两个集合。
下面，我们就来看一下各种分数的做法
30分做法
不难看出，第二个操作可以用优先队列轻易实现，而数据中正好有6个点没有1，3操作。
于是我们可以用STL的优先队列模拟这个过程，最后加起来即可。
60分做法
写过30分做法之后，我们就要尝试实现单点修改。
但STL中的优先队列不支持单点修改啊
那怎么办？
手写堆呗QAQ
我们可以通过手写堆来模拟这个过程，但由于我们不确定每个堆的大小，因此不能直接开2000000个堆，要用链表实现或数组模拟
这样我们就可以过掉所有满足特殊约定的点。
对于不满足特殊约定的点也可以暴力合并，但时间复杂度极高，为$O((n1+n2)log(n1+n2))$ 。
因此，我们需要想办法优化我们的合并操作
满分做法
那我们该怎么优化我们的合并操作呐？
在这里，我们引入一个新的数据结构:左偏树
左偏树是一种具有左偏性质的堆状二叉树，因此优先队列的操作都可以中左偏树实现。
而且左偏树具有十分强大的合并操作，可以在$O(nlogn)$的时间复杂度下合并两个优先队列。
想了解左偏树的同学们请点击这里Ｏ(≧▽≦)Ｏ
学过之后你会发现这是一道模板题……直接修改一下pop操作就过啦
Code
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;
}
|
