【模板库】斜堆

参考题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2809
参考代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;

LL vout;
int led[N],n,m,arr[N],rt;
vector<int> G[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

namespace Skew_Heap{
	#define SHP Skew_Heap
	int ch[N][2],sz[N],val[N],root[N],cnt;
	LL sum[N];
	
	inline void maintain(int w) {
		sz[w] = sz[ch[w][0]] + sz[ch[w][1]] + 1;
		sum[w] = sum[ch[w][0]] + sum[ch[w][1]] + val[w];
	}
	
	int Merge(int a, int b){
		if (!a || !b) return a+b;
		else {
			if (val[b] > val[a]) swap(a,b);
			ch[a][1] = Merge(ch[a][1],b);
			swap(ch[a][0],ch[a][1]); maintain(a); 
			return a;
		}
	}
	
	inline void pop(int w){
		root[w] = Merge(ch[root[w]][0],ch[root[w]][1]);
	}
	
	inline void insert(int w, int v){
		val[++cnt] = sum[cnt] = v; sz[cnt] = 1;
		root[w] = Merge(root[w],cnt);
	}
};

int main(){
	using namespace Skew_Heap;
	n = read(); m = read();
	for (int i=1,tmp;i<=n;i++) {
		G[read()].push_back(i);
		arr[i] = read(); led[i] = read();
	}
	for (int i=n;i;i--) {
		for (int j=0,lim=G[i].size();j<lim;j++) root[i] = Merge(root[i],root[G[i][j]]);
		insert(i,arr[i]); while (root[i] && sum[root[i]] > m) pop(i);
		vout = max(vout,(LL)sz[root[i]]*led[i]);
	} 
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 2809】[Apio2012] dispatching

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2809

我是来练习斜堆的 = ̄ω ̄=

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;

LL vout;
int led[N],n,m,arr[N],rt;
vector<int> G[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

namespace Skew_Heap{
	#define SHP Skew_Heap
	int ch[N][2],sz[N],val[N],root[N],cnt;
	LL sum[N];
	
	inline void maintain(int w) {
		sz[w] = sz[ch[w][0]] + sz[ch[w][1]] + 1;
		sum[w] = sum[ch[w][0]] + sum[ch[w][1]] + val[w];
	}
	
	int Merge(int a, int b){
		if (!a || !b) return a+b;
		else {
			if (val[b] > val[a]) swap(a,b);
			ch[a][1] = Merge(ch[a][1],b);
			swap(ch[a][0],ch[a][1]); maintain(a); 
			return a;
		}
	}
	
	inline void pop(int w){
		root[w] = Merge(ch[root[w]][0],ch[root[w]][1]);
	}
	
	inline void insert(int w, int v){
		val[++cnt] = sum[cnt] = v; sz[cnt] = 1;
		root[w] = Merge(root[w],cnt);
	}
};

int main(){
	using namespace Skew_Heap;
	n = read(); m = read();
	for (int i=1,tmp;i<=n;i++) {
		G[read()].push_back(i);
		arr[i] = read(); led[i] = read();
	}
	for (int i=n;i;i--) {
		for (int j=0,lim=G[i].size();j<lim;j++) root[i] = Merge(root[i],root[G[i][j]]);
		insert(i,arr[i]); while (root[i] && sum[root[i]] > m) pop(i);
		vout = max(vout,(LL)sz[root[i]]*led[i]);
	} 
	printf("%lld\n",vout);
	return 0;
}