BZOJ 1367([Baltic2004]sequence-左偏树+中位数贪心)

1367: [Baltic2004]sequence
Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 521 Solved: 159
[Submit][Status]
Description

Input

Output
一个整数R
Sample Input
7
9
4
8
20
14
15
18
Sample Output
13
HINT
所求的Z序列为6,7,8,13,14,15,18.
R=13

左偏树+1

这题裸裸的左偏树，我却各种WA。。。。

结果发现 左偏树合并 a*b==0 会乘爆掉。。。掉节操。。。。。

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (1300000+10)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
int father[MAXN];
int getfather(int x)
{
	if (father[x]==x) return x;
	father[x]=getfather(father[x]);
	return father[x];
}
struct node
{
	ll v;
	int dis,ch[2];
	node():v(0),dis(0){ch[0]=ch[1]=0;}
	node(ll _v):v(_v),dis(0){ch[0]=ch[1]=0;}
}q[MAXN];
int merge(int a,int b)
{
	if (a==0||b==0) return a+b;
	if (q[a].v0 a-b:b-a;}
int main()
{
//	freopen("bzoj1367.in","r",stdin);
	scanf("%d",&n);
	For(i,n) scanf("%lld",&a[i]),a[i]-=(long long)i,father[i]=i,q[i].v=a[i];
	For(i,n)
	{
		siz[++tot]=1;root[tot]=i;l[tot]=r[tot]=i;
		while (tot>1&&q[root[tot]].v<=q[root[tot-1]].v)
		{
			int ru=root[tot-1],rv=root[tot];
			Fork(j,l[tot],r[tot])
			{
				q[j]=node(a[j]);
				ru=merge(ru,j);
			}
			siz[tot-1]+=r[tot]-l[tot]+1;r[tot-1]=r[tot];tot--;
			while (siz[tot]>(r[tot]-l[tot]+2)/2) ru=pop(ru),siz[tot]--;
			root[tot]=ru;			
		}
//		For(i,tot) cout< 
 

 第二Sol-贪心：





 
 
假想有2数列A,B
 
 
A的中位数 
 
A的中位数>(B+C)的中位数
 
 
则(A+B+C)的中位数≤A的中位数 
 
所以A中位数，B中位数往上的部分去掉，不影响结果
 
 
 
 
 
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define MAXN (1000000+10)
typedef long long ll;
struct node
{
	int v,dis,ch[2];
	node():v(0),dis(0){ch[0]=ch[1]=0;}
	node(int _v):v(_v),dis(0){ch[0]=ch[1]=0;}
}q[MAXN];
int merge(int a,int b)
{
	if (a==0||b==0) return a+b;
	if (q[a].v0 a-b:b-a;}
int main()
{
	freopen("bzoj1367.in","r",stdin);
	scanf("%d",&n);
	For(i,n)
	{
		scanf("%d",&a[i]),a[i]-=i;q[i].v=a[i];
	}
	For(i,n)
	{
		siz[++tot]=1;root[tot]=i;l[tot]=r[tot]=i;
		while (tot>1&&q[root[tot-1]].v>q[root[tot]].v)
		{
			int ru=root[tot-1],rv=root[tot];
			/*
			Fork(j,l[tot],r[tot])
			{
				q[j]=node(a[j]);
				ru=merge(ru,j);
			}*/
			ru=merge(ru,rv);int b=((r[tot-1]-l[tot-1]+1)%2)+((r[tot]-l[tot]+1)%2);
			siz[tot-1]+=siz[tot];r[tot-1]=r[tot];tot--;
			if (b==2) ru=pop(ru),siz[tot]--;
			root[tot]=ru;			
//		For(i,tot) cout<