Pluto_Rabbit's Blog

蒟蒻妹纸一枚,轻拍

【学习】可并堆

Jacinth posted @ 2016年4月20日 10:15 in Lerning with tags 学习 算法 Learning BZOJ 可并堆 , 784 阅读

感觉写堆全是用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;
}
Avatar_small
AP SSC Maths Model P 说:
2022年9月19日 01:02

Mathematics is one of the tough subjects and also an easy subject for class 10th standard students of TM, EM, AP SSC Maths Model Paper UM and HM studying at government and private schools of the state. Department of School Education and teaching staff of various institutions have designed and suggested the Mathematics question paper with solutions for all chapters topic wide for each lesson of the course, and the AP SSC Maths Model Paper 2023 Pdf designed based on the new revised syllabus and curriculum.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter