首页 > 代码库 > 【BZOJ4811】[Ynoi2017]由乃的OJ 树链剖分+线段树

【BZOJ4811】[Ynoi2017]由乃的OJ 树链剖分+线段树

2024-11-25 16:45:02   204人阅读

【BZOJ4811】[Ynoi2017]由乃的OJ

Description

由乃正在做她的OJ。现在她在处理OJ上的用户排名问题。OJ上注册了n个用户，编号为1～"，一开始他们按照编号排名。由乃会按照心情对这些用户做以下四种操作，修改用户的排名和编号：然而由乃心情非常不好，因为Deus天天问她题。。。因为Deus天天问由乃OI题，所以由乃去学习了一下OI，由于由乃智商挺高，所以OI学的特别熟练她在RBOI2016中以第一名的成绩进入省队，参加了NOI2016获得了金牌保送
Deus：这个题怎么做呀？
yuno：这个不是NOI2014的水题吗。。。
Deus：那如果出到树上，多组链询问，带修改呢？
yuno：诶。。。？？？
Deus：这题叫做睡觉困难综合征哟~
虽然由乃OI很好，但是她基本上不会DS，线段树都只会口胡，比如她NOI2016的分数就是100+100+100+0+100+100。
。。NOIP2017的分数是100+0+100+100+0+100所以她还是只能找你帮她做了。。。
给你一个有n个点的树，每个点的包括一个位运算opt和一个权值x，位运算有&,l,^三种，分别用1,2,3表示。
每次询问包含三个数x,y,z,初始选定一个数v。然后v依次经过从x到y的所有节点，每经过一个点i，v就变成v opti xi，所以他想问你，最后到y时，希望得到的值尽可能大，求最大值？给定的初始值v必须是在[0,z]之间。每次修改包含三个数x,y,z，意思是把x点的操作修改为y，数值改为z

Input

第一行三个数n，m，k。k的意义是每个点上的数，以及询问中的数值z都 <2^k。之后n行
每行两个数x,y表示该点的位运算编号以及数值
之后n - 1行，每行两个数x,y表示x和y之间有边相连
之后m行，每行四个数，Q,x,y,z表示这次操作为Q(1位询问，2为修改)，x，y，z意义如题所述
0 <= n , m <= 100000 , k <= 64

Output

对于每个操作1，输出到最后可以造成的最大刺激度v

Sample Input

5 5 3
1 7
2 6
3 7
3 6
3 1
1 2
2 3
3 4
1 5
1 1 4 7
1 1 3 5
2 1 1 3
2 3 3 3
1 1 3 2

Sample Output

7
1
5

题解：思路同BZOJ2908又是nand，不过本题nlog3n显然过不去，所以我们考虑优化我们的算法。

考虑能否不拆位，将所有位压成一个unsigned long long一起尽行计算。设l0表示一个所有位都是0的数从左往右经过这段区间会变成什么，l1表示一个所有位都是1的数从左往右经过这个点会变成什么，那么显然有：

l0[x]=(l0[lson]&l1[rson])|((~l0[lson])&l0[rson])
l1[x]=(l1[lson]&l1[rson])|((~l1[lson])&l0[rson])

r0,r1同理，然后就是nlog2n的了。

