左偏树基本代码如下：
struct node
{
    int key,dist;
    node *left,*right;
}*S[NMax];
void make(node *a,int K)
{
    a->key=K;
    a->dist=0;
    a->left=a->right=NULL;
}
node* merge(node *a,node *b)
{
    if(a==NULL) return b;
    if(b==NULL) return a;
    if(a->key<b->key) swap(a,b);
    a->right=merge(a->right,b);
    if(a->left==NULL || a->right->dist>a->left->dist)
        swap(a->right,a->left);
    if(a->right==NULL) a->dist=0;
    else a->dist=a->right->dist+1;
    return a;
}
这道题与3666类似，都必需要有http://wenku.baidu.com/view/20e9ff18964bcf84b9d57ba1.html
这篇论文中数字序列那题的基础。
先大概说一下那题的思路：把整个序列分成若干块，每一块都改成那一块的中位数，而且保证每个块的中位数不小于前一个块的

那么就用左偏树维护这几个块的中位数，用栈来维护这些块

S1:（假设前i-1个数的块已经分好了）先把第i个数以一个数新开个块

S2:检查栈顶top的块的中位数是不是比top-1的要小，如果是则转S3，否则继续做下一个数i+1直到n个数都做完

S3:合并top和top-1两个块，转S2

至于中位数怎么维护，其实是很简单的

一个块如果有n个数，你只保留较小的(n+1)div 2个就可以了，用左偏树做个最大堆，最大的元素就是中位数

就每个左偏树维护4个东西

堆中元素个数now[i]、这些数的和s[i]、属于这个堆但被从堆中去掉的元素个数go[i]、这些数的和b[i]

最后ans=Sum每个块(该块中位数*now[i]-s[i]+b[i]-go[i]*中位数)

时间复杂度O(nlogn)


上述算法在论文里讲的更详细一点，你还可以参考一下那篇论文
还可以参考这里：
http://poj.org/showmessage?message_id=172619
再说这一题的方法：
预处理
由于题目要求要使序列递增，而上一题的那个算法处理的只能是非降，其实很简单，我们要使a[i-1]<a[i]，可以转化为a[i-1]+1<=a[i]——>a[i-1]-(i-1)<=a[i]-i（即a[i-1]-i<a[i]-i），令b[i]=a[i]-i，即维护b[i]非降。
同理，a[i-1]>a[i]——>a[i-1]+(i-1)>=a[i]+i       （1）
但是，这次要处理非升，而前面的算法讲的是非降，怎么办呢？
方法很简单，只需要把a[i]+i取相反数即可！
于是（1）改为-(a[i]+i)
主体
这题也是求修改数量，但是是分成K个不同的单调部分，怎么办呢？
答案是DP，DP[i][j]相当于在前j个数里，将他们变成i个单调序列的最小修改数量。F[i][j]相当于将第i到第j个数转换为单调的最小修改数量。
状态转移：dp[i][j]=min{dp[i-1][k]+F[k+1][j]}0<=k<j
我们可以惊喜的看到，因为每个i只与i-1有关，所以可以优化成一维，只不过j须要从1到n变为n到1。
关键是求F数组，很难表达出实际意思，直接贴代码：
//堆中元素个数Cnt[i]、这些数的和TCnt[i]、属于这个堆但被从堆中去掉的元素个数Non[i]、这些数的和TNon[i]，La[L]代表从I开始一直到栈的第L个（从栈底开始）的最小修改值
for(int I=1;I<N;I++)
{
    L=1,S[1]=&pool[I];
    make(S[1],A[I]);
    W[1]=A[I],NUM[1]=1,Cnt[1]=1,TCnt[1]=A[I],TNon[1]=0,Non[1]=0,La[1]=0;
    for(int i=I+1;i<=N;i++)
    {
        L++;
        S[L]=&pool[i];
        make(S[L],A[i]);
        W[L]=A[i],NUM[L]=1,Cnt[L]=1,TCnt[L]=A[i],TNon[L]=0,Non[L]=0,La[L]=0;
        while(L>1 && W[L]<W[L-1])
        {
            node *tmp=merge(S[L],S[L-1]);
            Cnt[L-1]+=Cnt[L],TCnt[L-1]+=TCnt[L],TNon[L-1]+=TNon[L],Non[L-1]+=Non[L];
            if((NUM[L]+1)/2+(NUM[L-1]+1)/2>(NUM[L]+NUM[L-1]+1)/2)
            {
                int tmp1=tmp->key;
                tmp=merge(tmp->left,tmp->right);
                Cnt[L-1]--,TCnt[L-1]-=tmp1;
                Non[L-1]++,TNon[L-1]+=tmp1;
            }
            NUM[L-1]=NUM[L]+NUM[L-1];
            S[L-1]=tmp;
            W[L-1]=tmp->key;
            L--;
        }
        F2[I][i]/*或F1[I][i]*/=La[L]=La[L-1]+(W[L]*Cnt[L]-TCnt[L]+TNon[L]-Non[L]*W[L]);
    }
}
楼下贴完整代码。

• 代码 (3208) yc5_yc 2012-07-06 17:40:39