A
略
B
略
C
略
D
略
E
略
G
这题比F简单很多,但是两题都不难。
考虑枚举 \(w\) 的位置,把它拎起来当根,然后考虑一个儿子 \(son\) 认为 \(u\) 在它的子树内。
实际上,我们不可能把 \(w\) 拎起来当根,所以我们对 \(son\) 分两类讨论:
-
\(son\) 是 \(w\) 的儿子,我们求出 \(v\) 的数量,然后子树加。怎么求 \(v\) 的数量?考虑一个子树在dfs序上是连续的,那么按照dfs树建立主席树容易求出比 \(w\) 大 的 \(v\) 的数量。
-
\(son\) 是 \(w\) 的父亲,求出 \(v\) 的数量也是类似,但是怎么加到 \(u\) 上去?发现除了 \(w\) 这个子树外的节点的dfs序最多是两个区间,区间加法即可。
时间复杂度 \(O(n \log n)\) 。
F
思路点拨
考率数组倍长,然后变成滑动窗口问题。
考虑对于一个长度为 \(n\) 的窗口存在一个 \(lim\) ,使得在 \(lim\) 个元素的时候每一个盒子都有元素并且 \(lim\) 最小。容易知道 \(lim\) 随着滑动窗口左端点变大而变大。如果对于每一个窗口求出 \(lim\) 可以维护一个元素桶和指针一路扫过去线性求出。
考虑知道了 \(lim\) 怎么求出一个区间的答案?考虑使用multiset维护当前局面的每一个盒子的颜色以及球的数量。每一次区间的左端点加一的时候,可能导致multiset里面减少一个盒子,右端点增加的时候可能导致增加一个盒子,但都是好维护的。问题在于可能存在元素比 \(lim\) 大,但是依然会出现在盒子中。
考虑到盒子增减的变化总数是 \(O(n)\) 级别的,我们在滑动窗口的过程中维护一个桶表示当前区间有多少个 \(i\) 元素不在盒子里面,减少桶或者移动右端点会增加桶,增加盒子会减少桶,这个可以维护。在左端点变大的时候盒子的增减变化以及右端点新增的元素总量为 \(O(n)\) 级别,配合上桶完成分配。
时间复杂度 \(O(n \log n)\) 。可能讲的不是太好,比较抽象的一题。
标签:盒子,报告,lim,元素,abc337,解题,端点,窗口,son From: https://www.cnblogs.com/Diavolo/p/17998011