左偏树
左偏树论文题。左偏树的优越性在于它可以不断找出树高最短的一段，因此能一直保持O(logn)的合并复杂度。
对于这题，先转成不降序列来做，只需-i
我们将序列先分成n段，则每一段的最优解z[i]=t[i]，从左到右一段一段做，考虑合并。
若z[i] <= t[i]，不需要合并。去做下一段。
若z[i] > t[i]，易证(感性地想，或者去看论文)两段的最优解应当是两段所有数字的中位数。于是合并两段并改最优解为中位数。去做下一段。
维护中位数的过程需要左偏树。
#include<cstdio> #include<algorithm> #define N 1000005 using namespace std; namespace ziqian { int a[N], hcnt, cnt[N], num[N], l[N], r[N], tot, root[N]; struct heap { int l, r, v, dis; }h[N]; int new_heap(int v) { h[++hcnt] = (heap){0,0,v,0}; return hcnt; } int merge(int x, int y)// big root { if(!x || !y)return x?x:y; if(h[x].v < h[y].v) swap(x, y); h[x].r = merge(h[x].r,y); if(h[h[x].l].dis < h[h[x].r].dis) swap(h[x].l, h[x].r); h[x].dis = h[h[x].l].dis + 1; return x; } int pop(int x) { return merge(h[x].l,h[x].r); } int abs(int x){return x>0?x:-x;} void main() { int n; scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); a[i]-=i; } for(int i = 1; i <= n; i++) { ++tot; root[tot] = new_heap(a[i]); l[tot] = r[tot] = i; cnt[tot] = num[tot] = 1; while(tot > 1 && h[root[tot-1]].v > h[root[tot]].v) { --tot; root[tot] = merge(root[tot], root[tot+1]); cnt[tot] += cnt[tot+1]; num[tot] += num[tot+1]; r[tot] = r[tot+1]; while(num[tot] > (cnt[tot]+1)/2) { root[tot] = pop(root[tot]); num[tot]--; } } } long long ans = 0; for(int i = 1; i <= tot; i++) { int tmp = h[root[i]].v; for(int j = l[i]; j <= r[i]; j++) ans += abs(a[j] - tmp); } printf("%lld\n",ans); } } int main() { ziqian::main(); }