BZOJ 3531 [Sdoi2014]旅行 树链剖分+动态开点线段树

题意

S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。

为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

在S国的历史上常会发生以下几种事件：

“CC x c“：城市x的居民全体改信了c教；

“CW x w“：城市x的评级调整为w;

“QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；

“QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

分析

对每种宗教建一颗动态开点线段树，不动态开点稳Tle+Mle的，然后就树链剖分裸题啊，对于查询操作，查询出发城市的信仰宗教的线段树就行了

这题写完就过编译和样例了，然后在bzoj一交秒Tle??内存636kb？？感觉数据有问题去洛谷交了下，一发过!

Code

#include
#define fi first
#define se second
#define pb push_back
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
using namespace std;
typedef long long ll;
const int inf=1e9;
const int maxn=2e5;
int n,q;
int w[maxn],c[maxn];
vectorg[maxn];
int sz[maxn],son[maxn],top[maxn],p[maxn],d[maxn],f[maxn],id[maxn],tot;
int val[maxn*300],mx[maxn*300],ls[maxn*300],rs[maxn*300],rt[maxn],o;
void up(int x,int l,int r,int &p,int k){val[++o]=val[p],mx[o]=mx[p],ls[o]=ls[p],rs[o]=rs[p],p=o;if(l==r) return val[p]=mx[p]=k,void();int mid=l+r>>1;if(x<=mid) up(x,l,mid,ls[p],k);else up(x,mid+1,r,rs[p],k);val[p]=val[ls[p]]+val[rs[p]];mx[p]=max(mx[ls[p]],mx[rs[p]]);
}
int qy(int dl,int dr,int l,int r,int p){if(l>=dl&&r<=dr) return val[p];int mid=l+r>>1;int ret=0;if(dl<=mid) ret+=qy(dl,dr,l,mid,ls[p]);if(dr>mid) ret+=qy(dl,dr,mid+1,r,rs[p]);return ret;
}
int qmx(int dl,int dr,int l,int r,int p){if(l>=dl&&r<=dr) return mx[p];int mid=l+r>>1;int ret=-inf;if(dl<=mid) ret=max(qmx(dl,dr,l,mid,ls[p]),ret);if(dr>mid) ret=max(qmx(dl,dr,mid+1,r,rs[p]),ret);return ret;
}
void dfs1(int u){sz[u]=1;d[u]=d[f[u]]+1;for(int i=0;isz[son[u]]) son[u]=x;}
}
void dfs2(int u,int t){top[u]=t;p[u]=++tot;id[tot]=u;if(son[u]) dfs2(son[u],t);for(int i=0;i

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