#include <cstdio>#include <cstring>#include <iostream>#define lson x<<1#define rson x<<1|1using namespace std;typedef unsigned long long ll;const int maxn=100010;int n,m,k,cnt;ll msk;ll l0[maxn<<2],l1[maxn<<2],r0[maxn<<2],r1[maxn<<2],v[maxn];int to[maxn<<1],next[maxn<<1],head[maxn],dep[maxn],fa[maxn],top[maxn],son[maxn],siz[maxn],p[maxn],op[maxn],q[maxn];int st[maxn];void pushup(int x){	l0[x]=(l0[lson]&l1[rson])|((~l0[lson])&l0[rson]);	l1[x]=(l1[lson]&l1[rson])|((~l1[lson])&l0[rson]);	r0[x]=(r0[rson]&r1[lson])|((~r0[rson])&r0[lson]);	r1[x]=(r1[rson]&r1[lson])|((~r1[rson])&r0[lson]);}void build(int l,int r,int x){	if(l==r)	{		if(op[q[l]]==1)	l1[x]=r1[x]=v[q[l]],l0[x]=r0[x]=0;		if(op[q[l]]==2)	l1[x]=r1[x]=msk,l0[x]=r0[x]=v[q[l]];		if(op[q[l]]==3)	l1[x]=r1[x]=v[q[l]]^msk,l0[x]=r0[x]=v[q[l]];		return ;	}	int mid=l+r>>1;	build(l,mid,lson),build(mid+1,r,rson);	pushup(x);}void updata(int l,int r,int x,int a,int op,ll val){	if(l==r)	{		if(op==1)	l1[x]=r1[x]=val,l0[x]=r0[x]=0;		if(op==2)	l1[x]=r1[x]=msk,l0[x]=r0[x]=val;		if(op==3)	l1[x]=r1[x]=val^msk,l0[x]=r0[x]=val;		return ;	}	int mid=l+r>>1;	if(a<=mid)	updata(l,mid,lson,a,op,val);	else	updata(mid+1,r,rson,a,op,val);	pushup(x);}ll ql(int l,int r,int x,int a,int b,ll val){	if(a<=l&&r<=b)	return (val&l1[x])|((~val)&l0[x]);	int mid=l+r>>1;	if(b<=mid)	return ql(l,mid,lson,a,b,val);	if(a>mid)	return ql(mid+1,r,rson,a,b,val);	return ql(mid+1,r,rson,a,b,ql(l,mid,lson,a,b,val));}ll qr(int l,int r,int x,int a,int b,ll val){	if(a<=l&&r<=b)	return (val&r1[x])|((~val)&r0[x]);	int mid=l+r>>1;	if(b<=mid)	return qr(l,mid,lson,a,b,val);	if(a>mid)	return qr(mid+1,r,rson,a,b,val);	return qr(l,mid,lson,a,b,qr(mid+1,r,rson,a,b,val));}void dfs1(int x){	siz[x]=1;	for(int i=head[x];i!=-1;i=next[i])	{		if(to[i]!=fa[x])		{			fa[to[i]]=x,dep[to[i]]=dep[x]+1,dfs1(to[i]),siz[x]+=siz[to[i]];			if(siz[to[i]]>siz[son[x]])	son[x]=to[i];		}	}}void dfs2(int x,int tp){	top[x]=tp,p[x]=++p[0],q[p[0]]=x;	if(son[x])	dfs2(son[x],tp);	for(int i=head[x];i!=-1;i=next[i])	if(to[i]!=fa[x]&&to[i]!=son[x])	dfs2(to[i],to[i]);}void ask(int x,int y,ll mx){	ll ret=0,r0=0,r1=msk;	st[0]=0;	while(top[x]!=top[y])	{		if(dep[top[x]]>dep[top[y]])	r0=qr(1,n,1,p[top[x]],p[x],r0),r1=qr(1,n,1,p[top[x]],p[x],r1),x=fa[top[x]];		else	st[++st[0]]=y,y=fa[top[y]];	}	if(dep[x]>dep[y])	r0=qr(1,n,1,p[y],p[x],r0),r1=qr(1,n,1,p[y],p[x],r1);	else	r0=ql(1,n,1,p[x],p[y],r0),r1=ql(1,n,1,p[x],p[y],r1);	for(int i=st[0];i;i--)	y=st[i],r0=ql(1,n,1,p[top[y]],p[y],r0),r1=ql(1,n,1,p[top[y]],p[y],r1);	for(int i=k-1;~i;i--)	{		if(mx<(1ULL<<i)||(r0&(1ULL<<i))>=(r1&(1ULL<<i)))	ret|=(r0&(1ULL<<i));		else	ret|=(r1&(1ULL<<i)),mx-=(1ULL<<i);	}	printf("%llu\n",ret);}void add(int a,int b){	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;}inline ll rd(){	ll ret=0;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	gc=getchar();	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+(gc-‘0‘),gc=getchar();	return ret;}int main(){	n=rd(),m=rd(),k=rd();	int i,a,b,d;	ll c;	for(i=0;i<k;i++)	msk|=(1ULL<<i);	for(i=1;i<=n;i++)	op[i]=rd(),v[i]=rd();	memset(head,-1,sizeof(head));	for(i=1;i<n;i++)	a=rd(),b=rd(),add(a,b),add(b,a);	dep[1]=1,dfs1(1),dfs2(1,1);	build(1,n,1);	for(i=1;i<=m;i++)	{		d=rd(),a=rd(),b=rd(),c=rd();		if(d==1)	ask(a,b,c);		else	updata(1,n,1,p[a],b,c);	}	return 0;}//5 5 3 1 7 2 6 3 7 3 6 3 1 1 2 2 3 3 4 1 5 1 1 4 7 1 1 3 5 2 1 1 3 2 3 3 3 1 1 3 2

【BZOJ4811】[Ynoi2017]由乃的OJ 树链剖分+线段树


联系
我们