[国家集训队2011]旅游 - rvalue - 402533

记录编号	402533	评测结果	AAAAAAAAAA
题目名称	[国家集训队2011]旅游	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.333 s
提交时间	2017-05-06 17:53:25	内存使用	93.75 MiB
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int INF=0x7FFFFFFE;
const int MAXN=500010;
const int BUF_SIZE=100;

struct Edge{
	int from;
	int to;
	int value;
	Edge* next;
};

struct Node{
	int l;
	int r;
	int max;
	int min;
	int sum;
	bool neg;
	Node* lch;
	Node* rch;
	inline void Flip(){
		this->neg=!this->neg;
		this->max=-this->max;
		this->min=-this->min;
		this->sum=-this->sum;
		swap(this->max,this->min);
	}
	inline void PushDown(){
		if(this->neg){
			this->lch->Flip();
			this->rch->Flip();
			this->neg=false;
		}
	}
	inline void Maintain(){
		this->max=std::max(this->lch->max,this->rch->max);
		this->min=std::min(this->lch->min,this->rch->min);
		this->sum=this->lch->sum+this->rch->sum;
	}
};

Edge E[MAXN*2];
Edge* head[MAXN];
Edge* tope=E;

Node N[MAXN*4];
Node* topv=N;

int v;
int clk;
int id[MAXN];
int top[MAXN];
int pos[MAXN];
int prt[MAXN];
int son[MAXN];
int deep[MAXN];
int size[MAXN];
int value[MAXN];

char buf[BUF_SIZE];

void Initialize();
void Insert(int,int,int);
void Change(Node*,const int&,const int&);
void Negate(int,int);
void Negate(Node*,const int&,const int&);
void Build(Node*,int,int);
void DFS(int,int,int);
void DFS(int,int);
int QueryMin(Node*,const int&,const int&);
int QueryMin(int,int);
int QueryMax(Node*,const int&,const int&);
int QueryMax(int,int);
int QuerySum(Node*,const int&,const int&);
int QuerySum(int,int);

int main(){
	int __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	int t;
	int a,b;
	Initialize();
	scanf("%d",&t);
	for(int i=0;i<t;i++){
		scanf("%s%d%d",buf,&a,&b);
		if(buf[0]=='M'){
			if(buf[1]=='I'){
				printf("%d\n",QueryMin(a,b));
			}
			else{
				printf("%d\n",QueryMax(a,b));
			}
		}
		else if(buf[0]=='S'){
			printf("%d\n",QuerySum(a,b));
		}
		else if(buf[0]=='N'){
			Negate(a,b);
		}
		else if(buf[0]=='C'){
			int from=E[a*2-1].from;
			int to=E[a*2-1].to;
			if(prt[from]==to){
				Change(N,id[from],b);
			}
			else{
				Change(N,id[to],b);
			}
		}
	}
	return 0;
}

void Initialize(){
#ifndef ASC_LOCAL
	freopen("nt2011_travel.in","r",stdin);
	freopen("nt2011_travel.out","w",stdout);
#endif
	int from;
	int to;
	int value;
	scanf("%d",&v);
	for(int i=1;i<v;i++){
		scanf("%d%d%d",&from,&to,&value);
		Insert(from,to,value);
		Insert(to,from,value);
	}
	memset(son,0xFF,sizeof(son));
	DFS(1,1,0);
	// puts("DFS");
	DFS(1,1);
	Build(topv++,1,clk);
}

void DFS(int root,int prt,int deep){
	int maxSize=0;
	::prt[root]=prt;
	::deep[root]=deep;
	::size[root]=1;

	for(Edge* i=head[root];i!=NULL;i=i->next){
		if(::prt[root]!=i->to){
			value[i->to]=i->value;
			DFS(i->to,root,deep+1);
			size[root]+=size[i->to];
			if(size[i->to]>maxSize){
				son[root]=i->to;
				maxSize=size[i->to];
			}
		}
	}
}

void DFS(int root,int top){
	// printf("root=%d\n",root);
	clk++;
	::top[root]=top;
	::id[root]=clk;
	::pos[clk]=root;

	if(son[root]!=-1){
		DFS(son[root],top);
	}
	for(Edge* i=head[root];i!=NULL;i=i->next){
		if(i->to!=son[root]&&i->to!=prt[root]){
			DFS(i->to,i->to);
		}
	}
}
//=====================================Segment Tree======================================
void Build(Node* root,int l,int r){
	root->l=l;
	root->r=r;
	if(l==r){
		root->min=root->max=root->sum=value[pos[l]];
		root->neg=false;
	}
	else{
		int mid=(l+r)>>1;
		Build(root->lch=topv++,l,mid);
		Build(root->rch=topv++,mid+1,r);
		root->Maintain();
	}
}

