数据结构杂题选做

标签：颜色 线段 合并 区间 数据结构 杂题 dis

好像数据结构也没什么专项，那就全塞一起吧（大雾
好像wind_whisper神仙今天留的题也没什么专项。

P1972 [SDOI2009] HH的项链

居然没做过的“经典题”++。怎么到处都是经典题捏
一个区间内的相同颜色可以只考虑最右边的那个。把询问离线按右端点排序，每次遇到同一颜色 \(a_i\) 再次出现，则 \(add(i,1),add(lst_i,-1)\)，即删除上一次的贡献。
那么一边维护一边更新答案，答案就是 \([l,r]\) 的区间和。

P4113 [HEOI2012]采花

题意大概是数区间内出现超过 \(1\) 次的颜色数。采取上题的方法，同时记录 \(lst_i\) 和 \(lstlst_i\)，在加入新颜色时撤销掉 \(lstlst_i\) 的贡献。那这样求出来的答案是 大于2次颜色数*2+只有一次颜色数。
于是再维护一个原版的区间颜色数，把它们相减一下就好了qwq

P5327 [ZJOI2019]语言

撞上了前几天学线段树合并做的例题，好诶（） 当时没写博客，顺路来补个档qwq
树上路径覆盖问题，首先考虑树上差分。把一次“普及语言”拆成从节点到根的单点修改。
考虑这样一个性质：对于树上按 \(dfn\) 序排列的点集 \(S=a1,a2...a_n\) ，它们构成连通块（？）的边数是 (我不知道是不是这么叫

\[\frac{dis_{a_1,a_2}+dis_{a_2,a_3}+...+dis_{a_{n-1},a_n}+dis_{a_n,a_1}}{2} \]

依旧感性证明一下：因为已经把点按 \(dfn\) 序排列，上述柿子的路径并就经过联通块上的每条边恰好两次。
这个东西是可以线段树维护的。至于怎么合并两个区间，还需记录区间内最靠左/最靠右的点。
注意就是 \(dis_{r,l}\) 不用维护进去 不然咋合并，于是线段树的问题解决了。当前线段树根节点的值就是子树内能与 \(a_i\) 共通语言的人数。
把整棵线段树往上传递，线段树合并一下就好了。
写了一上午，不难理解但真的难调。

P3960 [NOIP2017 提高组] 列队

这题 wzh 老师讲过诶。可是他讲的时候我连树状数组线段树都还不会诶。

标签：颜色,线段,合并,区间,数据结构,杂题,dis
From： https://www.cnblogs.com/ying-xue/p/16986096.html