- https://www.spoj.com/problems/COT6/
- https://github.com/lychees/ACM-Training/tree/master/Archive/Spoj/COT%20%E7%B3%BB%E5%88%97/COT6
前排膜拜主席。。。
算法一:李超线段树 + 线段树合并
DP 结构和 COT3 一样,方程和 Cash 一样,都是动态维护凸壳,询问与某个向量的点积的最小值。。。
后来我系统的学习了一下 线段树合并,
然后发现有一个题的做法是李超线段树 + 线段树合并,来搞树上 dp。。。
这个题的方程和那个题差不多。。。询问向量都是 (x, 1),所以用 kx+b 来搞更方便。。。
可以预处理出所有的 sw,来做离散化,然后打标记只要整体平移 b,不会影响线段树的结构。。。
然后就没有然后了。。。复杂度 O(nlog2n)。。。
经过这个题我们发现。。线性分段函数极值 和 动态凸包 问题是等价的。。
根据情况可以互相转换。。看怎么写好写。。。
似乎还有一种 O(nlogn) 的做法。。。dfs 序 + cdq 分治。。。(尝试了一下失败了,原因是 cdq 分治两边的状态会互相依赖。。。)
晚上再试试。。。
我发现之前的模板里有一个 bug 的地方(我靠居然连 COT6 的样例都过不去。。)
if (T[x].y(ml) > t.y(ml) || T[x].y(mr) > t.y(mr)) swap(T[x], t); //!
就是上面这行,必须要两边都检查一次,否则有可能恰好在边界,然后又相等的话,我这种写法就炸了。。。。
算法二:平衡树维护凸壳 + 启发式合并
https://t.me/TwilightParliament/102671
平衡树有很多写法。。。如果选择 Splay 的话,复杂度可以变成 O(nlogn) 。。。Splay 有着许多非常神奇的性质。。
比如 Dynamic Finger Property 。。。
对于 n>=m,把 m 个有序的元素按顺序插到一个已经有 n 个元素的 Splay 里。。
时间复杂度是 O(mlog(n/m))。。。
一通计算,可以证明启发式合并 n 个东西 from scratch 的总开销是 O(nlogn)。。
(在 n 个元素里顺序访问 m 个的总开销差不多就是把 n 分成 m 个数的和,log 以后加起来。
根据log的凹性,最差的情况是 m 个都是 n/m。。。)
不过我试图找以前自己的 Splay 维护凸壳的模板。。。交以前的题居然 WA 了。。。于是去搜了一下看看大家现在是怎么做的。。。
于是 找到了一份非常短的 Multiset 维护凸壳的代码。。。。。
考据了一下。。来自 CF 的某个瑞典的 IGM 选手 simonlindholm。。
模板仓库在 这里。。。
个人感觉这份代码实现的非常优秀。。。特别是插入过程。。。比 CLJ 的版本 都要短好多。。。
这个是一堆线性函数求极值的。。然后 p 维护的是相邻直线的交点。。。
查询的时候直接用 p 去二分查找就可以了。。。
只要对每个凸壳整体打标记,然后把模板从求最大改成求最小就可以通过了。。
const int N = int(1.2e6) + 9; #define ll LL struct Line { mutable ll k, m, p; ll eval (ll x) { return k*x+m; } bool operator<(const Line& o) const { return k > o.k; } bool operator<(ll x) const { return p < x; } }; struct LC : multiset<Line,less<> > { const ll inf = LLONG_MAX; LL up; ll div(ll a, ll b) { return a/b - ((a^b) < 0 && a%b); } ll bet(const Line& x, const Line& y) { if (x.k == y.k) return x.m <= y.m ? inf : -inf; return div(y.m-x.m, x.k-y.k); } bool isect(iterator x, iterator y) { if (y == end()) { x->p = inf; return 0; } x->p = bet(*x,*y); return x->p >= y->p; } void add(ll k, ll m) { m -= up; auto z = insert({k,m,0}), y = z++, x = y; while (isect(y,z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y=erase(y)); while ((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } ll query(ll x) { assert(!empty()); auto l = *lower_bound(x); return l.k*x+l.m + up; } } H[N]; int HH[N]; const int NN = N * 20; int n; VI adj[N]; LL sw[N], dp[N]; int sz[N]; #define hu H[HH[u]] #define hv H[HH[v]] void dfs(int u,int p) { sw[u] += sw[p]; sz[u] = 1; LL s = 0; int max_sz = 0, vv = 0; for (auto v: adj[u]) if (v != p) { dfs(v, u); s += dp[v]; sz[u] += sz[v]; if (checkMax(max_sz, sz[v])) vv = v; } if (max_sz) { HH[u] = HH[vv]; hu.up += s - dp[vv]; for (auto v: adj[u]) if (v != p && v != vv) { hv.up += s - dp[v]; for (auto p: hv) { hu.add(p.k, p.m + hv.up); } } } else { HH[u] = u; } hu.add(sw[u], s + sqr(sw[u])); dp[u] = sqr(sw[p]) + hu.query(-2*sw[p]); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif RD(n); REP_1(i, n) RDD(sw[i]); DO(n-1) { int u, v; RD(u, v); adj[u].PB(v); adj[v].PB(u); } dfs(1,0); OT(dp[1]); }