洛谷 P1505 BZOJ 2157 [国家集训队]旅游

Time limit 10000 ms
Memory limit 265216 kB
OS Linux

吐槽

又浪费一个下午……区间乘-1之后，最大值和最小值更新有坑。新的最大值是原来最小值乘-1，新的最小值是原来最大值乘-1。

没脸见人了

树链剖分，但这题的权值在边上不在点上，那我们只需要在dfs过程中把边权搞到下方的点上，然后两点间各种操作时，不对两点LCA进行操作就好(见代码里一串/)

听说LCT处理这个更擅长，留坑

源代码

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

const int MAXN=2e4+5;

int n,q;

struct Edge{

	int nxt,to,w,id;

}e[MAXN<<1];

int head[MAXN],cnt=1;

inline void add(int u,int v,int w,int id)

{

	e[cnt]={head[u],v,w,id};

	head[u]=cnt++;

	e[cnt]={head[v],u,w,id};

	head[v]=cnt++;

}

int bridge[MAXN];//用桥的id查询点

struct Tree{

	int w;

	int fa,dep,sz,wson;

	int id,top;

}t[MAXN];

void dfs1(int u,int fa,int eid)

{

	t[u].w=e[eid].w;

	bridge[e[eid].id]=u;

	t[u].fa=fa;

	t[u].dep=t[t[u].fa].dep+1;

	t[u].sz=1;

	int mxson=-1;

	for(int i=head[u];i;i=e[i].nxt)

	{

		int v=e[i].to;

		if(fa==v) continue;

		dfs1(v,u,i);

		int temp=t[v].sz;

		if(temp>mxson)

		{

			t[u].wson=v;

			mxson=temp;

		}

		t[u].sz+=temp;

	}

}

int a[MAXN],id=1;

void dfs2(int u,int top)

{

	t[u].top=top;

	t[u].id=id;

	a[id]=t[u].w;

	id++;

	if(t[u].sz==1) return;

	dfs2(t[u].wson,top);

	for(int i=head[u];i;i=e[i].nxt)

	{

		int v=e[i].to;

		if(v==t[u].wson||v==t[u].fa) continue;

		dfs2(v,v);

	}

}

struct Segtree{

	int sum;

	int mx;

	int mn;

	bool lazy;//乘-1的

}s[MAXN<<2];

inline void pushup(int x)

{

	s[x].sum=s[x<<1].sum+s[x<<1|1].sum;

	s[x].mx=std::max(s[x<<1].mx,s[x<<1|1].mx);

	s[x].mn=std::min(s[x<<1].mn,s[x<<1|1].mn);

}

void build(int x,int l,int r)

{

	if(l==r)

	{

		s[x]={a[l],a[l],a[l],0};

		return;

	}

	int mid=l+r>>1;

	build(x<<1,l,mid);

	build(x<<1|1,mid+1,r);

	pushup(x);

}

inline void pushdown(int x)

{

	if(!s[x].lazy) return;

	s[x<<1].lazy=!s[x<<1].lazy;

	int temp=s[x<<1].mx;

	s[x<<1].mx=-s[x<<1].mn;

	s[x<<1].mn=-temp;

	s[x<<1].sum*=-1;

	s[x<<1|1].lazy=!s[x<<1|1].lazy;

	temp=s[x<<1|1].mx;

	s[x<<1|1].mx=-s[x<<1|1].mn;

	s[x<<1|1].mn=-temp;

	s[x<<1|1].sum*=-1;

	s[x].lazy=0;

}

void mul(int x,int l,int r,int ql,int qr)//区间乘-1

{

	if(ql<=l&&r<=qr)

	{

		s[x].lazy=!s[x].lazy;

		int temp=s[x].mx;

		s[x].mx=-s[x].mn;

		s[x].mn=-temp;

		s[x].sum*=-1;

		return;

	}

	pushdown(x);

	int mid=l+r>>1;

	if(ql<=mid) mul(x<<1,l,mid,ql,qr);

	if(qr>mid) mul(x<<1|1,mid+1,r,ql,qr);

	pushup(x);

}

void change(int x,int l,int r,int pos,int k)

{

	if(l==r)

	{

		s[x].mn=k;

		s[x].mx=k;

		s[x].sum=k;

		return;

	}

	pushdown(x);

	int mid=l+r>>1;

	if(pos<=mid) change(x<<1,l,mid,pos,k);

	else change(x<<1|1,mid+1,r,pos,k);

	pushup(x);

}

