BZOJ2157 旅游

Description

Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N − 1 座桥。Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座桥会增加w 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。现在，Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。

Input

输入的第一行包含一个整数N，表示T 城中的景点个数。景点编号为 0…N − 1。接下来N − 1 行，每行三个整数u、v 和w，表示有一条u 到v，使 Ray 愉悦度增加w 的桥。桥的编号为1…N − 1。|w| <= 1000。输入的第N + 1 行包含一个整数M，表示Ray 的操作数目。接下来有M 行，每行描述了一个操作，操作有如下五种形式： C i w，表示Ray 对于经过第i 座桥的愉悦度变成了w。 N u v，表示Ray 对于经过景点u 到v 的路径上的每一座桥的愉悦度都变成原来的相反数。 SUM u v，表示询问从景点u 到v 所获得的总愉悦度。 MAX u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最大愉悦度。 MIN u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最小愉悦度。测试数据保证，任意时刻，Ray 对于经过每一座桥的愉悦度的绝对值小于等于1000。

Output

对于每一个询问(操作S、MAX 和MIN)，输出答案。
（样例略）
HINT

一共有10 个数据，对于第i (1 <= i <= 10) 个数据， N = M = i * 2000。

树链剖分裸题。线段树代码量巨大，一定要沉得住气。
注意，反转一个节点要将其标记异或1，而不是直接对其赋值。因为这个WA了很久。
自己的代码：

