[BZOJ3531/Luogu3313][Sdoi2014]旅行(树链剖分,线段树)

发布于 2018-02-04  119 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3531/Luogu3313][Sdoi2014]旅行(树链剖分,线段树)

Description

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

Http

BZOJ
Luogu

Tag

树链剖分,线段树

解决思路

比价好想的就是树链剖分后对每一种宗教单独开一棵线段树维护,这样的话就可以直接对每一种宗教查询了。
但空间是开不下的,考虑到其实我们只要用到其中的部分空间,所以可以动态地开线段树的点,这样就可以了。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3531/Luogu3313][Sdoi2014]旅行(树链剖分,线段树)


HNCJ OIer