可并堆 | OceanEye's Blog

@OceanEye7年前

08/3

11:38

BZOJ1367 [Baltic2004]sequence

OceanEye 撰写可并堆无回复

1367: [Baltic2004]sequence

Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 1346 Solved: 550
[Submit][Status][Discuss]

Description

Input

Output

一个整数R

Sample Input

7
9
4
8
20
14
15
18

Sample Output

HINT

所求的Z序列为6,7,8,13,14,15,18.
R=13

Source

[Submit][Status][Discuss]这题很神……左偏树论文题百度文库有论文【之前我的左偏树也有挂过】
论文看不是很懂的可以去看看徐姥爷的题解
打错一个下划线wa N次，心痛一波ac率

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <queue>
#define ll long long
#define INF 1000000000

#define For(i,a,b) for(int i=a;i<=b;++i)

#define  p(x) ('0'<=x&&x<='9')
char cc; int C;
template <class T>
void read( T &x )
{
	x=0; C=1; cc=getchar();
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}
#undef p
using namespace std;

#define N 1000010

struct node
{
	int c[2],val,dep;
	node() { c[0]=c[1]=val=0; dep=1; }
	int& operator [] (const int &x) { return c[x]; }
}pool[N];
queue<int> q;
int root[N],siz[N],_siz[N],tot,pcnt;
int merge(int x,int y)
{
	if(!x||!y) return (x+y);
	if(pool[x].val<pool[y].val) swap(x,y);
	pool[x][1]=merge(pool[x][1],y);
	if(pool[pool[x][0]].dep<pool[pool[x][1]].dep) swap(pool[x][1],pool[x][0]);
	pool[x].dep=pool[pool[x][1]].dep+1;
	return x;
}
int pop(int &x) { q.push(x); x=merge(pool[x][0],pool[x][1]); }
int getpt()
{
	static int ret;
	if( q.empty() ) ret=++pcnt;
	else { ret=q.front(); q.pop(); };
	pool[ret]=node();
	return ret;
}
int z[N],n,w[N];
ll ans;

void init()
{
	while(!q.empty()) q.pop();
	read(n);
	For(i,1,n) read(z[i]),z[i]-=i;
	pool[0].dep=0;
}