#include 
#define gm 20001 
using namespace std; 
int n,m; 
struct e 
{ int t,v; e *n; e (int t,e *n,int v):t(t),n(n),v(v){} 
}*b[gm]={}; 
inline int max(int a,int b){return aint min(int a,int b){return a#define swap(a,b) a^=b^=a^=b 
#define link(x,y,z) b[x]=new e(y,b[x],z);b[y]=new e(x,b[y],z) 
#define along(x) for(e *i=b[x];i;i=i->n) 
#define getm int mid=(l+r)/2,p=o<<1,q=(o<<1)+1 
//begin 
int size[gm],fat[gm],hev[gm],dpt[gm],ord[gm],top[gm],now=0,q1[gm],q2[gm],qv[gm];
void first(int x) 
{ size[x]=1; dpt[x]=dpt[fat[x]]+1; int y; along(x) { y=i->t; if(fat[x]==y) continue; fat[y]=x; first(y); size[x]+=size[y]; if(size[y]>size[hev[x]]) hev[x]=y; } 
} 
void second(int x) 
{ top[x]=x==hev[fat[x]]?top[fat[x]]:x; ord[x]=++now; if(hev[x]) second(hev[x]); int y; along(x) { y=i->t; if(fat[x]==y||hev[x]==y) continue; second(y); } 
} 
//end 
//------------------------------------------- 
//begin 
int sum[gm*4],maxx[gm*4],minn[gm*4]; 
bool rev[gm*4]; 
int x,y,v,ans; 
void change(int l,int r,int o) 
{ if(l==r) { sum[o]=maxx[o]=minn[o]=v; rev[o]=0; return; } getm; if(rev[o]) v=-v;if(x<=mid) change(l,mid,p); else change(mid+1,r,q); sum[o]=sum[p]+sum[q]; maxx[o]=max(maxx[p],maxx[q]); minn[o]=min(minn[p],minn[q]);if(rev[o]){sum[o]=-sum[o]; int a=maxx[o]; maxx[o]=-minn[o]; minn[o]=-a; }
} 
inline void change(int pos,int val) 
{ x=pos;v=val; change(1,n,1); 
} 
void seija(int l,int r,int o) 
{ if(x<=l&&r<=y) { rev[o]^=1; sum[o]=-sum[o]; int a=maxx[o]; maxx[o]=-minn[o]; minn[o]=-a; return; }getm;if(x<=mid) seija(l,mid,p); if(mid<y) seija(mid+1,r,q); sum[o]=sum[p]+sum[q]; maxx[o]=max(maxx[p],maxx[q]); minn[o]=min(minn[p],minn[q]);if(rev[o]){sum[o]=-sum[o]; int a=maxx[o]; maxx[o]=-minn[o]; minn[o]=-a; } 
} 
inline void seija(int ll,int rr) 
{ x=ll;y=rr; seija(1,n,1); 
} 
void getsum(int l,int r,int o,bool nz) 
{ if(x<=l&&r<=y) { ans+=nz?-sum[o]:sum[o]; return; } getm; if(rev[o]) nz^=1;if(x<=mid) getsum(l,mid,p,nz); if(mid<y) getsum(mid+1,r,q,nz); 
} 
inline int getsum(int ll,int rr) 
{ x=ll;y=rr;ans=0; getsum(1,n,1,0); return ans; 
} 
void getmax(int l,int r,int o,bool nz) 
{ if(x<=l&&r<=y) { if(!nz) ans=max(ans,maxx[o]); else ans=max(ans,-minn[o]);return; } getm;if(rev[o]) nz^=1; if(x<=mid) getmax(l,mid,p,nz); if(mid<y) getmax(mid+1,r,q,nz); 
} 
inline int getmax(int ll,int rr) 
{ x=ll;y=rr;ans=-2000000000; getmax(1,n,1,0); return ans; 
} 
void getmin(int l,int r,int o,int nz) 
{ if(x<=l&&r<=y) { if(!nz) ans=min(ans,minn[o]); else ans=min(ans,-maxx[o]);return; } getm; if(rev[o]) nz^=1;if(x<=mid) getmin(l,mid,p,nz); if(mid<y) getmin(mid+1,r,q,nz); 
} 
inline int getmin(int ll,int rr) 
{ x=ll;y=rr;ans=2000000000; getmin(1,n,1,0); return ans; 
} 
//end 
//------------------------------- 
//begin 
int work_s(int beg,int end) 
{ int all=0; while(top[beg]!=top[end]) { if(dpt[top[beg]]ord[top[beg]],ord[beg]); beg=fat[top[beg]]; } if(beg==end) return all; if(dpt[end]ord[beg]+1,ord[end]); return all; 
} 
int work_a(int beg,int end) 
{ int all=-2000000000; while(top[beg]!=top[end]) { if(dpt[top[beg]]ord[top[beg]],ord[beg])); beg=fat[top[beg]]; } if(beg==end) return all; if(dpt[end]ord[beg]+1,ord[end])); return all; 
} 
int work_i(int beg,int end) 
{ int all=2000000000; while(top[beg]!=top[end]) { if(dpt[top[beg]]ord[top[beg]],ord[beg])); beg=fat[top[beg]]; } if(beg==end) return all; if(dpt[end]ord[beg]+1,ord[end])); return all; 
} 
void work_r(int beg,int end) 
{ while(top[beg]!=top[end]) { if(dpt[top[beg]]ord[top[beg]],ord[beg]); beg=fat[top[beg]]; }if(beg==end) return; if(dpt[end]ord[beg]+1,ord[end]); 
} 
inline void work_c(int no,int val)
{if(fat[q1[no]]==q2[no]) change(ord[q1[no]],val);else change(ord[q2[no]],val);
}
//end 
//-------------------------------- 
//begin 
int main() 
{scanf("%d",&n); int s2,s3,s4; for(int i=1;i"%d%d%d",&s2,&s3,&s4); link(s2+1,s3+1,s4); q1[i]=s2+1; q2[i]=s3+1; qv[i]=s4; } first(1); second(1); for(int i=1;i5]; scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%s%d%d",s1,&s2,&s3); if(s1[0]=='C') work_c(s2,s3);else if(s1[0]=='N') work_r(s2+1,s3+1); else if(s1[0]=='S') printf("%d\n",work_s(s2+1,s3+1)); else if(s1[1]=='A') printf("%d\n",work_a(s2+1,s3+1)); else if(s1[1]=='I') printf("%d\n",work_i(s2+1,s3+1)); } return 0; 
} 
//end

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！