【省选模拟赛】小奇的花园

2015年12月19日3,5633

原题:【泉七培训-刘定峰】花园

【题目背景】

小奇在家中的花园漫步时,总是会思考一些奇怪的问题。

【问题描述】

小奇的花园有n个温室,标号为1到n,温室以及以及温室间的双向道路形成一棵树。

每个温室都种植着一种花,随着季节的变换,温室里的花的种类也在不断发生着变化。

小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。

【输入格式】

第一行为两个整数n,q,表示温室的数目和操作的数目。

第二行有n个整数T1,T2…Tn其中Ti表示温室i中的花的种类。

接下来n-1行,每个两个整数x, y,表示温室x和y之间有一条双向道路。

接下来q行,表示q个操作,分别为以下两种形式之一:

• C x t 表示在温室x中的花的种类变为t。

• Q x y t 表示询问温室x走到温室y的路径中(包括两个端点),第t种花出现

的次数。

为了体现在线操作,输入数据中的每个操作的参数都进行了加密。记最后一次询问的答案为anslast(一开始设anslast为0),下次读入中的x,y,t均需要异或上anslast以得到真实值,在C/C++中异或为ˆ运算符,在pascal中为xor运算符。

【输出格式】

输出q行,每行一个正整数表示该次询问答案。

【样例输入】

5 8

10 20 30 40 50

1 2

1 3

3 4

3 5

Q 2 5 10

C 2 21

Q 3 4 21

C 6 22

Q 1 7 28

C 5 20

Q 2 5 20

Q 2 0 9

【样例输出】

1

2

0

3

1

【样例解释】

加密前的操作:

Q 2 5 10

C 3 20

Q 2 5 20

C 4 20

Q 3 5 30

C 5 20

Q 2 5 20

Q 1 3 10

【数据范围】

对于30%的数据,有n <= 1000, q <= 2000。

对于50%的数据,有n <= 10000, q <= 20000。

对于100%的数据,有n <= 100000, q <= 200000,0 <= T < 2^31。

【题解】

对于50%的数据,求出lca然后暴力

当年做这题的时候我很年轻,正好做了CTSC网络管理,就现场写了暴力:树链剖分+线段树套平衡树,这个做法应该很直接。其实对每一种权值建一棵线段树就不需要平衡树了,不过需要用map来存种类,但是这样还是很麻烦。

对于100%的数据

运用部分和思想把单点修改,路径查询转化成子树修改,单点询问。

具体地说我们用Vi 表示点i 的权值,Si 表示点i 到根节点上的权值和,那么询问x y 路径的权值和时,我们找到x y lca 那么答案就是Sx + Sy – 2Slca + Vlca. 而如果修改点x 的权值,就相当于x 子树上所有点的Si 都加上了一个数,我们只要先处理DFS序列之后就转化成区间加,这样可用线段树或者树状数组实现。

70分 树链剖分+线段树套平衡树 4个log几乎相当于暴力,但是常数小

100分

 

  • 杨乾澜2016年2月6日 上午10:16 回复

    学长请问,直接向100分做法一样,用map存一下,然后每个种类建一颗线段树直接做树剖不就好了?

    #1  
  • 丨单色独白丨2016年4月21日 上午7:21 回复

    同楼上,学长,可以类似[sdoi2014旅行]一样对每一个种类建一棵线段树,动态开点吧

    #2  
  • 蒟蒻2016年7月8日 下午8:54 回复

    吾王赛高

    #3