int main()
{
	int node=1;
	init();
	For(i,1,n)
	{
		root[++tot]=getpt(); pool[root[tot]].val=w[tot]=z[i];
		siz[tot]=_siz[tot]=1;
		while(w[tot]<w[tot-1]&&tot>1)
		{
			root[tot-1]=merge(root[tot-1],root[tot]);
			siz[tot-1]+=siz[tot]; _siz[tot-1]+=_siz[tot];
			tot--;
			while(_siz[tot] != (siz[tot]>>1)+(siz[tot]&1)) pop(root[tot]),_siz[tot]--;
			w[tot]=pool[root[tot]].val;
		}
	}
	For(i,1,tot)
	{
		for(;siz[i];siz[i]--) ans+=abs(z[node++]-w[i]);
	}
	printf("%lld",ans);
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <iostream>

#include <cstdlib>

#include <cmath>

#include <queue>

#define ll long long

#define INF 1000000000

#define For(i,a,b) for(int i=a;i<=b;++i)

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; C=1; cc=getchar();

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

#undef p

using namespace std;

#define N 1000010

struct node

{

int c[2],val,dep;

node() { c[0]=c[1]=val=0; dep=1; }

int& operator [] (const int &x) { return c[x]; }

}pool[N];

queue<int> q;

int root[N],siz[N],_siz[N],tot,pcnt;

int merge(int x,int y)

{

if(!x||!y) return (x+y);

if(pool[x].val<pool[y].val) swap(x,y);

pool[x][1]=merge(pool[x][1],y);

if(pool[pool[x][0]].dep<pool[pool[x][1]].dep) swap(pool[x][1],pool[x][0]);

pool[x].dep=pool[pool[x][1]].dep+1;

return x;

}

int pop(int &x) { q.push(x); x=merge(pool[x][0],pool[x][1]); }

int getpt()

{

static int ret;

if( q.empty() ) ret=++pcnt;

else { ret=q.front(); q.pop(); };

pool[ret]=node();

return ret;

}

int z[N],n,w[N];

ll ans;

void init()

{

while(!q.empty()) q.pop();

read(n);

For(i,1,n) read(z[i]),z[i]-=i;

pool[0].dep=0;

}

int main()

{

int node=1;

init();

For(i,1,n)

{

root[++tot]=getpt(); pool[root[tot]].val=w[tot]=z[i];

siz[tot]=_siz[tot]=1;

while(w[tot]<w[tot-1]&&tot>1)

{

root[tot-1]=merge(root[tot-1],root[tot]);

siz[tot-1]+=siz[tot]; _siz[tot-1]+=_siz[tot];

tot--;

while(_siz[tot] != (siz[tot]>>1)+(siz[tot]&1)) pop(root[tot]),_siz[tot]--;

w[tot]=pool[root[tot]].val;

}

For(i,1,tot)

{

for(;siz[i];siz[i]--) ans+=abs(z[node++]-w[i]);

}

printf("%lld",ans);

return 0;

}

BZOJ1367 [Baltic2004]sequence

@OceanEye7年前

04/23

15:45

BZOJ1455

OceanEye 撰写可并堆无回复

还是可并堆的题目……而且一如既往的很裸
合并，弹出都是log的复杂度
看代码吧……没什么细节但是我还是没有1A

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#define p(x) ('0'<=x&&x<='9')

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-')  C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;

#define N 1000010

struct node
{
	int lc,rc,val;
	int fa;
}pool[N];

int n,m;

#define Lc pool[x].lc
#define Rc pool[x].rc

int merge(int x,int y)
{
	if(!y) return x; if(!x) return y;
	if(pool[y].val<pool[x].val) swap(x,y);
	pool[x].rc=merge(y,pool[x].rc);
	pool[pool[x].rc].fa=x;
	return x;
}

int pop(int x)
{
	pool[x].fa=-1;
	pool[Lc].fa=0; pool[Rc].fa=0;
	merge(Lc,Rc);
	return pool[x].val;
}

void pre()
{
	read(n);
	for(int i=1;i<=n;i++) read(pool[i].val);
}

int main()
{
	freopen("roman.in","r",stdin);
	int _,__;
	pre();
	read(m);
	char cmd[10];
	while(m--)
	{
		scanf("%s",cmd);
		if(cmd[0]=='M')
		{
			read(_);read(__);
			while(pool[_].fa&&~pool[_].fa) _=pool[_].fa;
			while(pool[__].fa&&~pool[__].fa) __=pool[__].fa;
			if(pool[_].fa==-1||pool[__].fa==-1) continue;
			if(_==__) continue;
			merge(_,__);
		}
		if(cmd[0]=='K')
		{
			read(__);
			while(pool[__].fa&&~pool[__].fa)
				__=pool[__].fa;
			if(~pool[__].fa) printf("%d\n",pop(__));
			else puts("0");
		}
	}
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#define p(x) ('0'<=x&&x<='9')

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 1000010

struct node

{

int lc,rc,val;

int fa;

}pool[N];

int n,m;

#define Lc pool[x].lc

#define Rc pool[x].rc

int merge(int x,int y)

{

if(!y) return x; if(!x) return y;

if(pool[y].val<pool[x].val) swap(x,y);

pool[x].rc=merge(y,pool[x].rc);

pool[pool[x].rc].fa=x;

return x;

}

int pop(int x)

{

pool[x].fa=-1;

pool[Lc].fa=0; pool[Rc].fa=0;

merge(Lc,Rc);

return pool[x].val;

}

void pre()

{

read(n);

for(int i=1;i<=n;i++) read(pool[i].val);

}

int main()

{

freopen("roman.in","r",stdin);

int _,__;

pre();

read(m);

char cmd[10];

while(m--)

{

scanf("%s",cmd);

if(cmd[0]=='M')

{

read(_);read(__);

while(pool[_].fa&&~pool[_].fa) _=pool[_].fa;

while(pool[__].fa&&~pool[__].fa) __=pool[__].fa;

if(pool[_].fa==-1||pool[__].fa==-1) continue;

if(_==__) continue;

merge(_,__);

}

if(cmd[0]=='K')

{

read(__);

while(pool[__].fa&&~pool[__].fa)

__=pool[__].fa;

if(~pool[__].fa) printf("%d\n",pop(__));

else puts("0");

}

return 0;

}

BZOJ1455

@OceanEye7年前

04/17

08:26

BZOJ2809可并堆裸题

OceanEye 撰写 BZOJ 可并堆模版题无回复

题面大概是这样子的：

很裸，就学了一下可并堆的姿势然后就写了
1A啊:-D
写的是左偏树，安利百度文库的文章
但是不知道为什么跑了3k+ms
不理了可能是vector的原因吧

#include <cstdio>
#include <algorithm>
#include <vector>
#define p(x) ('0'<=x&&x<='9')
#define ll long long
char cc;
template <class T>
void read( T &x )
{
	x=0; cc=getchar();
	while(!p(cc)) cc=getchar();
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
}
template <class T,class TT>
void read(TT &_,T &__,T &___) { read(_); read(__); read(___); }
template <class T>
void comp( T &x, T y )
{
	x>y?x=x:x=y;
}
using namespace std;
#define N 100010
// zuo pian shu
struct node
{
	int l,r,k,d;
}pool[N];

int combine(int _,int __)
{
	if(!~_) return __; if(!~__) return _;
	if(pool[_].k<pool[__].k) swap(_,__);
	pool[_].r=combine(pool[_].r,__);
	if(~pool[_].r) pool[_].d=pool[pool[_].r].d+1;
	else pool[_].d=0;
	return _;
}
void pop(int &_)
{
	int l=pool[_].l,r=pool[_].r;
	_=combine(l,r);
}
//
vector <int> G[N];
ll C[N],L[N],ANS,SUM[N];
int n,m,SIZ[N],rt[N];
void init()
{
	read(n); read(m);
	for(int i=1,_;i<=n;i++)
	{
		G[i].reserve(10);
		read(_,C[i],L[i]);
		G[_].push_back(i);
	}
}
void dfs(int x)
{
	pool[x].l=pool[x].r=-1;
	SUM[x]=pool[x].k=C[x];
	SIZ[x]=1; rt[x]=x;
	for(int i=0,to;i<G[x].size();i++)
	{
		to=G[x][i];
		dfs(G[x][i]);
		rt[x]=combine(rt[x],rt[to]);
		SUM[x]+=SUM[to];
		SIZ[x]+=SIZ[to];
	}
	for(;SUM[x]>m;) { SUM[x]-=pool[rt[x]].k; pop(rt[x]); SIZ[x]--; }
	comp(ANS,L[x]*SIZ[x]);
}

int main()
{
	init();
	dfs(1);
	printf("%lld",ANS);
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <vector>

#define p(x) ('0'<=x&&x<='9')

#define ll long long

char cc;

template <class T>

void read( T &x )

{

x=0; cc=getchar();

while(!p(cc)) cc=getchar();

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

}

template <class T,class TT>

void read(TT &_,T &__,T &___) { read(_); read(__); read(___); }

template <class T>

void comp( T &x, T y )

{

x>y?x=x:x=y;

}

using namespace std;

#define N 100010

// zuo pian shu

struct node

{

int l,r,k,d;

}pool[N];

int combine(int _,int __)

{

if(!~_) return __; if(!~__) return _;

if(pool[_].k<pool[__].k) swap(_,__);

pool[_].r=combine(pool[_].r,__);

if(~pool[_].r) pool[_].d=pool[pool[_].r].d+1;

else pool[_].d=0;

return _;

}

void pop(int &_)

{

int l=pool[_].l,r=pool[_].r;

_=combine(l,r);

}

vector <int> G[N];

ll C[N],L[N],ANS,SUM[N];

int n,m,SIZ[N],rt[N];

void init()

{

read(n); read(m);

for(int i=1,_;i<=n;i++)

{

G[i].reserve(10);

read(_,C[i],L[i]);

G[_].push_back(i);

}

void dfs(int x)

{

pool[x].l=pool[x].r=-1;

SUM[x]=pool[x].k=C[x];

SIZ[x]=1; rt[x]=x;

for(int i=0,to;i<G[x].size();i++)

{

to=G[x][i];

dfs(G[x][i]);

rt[x]=combine(rt[x],rt[to]);

SUM[x]+=SUM[to];

SIZ[x]+=SIZ[to];

}

for(;SUM[x]>m;) { SUM[x]-=pool[rt[x]].k; pop(rt[x]); SIZ[x]--; }

comp(ANS,L[x]*SIZ[x]);

}

int main()

{

init();

dfs(1);

printf("%lld",ANS);

return 0;

}

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

BZOJ1367 [Baltic2004]sequence

1367: [Baltic2004]sequence

Description

Input

Output

Sample Input

Sample Output

HINT

Source

BZOJ1367 [Baltic2004]sequence

@OceanEye7年前

BZOJ1455

BZOJ1455

@OceanEye7年前

BZOJ2809可并堆裸题

BZOJ2809可并堆裸题

友情链接

近期文章

标签