void Change(Node* root,const int& x,const int& d){
	if(root->l==root->r){
		root->min=root->max=root->sum=d;
		root->neg=false;
	}
	else{
		root->PushDown();
		if(x<=root->lch->r)
			Change(root->lch,x,d);
		else
			Change(root->rch,x,d);
		root->Maintain();
	}
}

void Negate(Node* root,const int& l,const int& r){
	if(l<=root->l&&root->r<=r){
		root->Flip();
	}
	else{
		root->PushDown();
		if(l<=root->lch->r)
			Negate(root->lch,l,r);
		if(root->rch->l<=r)
			Negate(root->rch,l,r);
		root->Maintain();
	}
}

int QueryMax(Node* root,const int& l,const int& r){
	if(l<=root->l&&root->r<=r){
		return root->max;
	}
	else{
		int ans=-INF;
		root->PushDown();
		if(l<=root->lch->r)
			ans=max(ans,QueryMax(root->lch,l,r));
		if(root->rch->l<=r)
			ans=max(ans,QueryMax(root->rch,l,r));
		return ans;
	}
}

int QueryMin(Node* root,const int& l,const int& r){
	if(l<=root->l&&root->r<=r){
		return root->min;
	}
	else{
		int ans=INF;
		root->PushDown();
		if(l<=root->lch->r)
			ans=min(ans,QueryMin(root->lch,l,r));
		if(root->rch->l<=r)
			ans=min(ans,QueryMin(root->rch,l,r));
		return ans;
	}
}

int QuerySum(Node* root,const int& l,const int& r){
	// printf("l=%d r=%d L=%d R=%d\n",root->l,root->r,l,r);
	if(l<=root->l&&root->r<=r){
		return root->sum;
	}
	else{
		int ans=0;
		root->PushDown();
		if(l<=root->lch->r)
			ans+=QuerySum(root->lch,l,r);
		if(root->rch->l<=r)
			ans+=QuerySum(root->rch,l,r);
		return ans;
	}
}

/*inline void Maintain(Node* root){
	root->min=min(root->lch->min,root->rch->min);
	root->max=max(root->lch->max,root->rch->max);
	root->sum=root->lch->sum+root->rch->sum;
}

inline void PushDown(Node* root){
	root->lch->neg=!root->lch->neg;
	root->lch->max=-root->lch->max;
	root->lch->min=-root->lch->min;
	swap(root->lch->max,root->lch->min);
	root->lch->sum=-root->lch->sum;

	root->rch->neg=!root->rch->neg;
	root->rch->max=-root->rch->max;
	root->rch->min=-root->rch->min;
	swap(root->rch->max,root->rch->min);
	root->rch->sum=-root->rch->sum;

	root->neg=false;
}*/
//=========================================Tree Chain Div=====================================
int QuerySum(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		// printf("topx=%d topy=%d x=%d y=%d\n",top[x],top[y],x,y);
		if(deep[top[x]]<deep[top[y]])
			swap(x,y);
		ans+=QuerySum(N,id[top[x]],id[x]);
		x=prt[top[x]];
	}
	if(deep[x]>deep[y])
		swap(x,y);
	if(x!=y)
		ans+=QuerySum(N,id[x]+1,id[y]);
	return ans;
}

int QueryMin(int x,int y){
	int ans=INF;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])
			swap(x,y);
		ans=min(ans,QueryMin(N,id[top[x]],id[x]));
		x=prt[top[x]];
	}
	if(deep[x]>deep[y])
		swap(x,y);
	if(x!=y)
		ans=min(ans,QueryMin(N,id[x]+1,id[y]));
	return ans;
}

int QueryMax(int x,int y){
	int ans=-INF;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])
			swap(x,y);
		ans=max(ans,QueryMax(N,id[top[x]],id[x]));
		x=prt[top[x]];
	}
	if(deep[x]>deep[y])
		swap(x,y);
	if(x!=y)
		ans=max(ans,QueryMax(N,id[x]+1,id[y]));
	return ans;
}

void Negate(int x,int y){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])
			swap(x,y);
		Negate(N,id[top[x]],id[x]);
		x=prt[top[x]];
	}
	if(deep[x]>deep[y])
		swap(x,y);
	if(x!=y)
		Negate(N,id[x]+1,id[y]);
}

inline void Insert(int from,int to,int value){
	tope->to=to;
	tope->from=from;
	tope->value=value;
	tope->next=head[from];
	head[from]=tope;
	tope++;
}