「BZOJ3600」没有人的算术

2015年7月11日8,0653

http://pan.baidu.com/s/1B0JNo

vfk大大的题

好厉害QAQ

WJMZBMR在论文中也有提到平衡树的这种用法

《重量平衡树和后缀平衡树在信息学奥赛中的应用》

大概就是用平衡树维护这些数，给每个数一个实数值表示其大小

生成一个数(a,b)的时候，由于a,b都是之前出现过的数，所以我们可以直接在平衡树上插入，返回代表它的实数值

用线段树求区间最大值

#include<map>
#include<set>
#include<cmath>
#include<deque>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,rt,R,top;
double a[500005];
int mx[500005],pos[100005],id[500005];
char ch[5];
struct data{
	int l,r;
	friend bool operator>(data x,data y){
		if(a[x.l]>a[y.l])return 1;
		if(a[x.l]==a[y.l]&&a[x.r]>a[y.r])return 1;
		return 0;
	}
	friend bool operator==(data x,data y){
		if(x.l!=y.l||x.r!=y.r)return 0;
		return 1;
	}
};
struct sctree{
	int cnt;
	data v[500005];
	int size[500005],ls[500005],rs[500005];
	void dfs(int k){
		if(!k)return;
		dfs(ls[k]);
		id[++top]=k;
		dfs(rs[k]);
	}
	void build(int &k,int l,int r,double lv,double rv){
		if(l>r){k=0;return;}
		double mv=(lv+rv)/2.0;
		int mid=(l+r)/2;
		k=id[mid];a[k]=mv;
		build(ls[k],l,mid-1,lv,mv);
		build(rs[k],mid+1,r,mv,rv);
		size[k]=size[ls[k]]+size[rs[k]]+1;
	}
	void rebuild(int &k,double lv,double rv){
	    top=0;
		dfs(k);
		build(k,1,top,lv,rv);
	}
	int insert(int &k,double lv,double rv,data val){
		double mv=(lv+rv)/2.0;
		if(!k)
		{
			k=++cnt;a[k]=mv;v[k]=val;size[k]=1;
			return k;
		}
		int p;
		if(val==v[k])return k;
		else 
		{
			size[k]++;	
			if(val>v[k])p=insert(rs[k],mv,rv,val);
			else p=insert(ls[k],lv,mv,val);
		}
		if(size[k]*0.75>max(size[ls[k]],size[rs[k]]))
		{
			if(R)
			{
				if(ls[k]==R)rebuild(ls[k],lv,mv);
				else rebuild(rs[k],mv,rv);
				R=0;
			}
		}
		else R=k;
		return p;
	}
}sc;
void modify(int k,int l,int r,int v)
{
	int mid=(l+r)>>1;
	if(l==r){mx[k]=l;return;}
	if(v<=mid)modify(k<<1,l,mid,v);
	else modify(k<<1|1,mid+1,r,v);
	int x=mx[k<<1],y=mx[k<<1|1];
	if(a[pos[x]]>=a[pos[y]])mx[k]=x;
	else mx[k]=y;
}
int query(int k,int l,int r,int x,int y)
{
	int mid=(l+r)>>1;
	if(l==x&&y==r)return mx[k];
	int t=0,p=0;
	if(x<=mid)
	{
		p=query(k<<1,l,mid,x,min(mid,y));
		if(a[pos[p]]>a[pos[t]])t=p;
	}
	if(y>mid)
	{
		p=query(k<<1|1,mid+1,r,max(x,mid+1),y);
		if(a[pos[p]]>a[pos[t]])t=p;
	}
	return t;
}
int main()
{
	n=read();m=read();
	a[0]=-1;
    sc.insert(rt,0,1,(data){0,0});
	for(int i=1;i<=n;i++)pos[i]=1;
	for(int i=1;i<=n;i++)modify(1,1,n,i);
	int l,r,K;
	for(int i=1;i<=m;i++)
	{
		scanf("%s",ch+1);l=read();r=read();
		if(ch[1]=='C')
		{
			K=read();
			pos[K]=sc.insert(rt,0,1,(data){pos[l],pos[r]});
			if(R)sc.rebuild(rt,0,1);R=0;
			modify(1,1,n,K);
		}
		else printf("%d\n",query(1,1,n,l,r));
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

#include<map>

#include<set>

#include<cmath>

#include<deque>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,rt,R,top;

double a[500005];

int mx[500005],pos[100005],id[500005];

char ch[5];

struct data{

int l,r;

friend bool operator>(data x,data y){

if(a[x.l]>a[y.l])return 1;

if(a[x.l]==a[y.l]&&a[x.r]>a[y.r])return 1;

return 0;

}

friend bool operator==(data x,data y){

if(x.l!=y.l||x.r!=y.r)return 0;

return 1;

}

};

struct sctree{

int cnt;

data v[500005];

int size[500005],ls[500005],rs[500005];

void dfs(int k){

if(!k)return;

dfs(ls[k]);

id[++top]=k;

dfs(rs[k]);

}

void build(int &k,int l,int r,double lv,double rv){

if(l>r){k=0;return;}

double mv=(lv+rv)/2.0;

int mid=(l+r)/2;

k=id[mid];a[k]=mv;

build(ls[k],l,mid-1,lv,mv);

build(rs[k],mid+1,r,mv,rv);

size[k]=size[ls[k]]+size[rs[k]]+1;

}

void rebuild(int &k,double lv,double rv){

top=0;

dfs(k);

build(k,1,top,lv,rv);

}

int insert(int &k,double lv,double rv,data val){

double mv=(lv+rv)/2.0;

if(!k)

{

k=++cnt;a[k]=mv;v[k]=val;size[k]=1;

return k;

}

int p;

if(val==v[k])return k;

else

{

size[k]++;

if(val>v[k])p=insert(rs[k],mv,rv,val);

else p=insert(ls[k],lv,mv,val);

}

if(size[k]*0.75>max(size[ls[k]],size[rs[k]]))

{

if(R)

{

if(ls[k]==R)rebuild(ls[k],lv,mv);

else rebuild(rs[k],mv,rv);

R=0;

}

else R=k;

return p;

}

}sc;

void modify(int k,int l,int r,int v)

{

int mid=(l+r)>>1;

if(l==r){mx[k]=l;return;}

if(v<=mid)modify(k<<1,l,mid,v);

else modify(k<<1|1,mid+1,r,v);

int x=mx[k<<1],y=mx[k<<1|1];

if(a[pos[x]]>=a[pos[y]])mx[k]=x;

else mx[k]=y;

}

int query(int k,int l,int r,int x,int y)

{

int mid=(l+r)>>1;

if(l==x&&y==r)return mx[k];

int t=0,p=0;

if(x<=mid)

{

p=query(k<<1,l,mid,x,min(mid,y));

if(a[pos[p]]>a[pos[t]])t=p;

}

if(y>mid)

{

p=query(k<<1|1,mid+1,r,max(x,mid+1),y);

if(a[pos[p]]>a[pos[t]])t=p;

}

return t;

}

int main()

{

n=read();m=read();

a[0]=-1;

sc.insert(rt,0,1,(data){0,0});

for(int i=1;i<=n;i++)pos[i]=1;

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

int l,r,K;

for(int i=1;i<=m;i++)

{

scanf("%s",ch+1);l=read();r=read();

if(ch[1]=='C')

{

K=read();

pos[K]=sc.insert(rt,0,1,(data){pos[l],pos[r]});

if(R)sc.rebuild(rt,0,1);R=0;

modify(1,1,n,K);

}

else printf("%d\n",query(1,1,n,l,r));

}

return 0;

}

« 「CF339X」Codeforces Round #197 (Div. 2) 「省选模拟赛」小奇的花园 »

Marser

黄学长，替罪羊树判断重构的那一段应该是size[k]*0.75<max(size[ls[k]],size[rs[k]])吧。

Marser

emm我假了，如果给您带来了困扰，实在不好意思。

n+e

链接贴错了应该是这个http://pan.baidu.com/s/1B0JNo

hzwer.com _ Home | http://hzwer.com

「BZOJ3600」没有人的算术

分类目录

热门文章

Myfriends

近期评论