P1505 [国家集训队]旅游

线段树实现区间查询最大值，查询最小值，查询和，区间 $*-1$ ，前面 $3$ 种都没有什么好讲的，最后一种就是把区间和 $*-1$ ，最小值，最大值交换以后 $*-1$
注意：下标从 $0$ 开始。
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <vector>
#define MAXN 30005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch<='9'&&ch>='0'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
struct edge{
	int to,cost;
};
vector<edge>G[MAXN];
inline void add_edge(int u,int v,int w){
	edge temp;
	temp.to=v;
	temp.cost=w;
	G[u].push_back(temp);
}
int value[MAXN],size[MAXN],fa[MAXN],dep[MAXN],top[MAXN],id[MAXN],Bigson[MAXN];
int cnt;
int tofa[MAXN],pre[MAXN];
void dfs(int u,int father){
	size[u]=1;
	dep[u]=dep[father]+1;
	for (register int i=0;i<G[u].size();i++){
		int v=G[u][i].to;
		int w=G[u][i].cost;
		if (v!=father){
			fa[v]=u;
			dfs(v,u);
			tofa[v]=w;
			size[u]+=size[v];
			if (size[v]>size[Bigson[u]]){
				Bigson[u]=v;
			}
		}
	}
}
void dfs2(int u,int Top){
	top[u]=Top;
	pre[id[u]=++cnt]=u;
	if (Bigson[u]){
		dfs2(Bigson[u],Top);
	}
	for (register int i=0;i<G[u].size();i++){
		if (G[u][i].to!=fa[u]&&G[u][i].to!=Bigson[u]){
			dfs2(G[u][i].to,G[u][i].to);
		}
	}
}
#define lc i<<1
#define rc i<<1|1
struct SegmentTree{
	struct node{
		int l,r;
		int sum,revtag;//tag==-1需要变成相反数 
		int maxval,minval;
	}tree[MAXN<<2];
	inline void Swap(int i){
		swap(tree[i].maxval,tree[i].minval);
		tree[i].maxval*=-1,tree[i].minval*=-1;
	}
	inline void pushdown(int i){
		if (tree[i].revtag==-1){
			tree[lc].revtag*=-1;
			tree[rc].revtag*=-1;
			tree[lc].sum=-tree[lc].sum;
			tree[rc].sum=-tree[rc].sum;
			Swap(lc),Swap(rc);
			tree[i].revtag=1;
		}
	}
	inline void pushup(int i){
		tree[i].sum=tree[lc].sum+tree[rc].sum;
		tree[i].maxval=max(tree[lc].maxval,tree[rc].maxval);
		tree[i].minval=min(tree[lc].minval,tree[rc].minval);
	}
	void build(int l,int r,int i){
		tree[i].l=l,tree[i].r=r;
		tree[i].revtag=1;
		if (l==r){
			tree[i].maxval=tree[i].minval=tree[i].sum=tofa[pre[l]];
			return ;
		}
		int mid=(l+r)>>1;
		build(l,mid,lc);
		build(mid+1,r,rc);
		pushup(i);
	}
	void update_pos(int pos,int v,int i){
		int l=tree[i].l,r=tree[i].r;
		if (l==r){
			tree[i].sum=tree[i].maxval=tree[i].minval=v;
			return ;
		}
		pushdown(i);
		int mid=(l+r)>>1;
		if (pos<=mid) update_pos(pos,v,lc);
		else update_pos(pos,v,rc);
		pushup(i);
	}
	void rever(int L,int R,int i){
		int l=tree[i].l,r=tree[i].r;
		if (L<=l&&r<=R){
			tree[i].sum*=-1;
			Swap(i);
			tree[i].revtag*=-1;
			return ;
		}
		pushdown(i);
		int mid=(l+r)>>1;
		if (L<=mid) rever(L,R,lc);
		if (mid<R) rever(L,R,rc);
		pushup(i);
	}
	int query_sum(int L,int R,int i){
		int l=tree[i].l,r=tree[i].r;
		if (L<=l&&r<=R){
			return tree[i].sum;
		}
		int mid=(l+r)>>1;
		int ans=0;
		pushdown(i);
		if (L<=mid) ans+=query_sum(L,R,lc);
		if (mid<R) ans+=query_sum(L,R,rc);
		return ans;
	}
	int query_max(int L,int R,int i){
		int l=tree[i].l,r=tree[i].r;
		if (L<=l&&r<=R){
			return tree[i].maxval;
		}
		pushdown(i);
		int mid=(l+r)>>1;
		int ans=-0x7fffffff;
		if (L<=mid) ans=max(ans,query_max(L,R,lc));
		if (mid<R) ans=max(ans,query_max(L,R,rc));
		return ans;
	}
	int query_min(int L,int R,int i){
		int l=tree[i].l,r=tree[i].r;
		if (L<=l&&r<=R){
			return tree[i].minval;
		}
		pushdown(i);
		int mid=(l+r)>>1;
		int ans=0x7fffffff;
		if (L<=mid) ans=min(ans,query_min(L,R,lc));
		if (mid<R) ans=min(ans,query_min(L,R,rc));
		return ans;
	}
	#undef lc
	#undef rc
}Seg;
inline int query_ans(int u,int v){
	int sum=0;
	while (top[u]!=top[v]){
		if (dep[top[u]]<dep[top[v]]) swap(u,v);
		sum+=Seg.query_sum(id[top[u]],id[u],1);
		u=fa[top[u]];
	}
	if (u==v) return sum;
	if (id[u]>id[v]) swap(u,v);
	sum+=Seg.query_sum(id[u]+1,id[v],1);
	return sum;
}
inline int query_maxval(int u,int v){
	int maxn=-0x7fffffff;
	while (top[u]!=top[v]){
		if (dep[top[u]]<dep[top[v]]) swap(u,v);
		maxn=max(maxn,Seg.query_max(id[top[u]],id[u],1));
		u=fa[top[u]];
	}
	if (u==v) return maxn;
	if (id[u]>id[v]) swap(u,v);
	maxn=max(maxn,Seg.query_max(id[u]+1,id[v],1));
	return maxn;
}
inline int query_minval(int u,int v){
	int mino=0x7fffffff;
	while (top[u]!=top[v]){
		if (dep[top[u]]<dep[top[v]]) swap(u,v);
		mino=min(mino,Seg.query_min(id[top[u]],id[u],1));
		u=fa[top[u]];
	}
	if (u==v) return mino;
	if (id[u]>id[v]) swap(u,v);
	mino=min(mino,Seg.query_min(id[u]+1,id[v],1));
	return mino;
}
inline void update_tree(int u,int v){
	while (top[u]!=top[v]){
		if (dep[top[u]]<dep[top[v]]) swap(u,v);
		Seg.rever(id[top[u]],id[u],1);
		u=fa[top[u]];
	}
	if (u==v) return ;
	if (id[u]>id[v]) swap(u,v);
	Seg.rever(id[u]+1,id[v],1);
}
char str[10];
int main(){
	int n=read();
	for (register int i=1;i<n;i++){
		int u=read()+1,v=read()+1,w=read();
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	dfs(1,1);
	dfs2(1,1);
	Seg.build(1,n,1);
	int q=read();
	while (q--){
		scanf("%s",str);
		if (str[0]=='C'){
			int v=read()+1,w=read();
			Seg.update_pos(id[v],w,1);
			continue;
		}
		int u=read()+1,v=read()+1;
		if (str[0]=='N'){
			update_tree(u,v);
		}
		else if (str[0]=='S'){
			printf("%d\n",query_ans(u,v));
		}
		else if (str[1]=='A'){
			printf("%d\n",query_maxval(u,v));
		}
		else if (str[1]=='I'){
			printf("%d\n",query_minval(u,v));
		}
	}
}
Steven_Meng's Blog

下一篇：CF735D Taxes
