C. Colorful Segments 2
考虑最小的分组数量,可以先按左端点排序,然后每次贪心地找到前面一个最大右端点 \(r_j < l_i\) 的组加入。
考虑计数,还是同样地按左端点排序,那么假设现在有 \(k\) 个组,每个组最大右端点是 \(g_i\)(没有元素则 \(g_i = 0\)),那么每次可以选择一个 \(g_j < l_i\) 的组并且把 \(g_j\) 更新为 \(l_i\)。注意到我们不需要关心具体的 \(g_j\),只用关心 \(g_j < l_i\) 的数量。由于 \(l_i\) 是单增的,所以所有 \(g_j < l_i\) 的组 \(j\) 本质相同。那么就是每次查询 \(g_j < l_i\) 的数量,并且将其减 \(1\),并插入一个 \(r_i\),可以用堆模拟。复杂度 \(\Theta(n \log n)\)。
E. Sensors
由于恰好有 \(1\) 个点的线段是有用的,且每个点不会被重新加入,那不妨考虑每次删除点的时候快速找到所有从 \(>1\) 个变成 \(1\) 个的线段,和从 \(1\) 个变成 \(0\) 个的线段。
从 \(1\) 个变成 \(0\) 个是好维护的,只需要把 \(1\) 个的线段插入到那个点的 vector 中,删除的时候直接减去所有的贡献即可。
从 \(>1\) 个变成 \(1\) 个时,线段的左右端点恰好跨越一个点。设当前剩下的点坐标是 \(pos_1 < pos_2 < ... < pos_m\) 那么不妨用一个 multiset 维护每个 \(r_j \in [pos_i, pos_{i+1} - 1]\) 的 \(l_j\),删除 \(pos_i\) 时直接把 \(st_{pos_i}\) 合并到 \(st_{pos_{i-1}}\),并访问 \(st_{pos_{i-1}}\) 和 \(st_{pos_{i+1}}\) 最大的 \(l_j\) 更新即可。复杂度 \(\Theta(n\log^2n)\)。
考虑更优秀的复杂度,把每个线段插入到线段树上的 \(\log n\) 个节点,然后对于每个线段维护它所在的所有节点中点个数 \(=0,=1,>1\) 的节点个数,当更新一个节点 \(u\) 时,若 \(sum_u \le 1\) 就访问所有这个节点上的线段更新即可。复杂度 \(\Theta(n\log n)\)。
G. Cosmic Travel
差分转化为 \(x \le m\) 的第 \(k\) 大和,那么套路地枚举 \(x\) 和 \(m\) 的 lcp 下一位,在 trie 上模拟前这些位(若这一位是 \(0\),则先看 \(siz_{ls}\),不够就到 \(rs, k \leftarrow k - siz_{ls}\)),然后拆成 \(\Theta(\log V)\) 个询问一个子树异或任意数(不能超过这个子树能表示的最大数)的第 \(k_i\) 大和。注意到这个东西是与询问无关的,设 \(dp_{i,j}\) 为 \(i\) 子树异或任意数的第 \(j\) 大和,状态数量为 \(\Theta(n \log V)\) 的(每个叶子统计 \(\Theta(\log V)\) 次)。
这里为了方便,可以把和设为只看子树里的这些位的和,类似地模拟转移即可。
复杂度 \(\Theta((n+q)\log V)\)。
L. Intersection of Paths
考虑对于一个 \(k\),有那些点可能成为并的一个端点,考虑每一条边 \((u,v)\),如果删掉这条边后 \(\min(siz_u,siz_v) \ge k\) 这条边就合法,那么 \(u,v\) 就合法。那么假如不考虑更改边的话,答案就是只取这些点组成的虚树(一定是原树的一个联通块)的直径。
考虑 \(k\) 不同,并且加入更改边,由于大的 \(k\) 对应联通块一定被小 \(k\) 对应的完全包含,那么可以直径从小到大扫描线,每次从 \(k \to k + 1\) 时,把 \(\min(siz_u,siz_v) = k\) 的边删掉(更改边权为 \(0\))。
那么就是要实现动态修改边权,查询直径。考虑在欧拉序上做,每次遍历到 \(u\) 在 dfs 序后加入 \(u\),遍历 \(u\) 的 每个 儿子回来后再加入 \(u\)。然后就是要找到一个区间 \([l,r]\) 的 \(\max\limits_{l\le L \le a \le R\le r} dep_L + dep_R - 2 \times dep_a\),其中 \(a\) 肯定是 \([L,R]\) 中 \(dep\) 最小那个。于是线段树上维护区间信息 \(ans,ansl,ansr,maxd,mind\) 对应上述答案、\(\max\limits_{L \le a} dep_L - 2 \times dep_a\)、\(\max\limits_{a \le R} dep_R - 2 \times dep_a\),最大和最小 \(dep\)。合并时 \(ans = \max(ans_{ls},ans_{rs},ansl_{ls}+maxd_{rs},maxd_{ls}+ansr_{rs})\),\(ansl = \max(ansl_{ls},ansl_{rs},maxd_{ls} - 2\times mind_{rs}),ansr=\max(ansr_{ls},ansr_{rs},maxd_{rs} - 2\times mind_{ls})\)。
显然支持修改,复杂度 \(\Theta((n+q)\log n)\)。
标签:Provincial,Shandong,le,log,Contest,dep,线段,pos,ls From: https://www.cnblogs.com/MiniLong/p/18447323