【BZOJ-1367】sequence 可并堆+中位数

1367: [Baltic2004]sequence

Time Limit: 20 Sec  Memory Limit: 64 MB
Submit: 932  Solved: 348
[Submit][Status][Discuss]

Description

Input

Output

一个整数R

Sample Input

7
9
4
8
20
14
15
18

Sample Output

13

HINT

所求的Z序列为6,7,8,13,14,15,18.
R=13

Source

Solution

论文中的例题，非常吼啊….思想巧妙

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int read()
{
    int x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define maxn 1000100
long long ans;
int n,data[maxn],root[maxn],L[maxn],R[maxn],cnt[maxn],tot;
struct LeftTreeNode
{
    int sz,son[maxn][],d[maxn],size[maxn],a[maxn];
//    LeftTreeNode ()
//        {
//            sz=0;memset(son,0,sizeof(son));memset(size,0,sizeof(size));
//            memset(cnt,0,sizeof(cnt));memset(a,0,sizeof(a));memset(d,0,sizeof(d));
//        }
    int Merge(int x,int y)
        {
            if (!x) return y;
            if (!y) return x;
            if (a[x]<a[y]) swap(x,y);
            son[x][]=Merge(son[x][],y);
            size[x]=size[son[x][]]+size[son[x][]]+;
            if (d[son[x][]]>d[son[x][]]) swap(son[x][],son[x][]);
            d[x]=d[son[x][]]+;
            return x;
        }
    int Push(int x)
        {
            a[++sz]=x; size[sz]=;
            son[sz][]=son[sz][]=d[sz]=;
            return sz;
        }
    int Pop(int x) {return Merge(son[x][],son[x][]);}
    int Top(int x) {return a[x];}
    int Size(int x) {return size[x];}
}LTHeap;
int main()
{
    n=read();
    for (int i=; i<=n; i++) data[i]=read()-i;
    for (int i=; i<=n; i++)
        {
            tot++;
            root[tot]=LTHeap.Push(data[i]); cnt[tot]=; L[tot]=R[tot]=i;
            while (tot> && LTHeap.Top(root[tot])<LTHeap.Top(root[tot-]))
                {
                    tot--;
                    root[tot]=LTHeap.Merge(root[tot],root[tot+]); cnt[tot]+=cnt[tot+]; R[tot]=R[tot+];
                    while (LTHeap.Size(root[tot])*>cnt[tot]+)
                        root[tot]=LTHeap.Pop(root[tot]);
                }
        }
    for (int i=; i<=tot; i++)
        for (int j=L[i],top=LTHeap.Top(root[i]); j<=R[i]; j++)
            ans+=abs(data[j]-top);
    printf("%lld\n",ans);
    return ;
}

被YveH发现了…