int quesum(int x,int l,int r,int ql,int qr)

{

	if(ql<=l&&r<=qr) return s[x].sum;

	int mid=l+r>>1;

	int ans=0;

	pushdown(x);

	if(ql<=mid) ans+=quesum(x<<1,l,mid,ql,qr);

	if(qr>mid) ans+=quesum(x<<1|1,mid+1,r,ql,qr);

	return ans;

}

int quemx(int x,int l,int r,int ql,int qr)

{

	if(ql<=l&&r<=qr) return s[x].mx;

	int mid=l+r>>1;

	int ans=-99999999;

	pushdown(x);

	if(ql<=mid) ans=std::max(quemx(x<<1,l,mid,ql,qr),ans);

	if(qr>mid) ans=std::max(quemx(x<<1|1,mid+1,r,ql,qr),ans);

	return ans;

}

int quemn(int x,int l,int r,int ql,int qr)

{

	if(ql<=l&&r<=qr) return s[x].mn;

	int mid=l+r>>1;

	int ans=99999999;

	pushdown(x);

	if(ql<=mid) ans=std::min(quemn(x<<1,l,mid,ql,qr),ans);

	if(qr>mid) ans=std::min(quemn(x<<1|1,mid+1,r,ql,qr),ans);

	return ans;

}

void optn(int x,int y)

{

	while(t[x].top!=t[y].top)

	{

		if(t[t[x].top].dep<t[t[y].top].dep)

			std::swap(x,y);

		mul(1,1,n,t[t[x].top].id,t[x].id);

		x=t[t[x].top].fa;

	}

	if(x==y) return;

	if(t[x].id>t[y].id) std::swap(x,y);

	mul(1,1,n,t[x].id+1,t[y].id);///////////////////////////////////////////////////////////////////

}

int optsum(int x,int y)

{

	int ans=0;

	while(t[x].top!=t[y].top)

	{

		if(t[t[x].top].dep<t[t[y].top].dep) std::swap(x,y);

		ans+=quesum(1,1,n,t[t[x].top].id,t[x].id);

		x=t[t[x].top].fa;

	}

	if(x==y) return ans;

	if(t[x].id>t[y].id) std::swap(x,y);

	ans+=quesum(1,1,n,t[x].id+1,t[y].id);

	return ans;

}

int optmx(int x,int y)

{

	int ans=-99999999;

	while(t[x].top!=t[y].top)

	{

		if(t[t[x].top].dep<t[t[y].top].dep) std::swap(x,y);

		ans=std::max(ans,quemx(1,1,n,t[t[x].top].id,t[x].id));

		x=t[t[x].top].fa;

	}

	if(x==y) return ans;

	if(t[x].id>t[y].id) std::swap(x,y);

	ans=std::max(ans,quemx(1,1,n,t[x].id+1,t[y].id));

	return ans;

}

int optmn(int x,int y)

{

	int ans=99999999;

	while(t[x].top!=t[y].top)

	{

		if(t[t[x].top].dep<t[t[y].top].dep) std::swap(x,y);

		ans=std::min(ans,quemn(1,1,n,t[t[x].top].id,t[x].id));

		x=t[t[x].top].fa;

	}

	if(x==y) return ans;

	if(t[x].id>t[y].id) std::swap(x,y);

	ans=std::min(ans,quemn(1,1,n,t[x].id+1,t[y].id));

	return ans;

}

int main()

{

	//freopen("test.in","r",stdin);

	scanf("%d",&n);

	for(int i=1,u,v,w;i<n;i++)

	{

		scanf("%d%d%d",&u,&v,&w);

		add(u+1,v+1,w,i);

	}

	dfs1(1,0,0);

	dfs2(1,1);

	build(1,1,n);

	scanf("%d",&q);

	//for(int i=1;i<n;i++)

		//printf("%d ",bridge[i]);

	//puts("");

	while(q--)

	{

		char opt[10];

		int u,v;

		scanf("%s%d%d",opt,&u,&v);

		if(opt[0]=='C')

			change(1,1,n,t[bridge[u]].id,v);

		else if(opt[0]=='N') optn(u+1,v+1);

		else if(opt[0]=='S')

			printf("%d\n",optsum(u+1,v+1));

		else if(opt[1]=='A')

			printf("%d\n",optmx(u+1,v+1));

		else printf("%d\n",optmn(u+1,v+1));

	}

	return 0;

}

巴特西

洛谷 P1505 BZOJ 2157 [国家集训队]旅游

吐槽

源代码

最新文章

热门文章