dp 可并堆 uoj205【APIO2016】Fireworks

#include
#define int long long
#define fo(i, n) for(int i = 1; i 
#define out(x) cerr \n"
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); ++ it)
using namespace std;
// by piano
templatetypename tp> inline void read(tp &x) {
  x = 0;char c = getchar(); bool f = 0;
  for(; c '0' || c > '9'; f |= (c == '-'), c = getchar());
  for(; c >= '0' && c '9'; x = (x 3) + (x 1) + c - '0', c = getchar());
  if(f) x = -x;
}
templatetypename tp> inline void arr(tp *a, int n) {
  for(int i = 1; i " ";
  puts("");
}
const int N = 6e5 + 233;
int n, m, fa[N], w[N], sz[N], ans = 0;
int key[N], fix[N], sa = 0, L[N], R[N], rt[N];
inline int nw(int val) {
  ++ sa; L[sa] = R[sa] = 0;
  key[sa] = val;
  fix[sa] = rand();
  return sa;
}

inline int make(int x, int y) {
  if(!x || !y) return x | y;
  if(key[x] if(fix[x] else 
    L[x] = make(L[x], y);
  return x;
}

inline void pop(int x) {
  rt[x] = make(L[rt[x]], R[rt[x]]);
}

inline void dfs(int x) {
  if(!x) return ;
  cout " " "\n";
  dfs(L[x]); dfs(R[x]);
}

main(void) {
  srand(20021214);
  read(n); read(m);
  int all = n + m;
  for(int i = 2; i for(int i = all; i >= 2; i --) {
    int l = 0, r = 0;
    if(sz[i]) {
      while(-- sz[i]) pop(i);
      r = key[rt[i]]; pop(i);
      l = key[rt[i]]; pop(i);
    }
    l = nw(l + w[i]);
    r = nw(r + w[i]);
    rt[i] = make(rt[i], make(l, r));
    rt[fa[i]] = make(rt[fa[i]], rt[i]);
  }
  while(sz[1] --) pop(1);
  while(rt[1]) {
    ans -= key[rt[1]];
    pop(1);
  }
  cout "\n";
}