「BZOJ1180」[CROATIAN2009] OTOCI

2015年7月1日6,0756

Description

给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作： 1、bridge A B：询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。 2、penguins A X：将结点A对应的权值wA修改为X。 3、excursion A B：如果结点A和结点B不连通，则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。给出q个操作，要求在线处理所有操作。数据范围：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。

Input

第一行包含一个整数n(1<=n<=30000)，表示节点的数目。第二行包含n个整数，第i个整数表示第i个节点初始时对应的权值。第三行包含一个整数q(1<=n<=300000)，表示操作的数目。以下q行，每行包含一个操作，操作的类别见题目描述。任意时刻每个节点对应的权值都是1到1000的整数。

Output

输出所有bridge操作和excursion操作对应的输出，每个一行。

Sample Input

5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5

Sample Output

4
impossible
yes
6
yes
yes
15
yes
15
16

题解

模板题QAQ

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define mod 1000000007
#define ll long long
#define eps 1e-12
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,q,top;
int c[30005][2],fa[30005],sum[30005],v[30005],st[30005];
bool rev[30005];
char ch[15];
void update(int x)
{
	int l=c[x][0],r=c[x][1];
	sum[x]=sum[l]+sum[r]+v[x];
}
void pushdown(int x)
{
	int l=c[x][0],r=c[x][1];
	if(rev[x])
	{
		rev[x]^=1,rev[l]^=1,rev[r]^=1;
		swap(c[x][0],c[x][1]);
	}
}
bool isroot(int x)
{
	return !(c[fa[x]][0]==x||c[fa[x]][1]==x);
}
void rotate(int &x)
{
	int y=fa[x],z=fa[y],l,r;
	l=(c[y][1]==x);r=l^1;
	if(!isroot(y))c[z][c[z][1]==y]=x;
	fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
	c[y][l]=c[x][r];c[x][r]=y;
	update(y);update(x);
}
void splay(int x)
{
	top=0;st[++top]=x;
	for(int i=x;!isroot(i);i=fa[i])st[++top]=fa[i];
	while(top)pushdown(st[top--]);
	while(!isroot(x))
	{
		int y=fa[x],z=fa[y];
		if(!isroot(y))
		{
			if(c[y][0]==x^c[z][0]==y)rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
void access(int x)
{
	for(int t=0;x;t=x,x=fa[x])
		splay(x),c[x][1]=t,update(x);
}
void makeroot(int x)
{
	access(x);splay(x);rev[x]^=1;
}
void link(int x,int y)
{
    makeroot(x);fa[x]=y;
}
int getrt(int x)
{
	access(x);splay(x);
	while(c[x][0])x=c[x][0];
	return x;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)sum[i]=v[i]=read();
	q=read();
	while(q--)
	{
		scanf("%s",ch+1);int x=read(),y=read();
		if(ch[1]=='b')
		{
			if(getrt(x)==getrt(y))puts("no");
			else puts("yes"),link(x,y);
		}
		if(ch[1]=='p')
		{
			makeroot(x);v[x]=y;update(x);
		}
		if(ch[1]=='e')
		{
			if(getrt(x)!=getrt(y))puts("impossible");
			else 
			{
				makeroot(x),access(y),splay(y);
				printf("%d\n",sum[y]);
			}
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define mod 1000000007

#define ll long long

#define eps 1e-12

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,q,top;

int c[30005][2],fa[30005],sum[30005],v[30005],st[30005];

bool rev[30005];

char ch[15];

void update(int x)

{

int l=c[x][0],r=c[x][1];

sum[x]=sum[l]+sum[r]+v[x];

}

void pushdown(int x)

{

int l=c[x][0],r=c[x][1];

if(rev[x])

{

rev[x]^=1,rev[l]^=1,rev[r]^=1;

swap(c[x][0],c[x][1]);

}

bool isroot(int x)

{

return !(c[fa[x]][0]==x||c[fa[x]][1]==x);

}

void rotate(int &x)

{

int y=fa[x],z=fa[y],l,r;

l=(c[y][1]==x);r=l^1;

if(!isroot(y))c[z][c[z][1]==y]=x;

fa[x]=z;fa[y]=x;fa[c[x][r]]=y;

c[y][l]=c[x][r];c[x][r]=y;

update(y);update(x);

}

void splay(int x)

{

top=0;st[++top]=x;

for(int i=x;!isroot(i);i=fa[i])st[++top]=fa[i];

while(top)pushdown(st[top--]);

while(!isroot(x))

{

int y=fa[x],z=fa[y];

if(!isroot(y))

{

if(c[y][0]==x^c[z][0]==y)rotate(x);

else rotate(y);

}

rotate(x);

}

void access(int x)

{

for(int t=0;x;t=x,x=fa[x])

splay(x),c[x][1]=t,update(x);

}

void makeroot(int x)

{

access(x);splay(x);rev[x]^=1;

}

void link(int x,int y)

{

makeroot(x);fa[x]=y;

}

int getrt(int x)

{

access(x);splay(x);

while(c[x][0])x=c[x][0];

return x;

}

int main()

{

n=read();

for(int i=1;i<=n;i++)sum[i]=v[i]=read();

q=read();

while(q--)

{

scanf("%s",ch+1);int x=read(),y=read();

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

{

if(getrt(x)==getrt(y))puts("no");

else puts("yes"),link(x,y);

}

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

{

makeroot(x);v[x]=y;update(x);

}

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

{

if(getrt(x)!=getrt(y))puts("impossible");

else

{

makeroot(x),access(y),splay(y);

printf("%d\n",sum[y]);

}

return 0;

}

« 「BZOJ2157」旅游

同问为什么修改要用makeroot…，测的感觉跑起来差不多呀QAQ

老蒋

为什么修改的时候要makeroot啊……splay一下不可以吗？是不是要保证均摊复杂度？

Yzx835

黄学长，那个加rev标记有啥用呀０．０

噫

区间翻转

Yzx835

但是为啥要翻转左右子树

黄励新

因为要换根

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

「BZOJ1180」[CROATIAN2009] OTOCI

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论