感觉写堆全是用priority_queue有点虚

来两道可并堆吧

BZOJ-4003

可并堆写起来比较方便吧QAQ

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define LL long long
#define MM 300005
using namespace std;
int n,m,st,tot=0,head[MM];
struct Q {	int ans; LL s;}q[MM];
struct C { int f,a,ans,root; LL h,v;}c[MM];
struct Edge{ int ne,v;}e[MM<<2];
struct T { int aa,ans,l,r,dis,root,id; LL add,mul,v;}a[MM];
void Read(LL &xx)
{
	bool f=0; char CH;
	for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
	for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
}
void read(int &xx)
{
	bool f=0; char CH;
	for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
	for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
}
void Build(int xx,int yy) {e[++tot].ne=head[xx], e[tot].v=yy, head[xx]=tot;}
void Modify(int xx,int aa,LL mul,LL add)
{
	if (!aa && !add && mul==1) return;
	a[xx].aa+=aa, a[xx].ans+=aa, a[xx].v=a[xx].v*mul+add;
	a[xx].add=a[xx].add*mul+add, a[xx].mul*=mul;
}
void Push_down(int xx)
{
	int l=a[xx].l, r=a[xx].r;
	Modify(l,a[xx].aa,a[xx].mul,a[xx].add);
	Modify(r,a[xx].aa,a[xx].mul,a[xx].add);
	a[xx].aa=a[xx].add=0, a[xx].mul=1;
}
int Merge(int xx,int yy)
{
	if (!xx || !yy) return xx+yy;
	Push_down(xx), Push_down(yy);
	if (a[xx].v>a[yy].v) swap(xx,yy);
	a[xx].r=Merge(a[xx].r,yy);
	if (a[a[xx].l].dis<a[a[xx].r].dis) swap(a[xx].l,a[xx].r);
	a[xx].dis=a[a[xx].r].dis+1;
	return xx;
}
int Del(int xx) {	return Merge(a[xx].l,a[xx].r);}
void DFS(int xx,int fa)
{
	for (int i=head[xx];i;i=e[i].ne)
		DFS(e[i].v,xx), c[xx].root=Merge(c[xx].root,c[e[i].v].root);
	while (c[xx].root)
	{
		Push_down(c[xx].root);
		if (a[c[xx].root].v<c[xx].h)
		{
			c[xx].ans++;
			q[a[c[xx].root].id].ans=a[c[xx].root].ans;
			c[xx].root=Del(c[xx].root);
		}
		else break;
	}
	int r=c[xx].root;
	if (c[xx].a) a[r].v*=c[xx].v, a[r].mul*=c[xx].v, a[r].add*=c[xx].v;
	else a[r].v+=c[xx].v, a[r].add+=c[xx].v;
	a[r].ans++, a[r].aa++;
}
int main()
{
	read(n), read(m);
	for (int i=1;i<=n;++i) Read(c[i].h);
	for (int i=2;i<=n;++i) read(c[i].f), read(c[i].a), Read(c[i].v), Build(c[i].f,i);
	for (int i=1;i<=m;++i)
	{
		Read(q[i].s), read(st);
		a[i].root=i, a[i].v=q[i].s, a[i].mul=1, a[i].add=0, a[i].aa=0, a[i].ans=0, a[i].id=i;
		if (c[st].root) c[st].root=Merge(c[st].root,i); else c[st].root=i;
	}
	DFS(1,0);
	for (int i=1;i<=n;++i) printf("%d\n",c[i].ans);
	while (c[1].root)
	{
		Push_down(c[1].root);
		q[a[c[1].root].id].ans=a[c[1].root].ans;
		c[1].root=Del(c[1].root);
	}
	for (int i=1;i<=m;++i) printf("%d\n",q[i].ans);
	return 0;
}

BZOJ-2333

神奇的题号

本来好像是堆套堆。。用multiset弄掉一个。。跑过了就可以啦

详见 http://lujiaxin.is-programmer.com/posts/199317.html

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <set>
#include <ctime>
#define NN 300100
#define INF 0x3f3f3f3f;
using namespace std;
multiset <int> H;
int son[NN][3],val[NN],flag[NN],FLAG,root[NN],fa[NN],n,m,st[NN],top;
char ch[10];
void read(int &xx)
{
	bool f=0; char CH;
	for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
	for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
}
void push_down(int x)
{
	val[x]+=flag[x];
	if (son[x][0]) flag[son[x][0]]+=flag[x];
	if (son[x][1]) flag[son[x][1]]+=flag[x];
	flag[x]=0;
}
int Merge(int x,int y)
{
	push_down(x),push_down(y);
	if (val[x]<val[y]) swap(x,y);
	if ((x&&y)==0) return x;
	int d=rand()&1;
	son[x][d]=Merge(son[x][d],y);
	if (son[x][d]) fa[son[x][d]]=x; return x;
}
int Find(int xx){	return (xx==root[xx]?xx:(root[xx]=Find(root[xx]))); }
void Init(int n)
{
	val[0]=-INF;
	for (int i=1;i<=n;++i)	read(val[i]), H.insert(val[i]), root[i]=i;
}
void U()
{
	int x,y;
	read(x), read(y);
	int fx=Find(x), fy=Find(y);
	if (fx==fy) return;
	root[fx]=root[fy]=Merge(fx,fy);
	if (root[fx]==fx) H.erase(H.find(val[fy])); else H.erase(H.find(val[fx]));
}
void A1()
{
	int x,V,L,R,y;
	read(x), read(V);
	for (st[top=1]=x,y=fa[x];y;y=fa[y]) st[++top]=y;
	int head=st[top];
	H.erase(H.find(val[head]));
	while (top) push_down(st[top--]);
	val[x]+=V, y=fa[x];
	int k=(x==son[y][1]);
	son[y][k]=fa[x]=0, L=son[x][0], R=son[x][1];
	fa[L]=fa[R]=son[x][0]=son[x][1]=0;
	L=Merge(L,R);
	if (L) fa[L]=y;
	if (y) son[y][k]=L, L=head;
	root[L]=root[x]=root[head]=Merge(x,L), root[0]=0, push_down(root[x]), H.insert(val[root[x]]);
}
void A2()
{
	int x,y;
	read(x), read(y), H.erase(H.find(val[Find(x)]));
	flag[Find(x)]+=y, push_down(root[x]), H.insert(val[root[x]]);
}
void A3() {	int x;	read(x), FLAG+=x;}
void F1()
{
	int x,y;
	read(x), push_down(x);
	if (x==root[x])	{ printf("%d\n", val[x]+FLAG); return;	}
	for (st[top=1]=x,y=fa[x];y;y=fa[y]) st[++top]=y;
	while (top) push_down(st[top--]);
	printf("%d\n",val[x]+FLAG);
}
void F2()
{
	int x;
	read(x), push_down(Find(x)), printf("%d\n",val[root[x]]+FLAG);
}
void F3()
{
	multiset<int>::iterator it=H.end();
	printf("%d\n",(*(--it))+FLAG);
}
int main()
{ 
	srand(598562895);
	read(n), Init(n), read(m);
	while (m--)
	{
		scanf("%s",ch);
		if (ch[0]=='U') U();
		else if (ch[0]=='A' && ch[1]=='1') A1();
		else if (ch[0]=='A' && ch[1]=='2') A2();
		else if (ch[0]=='A' && ch[1]=='3') A3();
		else if (ch[0]=='F' && ch[1]=='1') F1();
		else if (ch[0]=='F' && ch[1]=='2') F2();
		else if (ch[0]=='F' && ch[1]=='3') F3();
	}
	return 0;
}