bzoj 3043: IncDec Sequence 模拟

3043: IncDec Sequence

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 248 Solved: 139
[Submit][Status]

Description

给定一个长度为n的数列{a1,a2...an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。
问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。

Input

第一行一个正整数n
接下来n行,每行一个整数,第i+1行的整数表示ai。
。

Output

第一行输出最少操作次数
第二行输出最终能得到多少种结果

Sample Input

4
1
1
2
2

Sample Output

1
2

HINT

对于100%的数据，n=100000，0<=ai<2147483648

　　正解传送门：http://blog.csdn.net/willinglive/article/details/38419573

　　我看到这道题时并没有想到正解，但是很容易yy出来修改策略，每次填满最低的那一段区间，像涨水一样一直涨到顶端，离散处理将低于x的所有值提升到x的增加次数，然后倒着在做一遍，如果暴力做的话肯定会TLE，我们观察每次增加的区间数量即为低于x的区间联通块数量，这不是涨水求联通数的裸题？。。。。

　　最后，因为我先离散化了所有点，所以如果我想回答询问2的话，需要回答离散之前的位置个数，这一点很容易wa。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 110000

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3fLL

typedef long long qword;

int a[MAXN];

pair<int,int> b[MAXN];

int c[MAXN];

int n,m;

qword v1[MAXN],v2[MAXN];

int uf[MAXN];

int get_fa(int now)

{

        return uf[now]==now ? now : uf[now]=get_fa(uf[now]);

}

int comb(int x,int y)

{

        x=get_fa(x);

        y=get_fa(y);

        if (x==y)return false;

        uf[x]=y;

        return true;

}

int main()

{

        freopen("input.txt","r",stdin);

        scanf("%d",&n);

        int i,j,k;

        for (i=;i<n;i++)

        {

                scanf("%d",a+i);

                b[i].first=a[i];

                b[i].second=i;

                c[i]=a[i];

        }

        sort(c,c+n);

        m=unique(c,c+n)-c;

        sort(b,&b[n]);

        int nowc=;

        qword tot=;

        int x,y;

        for (i=;i<n;i++)uf[i]=i;

        for (i=;i<n;i++)

        {

                x=b[i].second;

                tot++;

                if (x && a[x-]<=a[x])

                        tot-=comb(x-,x);

                if (x<n- && a[x+]<a[x])

                        tot-=comb(x+,x);

                if (i!=n- && b[i+].first!=b[i].first)

                {

                        v1[nowc+]=v1[nowc]+tot*(c[nowc+]-c[nowc]);

                        nowc++;

                }

        }

        nowc=m-;

        tot=;

        for (i=;i<n;i++)uf[i]=i;

        for (i=n-;i>=;i--)

        {

                x=b[i].second;

                tot++;

                if (x<n- && a[x+]>=a[x])

                        tot-=comb(x+,x);

                if (x && a[x-]>a[x])

                        tot-=comb(x-,x);

                if (i && b[i-].first!=b[i].first)

                {

                        v2[nowc-]=v2[nowc]+tot*(c[nowc]-c[nowc-]);

                        nowc--;

                }

        }

        qword ans=INFL;

        int mina=INF,maxa=-INF;

        for (i=;i<m;i++)

        {

                if (v1[i]+v2[i]<ans)

                {

                        ans=v1[i]+v2[i];

                        mina=INF,maxa=-INF;

                }

                if (v1[i]+v2[i]==ans)

                        mina=min(mina,c[i]),maxa=c[i];

        }

        printf("%lld\n%d\n",ans,maxa-mina+);

}

巴特西