[BZOJ 4919][Lydsy1706月赛]大根堆
ao神啊这题,,,
很显然的思路是设计状态,然后线段树合并或者线段树启发式合并转移来优化一下,但是真的不好写……
考虑求LIS的那个二分+单调数组来做,那个东西的本质其实就是维护了一堆各种长度的断点一样的东西(考虑答案为\(n\),\(n - 1\)……的情况,在值的选取上各个情况之间会有断点)。那么我们就用一个multiset来维护断点,然后启发式合并即可。
考虑一棵子树,把根的子树进行合并,根加进来之后对断点会有何影响?那么考虑现在那个multiset里那个东西的后继(要lower_bound,因为如果有和根权值一样的点的话拐点不会发生变化。这里讨论有后继的情况),如果要取到那个点的长度的LIS的话,现在只需要小于等于根的权值的点就行了,取到这个点也不会使LIS变大(它不能和根共存),所以那个点就不是拐点了。并且无论是否出现这种情况,根那个点都会成为一个新的拐点。
然后DFS一遍就行啦。
代码:
/************************************************************** Problem: 4919 User: danihao123 Language: C++ Result: Accepted Time:992 ms Memory:25648 kb ****************************************************************/ #include <cstdio> #include <set> #include <vector> const int maxn = 200005; std::vector<int> G[maxn]; std::multiset<int> *st[maxn]; void merge(int x, int y) { if(st[x] -> size() < st[y] -> size()) std::swap(st[x], st[y]); while(st[y] -> size() > 0) { std::multiset<int>::iterator it = st[y] -> begin(); int v = *it; st[y] -> erase(it); st[x] -> insert(v); } } int d[maxn]; void dfs(int x) { for(int i = 0; i < G[x].size(); i ++) { int v = G[x][i]; dfs(v); merge(x, v); } std::multiset<int>::iterator it = st[x] -> lower_bound(d[x]); if(it != (st[x] -> end())) st[x] -> erase(it); st[x] -> insert(d[x]); } int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i ++) { int f; scanf("%d%d", &d[i], &f); G[f].push_back(i); } for(int i = 1; i <= n; i ++) { st[i] = new std::multiset<int>(); } dfs(1); printf("%d\n", st[1] -> size()); for(int i = 1; i <= n; i ++) { delete st[i]; } return 0; }
[BZOJ 2733][HNOI2012]永无乡
我这题竟然很早就做了……
求k小显然可以用平衡树。但是这个题还需要快速的合并平衡树,那就需要启发式合并了。
[BZOJ 1483][HNOI2009]梦幻布丁
做了很久了吧,但现在才写题解……(斜眼
首先记录一个起始的颜色段数,然后每种颜色都要用链表顺序记下该颜色有哪些点。然后合并的时候合并两个链表——最优策略显然是启发式合并。
但是,很多时候并不是把小链表的扔到大的里面的情况,而是恰好反过来的情况,如何处理?
这种时候,我们可以交换两个颜色的“真实身份”。合并的时候,把每个点当成它的“真实身份”处理即可。