近期看了一些先辈的文章……柑橘要刷一些CC力,,,
怕不是有一半题都是毒瘤数据结构?
QTREE6 Query on a tree VI
Description
有一棵n个点的有颜色的树,初始时每一个点都是白色。要求你支持以下两种操作(共m次):
0 u
:查询u所在的连通块有几个点。这里的话一条边当且仅当两边颜色一样才会生效。1 u
:翻转u的颜色。
1≤n,m≤105。
Solution
记得大约一年前多听过一个挺毒瘤的树剖做法……然而柑橘还事动态树简单哎。
把每个点拆成白点和黑点,每个点如果是白色的那么他的白点向父亲连边,反之亦然,并且两者只能择其一。可以发现如果一个点所在的森林的根是同色的话那么就取根的子树大小就行了,其他情况特判一下取下面一个点。
然后还剩下一个问题就是在动态树上维护子树大小……这个的当然可以直接ETT,不过我从来没写过LCT维护子树信息所以就用了LCT。LCT维护子树信息倒也简单,就在每个Splay结点上额外开个域维护它的虚儿子信息就行了,access和link-cut的时候再修改一下这个信息,然后就做完了……
Code
1 |
|
FNCS Chef and Churu
Description
你有一个长度为n的数字序列A,以及一个长度为n的函数序列F(Fi定义为∑Rik=LiAk)。要求你支持以下两种操作:
1 x y
:将Ai变成y。2 l r
:求∑ri=lFi。
1≤n≤105,1≤Ai,y≤109。
Solution
很显然常规数据结构无能为力……那就毒瘤分块吧!其实这是我做的第一道不水的分块题……
我们考虑对序列F分块。这样的话查询倒还好说,整块的话直接加,散块的话暴力扫一下用树状数组求和。那修改咋整?
修改对散块的影响不需要考虑,只需要考虑对整块的影响。我们可以扫每一个块,然后考虑修改对答案的影响。假设这个修改使得Ai变大了d,那么对于一个块k其答案就会变大cntk,id,其中cntk,i表示块k中有多少个函数包含了位置i,这个可以在预处理时很容易的用差分搞出来。
还有一点就是你用long long
会溢出……要开unsigned long long
。
Code
1 |
|
MONOPOLY Gangsters of Treeland
Description
有一棵n个点的点有颜色的树,以0为根,初始时任意两点颜色不同。一条边在两边颜色不一样时边权为1,其他情况下为0。
现在要求你支持两种操作:
O u
:搞出来一种全新的颜色,然后把u到根上所有点都染上该颜色。q u
:求u所在子树所有点到根路径长度的平均值。
Solution
感觉像是某些套路的万恶之源?
我们把两边颜色不一样的边看成虚边,其他看成实边,那么到根路径长度就是到根路径虚边数量。初始时整个树全是虚边。
然后我们发现第一种操作其实和access一模一样……所以用线段树+DFS序维护子树权值,access的时候改一下,然后没了……
Code
1 |
|