[BZOJ 5059]前鬼后鬼的守护
这不是可并堆裸题吗……我这种傻逼只会用线段树合并做
显然一个集合的中位数可以用平衡树或者权值线段树求出，然后为了方便合并我用了权值线段树。
然后考虑对于一个递减的序列，选择中位数一定更优，一个递增的序列当然xjb选即可。我们可以用一个栈来维护当前的所有答案区间，然后考虑一个新的点加进来。这个点的答案如果比栈首答案小，那么就违反了单调不降的要求，我们需要把两段合并。然后完了……
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | /************************************************************** Problem: 5059 User: danihao123 Language: C++ Result: Accepted Time:2348 ms Memory:250520 kb****************************************************************/#include <cstdio>#include <cstring>#include <cstdlib>#include <cctype>#include <cassert>#include <algorithm>#include <utility>#include <stack>const int BUFSIZE = 20 * 1024 * 1024;int n;struct Node { Node *lc, *rc; int sumv;};Node pool[BUFSIZE];Node *nil, *cur;void init_pool() { cur = nil = pool; nil -> lc = nil -> rc = nil; nil -> sumv = 0;}Node *alloc_node(int v = 0, Node *lc = nil, Node *rc = nil) { cur ++; cur -> lc = lc; cur -> rc = rc; cur -> sumv = v; return cur;}void modify(Node* &o, int L, int R, int p, int v) { if(o == nil) { o = alloc_node(0); } o -> sumv += v; if(L < R) { int M = (L + R) / 2; if(p <= M) { modify(o -> lc, L, M, p, v); } else { modify(o -> rc, M + 1, R, p, v); } }}Node *merge(Node* &tag, Node* &src) { if(src == nil) return tag; if(tag == nil) { return src; } tag -> sumv += src -> sumv; tag -> lc = merge(tag -> lc, src -> lc); tag -> rc = merge(tag -> rc, src -> rc); return tag;}int kth(Node *o, int L, int R, int k) { if(L == R) { return L; } else { int M = (L + R) / 2; if(k <= o -> lc -> sumv) { return kth(o -> lc, L, M, k); } else { return kth(o -> rc, M + 1, R, k - o -> lc -> sumv); } }}void gou_tree(Node *o, int L, int R) { printf("Tree (%d, %d, %d)\n", L, R, o -> sumv); int M = (L + R) / 2; if(L < R) { gou_tree(o -> lc, L, M); gou_tree(o -> rc, M + 1, R); }}int lsiz;const int maxn = 500005;int A[maxn], A2[maxn];void break_up() { std::sort(A2 + 1, A2 + 1 + n); lsiz = std::unique(A2 + 1, A2 + 1 + n) - A2 - 1; for(int i = 1; i <= n; i ++) { A[i] = std::lower_bound(A2 + 1, A2 + 1 + lsiz, A[i]) - A2; }}struct Interval { Node *rt; int l, r; int siz, ans; Interval() { rt = nil; siz = ans = 0; } Interval(int p) { rt = nil; modify(rt, 1, lsiz, p, 1); siz = 1; ans = p; }};typedef long long ll;ll solve() { break_up(); init_pool(); std::stack<Interval> S; for(int i = 1; i <= n; i ++) { Interval nv(A[i]); nv.l = nv.r = i; while(!S.empty() && S.top().ans > nv.ans) { Interval g = S.top(); S.pop();#ifdef LOCAL printf("ans of [%d, %d] : %d\n", g.l, g.r, A2[g.ans]);#endif nv.l = g.l; nv.siz += g.siz; nv.rt = merge(nv.rt, g.rt);#ifdef LOCAL gou_tree(nv.rt, 1, lsiz);#endif nv.ans = kth(nv.rt, 1, lsiz, (nv.siz + 1) / 2); } S.push(nv); } ll ans = 0; while(!S.empty()) { Interval g = S.top(); S.pop();#ifdef LOCAL printf("ans of [%d, %d] : %d\n", g.l, g.r, A2[g.ans]);#endif for(int i = g.l; i <= g.r; i ++) { ans += abs(A2[A[i]] - A2[g.ans]); } } return ans;}int main() { scanf("%d", &n); for(int i = 1; i <= n; i ++) { scanf("%d", &A[i]); A2[i] = A[i]; } printf("%lld\n", solve()); return 0;} |
