这不是可并堆裸题吗……我这种傻逼只会用线段树合并做

显然一个集合的中位数可以用平衡树或者权值线段树求出，然后为了方便合并我用了权值线段树。

然后考虑对于一个递减的序列，选择中位数一定更优，一个递增的序列当然xjb选即可。我们可以用一个栈来维护当前的所有答案区间，然后考虑一个新的点加进来。这个点的答案如果比栈首答案小，那么就违反了单调不降的要求，我们需要把两段合并。然后完了……

代码：

/**************************************************************
	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;
}

• 相关文章
• 全局相关文章