题解 CF212D 【Cutting a Fence】

2018-07-05 19:32:44


真的,已经不想说什么了,这道题出的真的太好了……orzorzorz

  • 对于每个数a[x]在它左边找一个离它最近的小于它的数,在它右边找一个离它最近 的小于等于它的数

    记所找到左边数的位置为 l ,所找到右边数的位置为 r

    那么在[ l +1, r -1]中的所有子区间,只要包含a[x],最小值都是a[x]

  • 设a[x]到a[ l +1]长度为L,a[x]到a[ r -1]长度为R

    当第二问的区间长度为K时(K是个变量),把所有长度为K的区间最小值的和设为Sum

    我们开始分类讨论

    设L<=R

    ① 当1<=K<=L,会有K个长度为K的区间的最小值是a[x],Sum=Sum+K*a[x]

    ② 当L+1<=K<=R 会有L个长度为K的区间的最小值是a[x],Sum=Sum+L*a[x]

    ③ 当R+1<=K<=L+R-1 会有L+R-K个长度为K的区间的最小值a[x],

    Sum=Sum+a[x] (L+R-K)=Sum+a[x] (L+R)-K*a[x]

    对于每一个a[x],我们需要把它对所有区间长度询问的答案贡献求出 也就是对于每个Len(1<=len<=L+R-1),我们都要根据上面分类讨论得出的结论, 算出对Sum的贡献。观察关于Sum的式子可以发现,只有K*a[x]才是一个会变化的值, 其余都是定值。

    我们不妨设C1[K]是区间长度为K时,所有需要乘K的a[x]的和,C2[K]是区间长度为K时,所有定值的和。

    设ans[K]是区间长度为K的答案,ans[K]=(K*C1[K]+C2[K])/(n-K+1)

    我们需要预处理出所有区间长度的答案,然后O(1)解出每一个询问。

    显然对于每一个a[x] (1<=x<=n),都会有一系列的K满足前面的三种讨论情况, 而每一个K,都会有一个C1[K],C2[K],会发现,当连续的几个K都处于同一种情况的时候,所对应的C1[],C2[]增加的值是相等的,这就可以看作是区间加,可以用差分来做。

    For Example

    2 5 5 5 3 5 5 5 5 5 5 2

    a[6]=3, L=4, R=7

    当K取[1,4]时,对于a[6]会有4个区间满足最小值是a[6]的条件

    那么

    C1[1]=C1[1]+a[6],

    C1[2]=C1[2]+a[6],

    C1[3]=C1[3]+a[6],

    C1[4]=C1[4]+a[6]

    ——显然一个区间加

    当K取[5,7]时,对于a[6]会有5个区间满足最小值是a[6]的条件

    那么

    C2[5]=C2[5]+4*a[6]

    C2[6]=C2[6]+4*a[6]

    C2[7]=C2[7]+4*a[6]

    ——显然一个区间加

    当K取[8,10]时,对于a[6]会有11-K个区间满足最小值是a[6]的条件

    那么

    C1[8]=C1[8]+11*a[6]

    C1[9]=C1[9]+11*a[6]

    C1[10]=C1[10]+11*a[6]

    ——显然一个区间加

    C2[8]=C2[8]-a[6]

    C2[9]=C2[9]-a[6]

    C2[10]=C2[10]-a[6]

    ——显然一个区间加

    至于为什么对于每个数a[x]一个是找离它最近的小于它的数,另一个是找右边离它最近的小于等于它的数?

    同一个区间内最小值有多个的话,也只需要算一次,比如样例二的这种数据是会被多次计算的,[1,2]这个区间,a[1]的时候算一次,a[2]的时候算一次,所以为什么要这么做,你可以感性的理解为去重。

    OK,OK,其余就看代码吧!

    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    long long n,m,R[1000100],a[1000100],k,x,L[1001000],y,C1,C2;
    long long c1[1001000],c2[1001000];
    double ans[1001000];
    inline long long read()
    {
    long long cnt=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();}
    return cnt*f;
    }
    int main()
    {
    n=read();
    for (int i=1;i<=n;i++)
    a[i]=read();
    a[n+1]=-((long long)1<<60);
    a[0]=-((long long)1<<60);
    for (int i=n;i;i--)
    {
    if (a[i+1]<=a[i]) R[i]=i+1;
    else
    for (int j=R[i+1];j<=n+1;j=R[j])
     if (a[j]<=a[i]) {R[i]=j;break;}
    }
    for (int i=1;i<=n;i++)
    {
    if (a[i-1]<a[i]) L[i]=i-1;
    else
    for (int j=L[i-1];j>=0;j=L[j])
     if (a[j]<a[i]) {L[i]=j;break;}
    }
    for (int i=1;i<=n;i++)
    {
    L[i]=i-L[i];
    R[i]=R[i]-i;
    }
    for (int i=1;i<=n;i++)
    {
     x=L[i];y=R[i];
     if (x>y) swap(x,y);
     c1[1]+=a[i];c1[x+1]-=a[i];
     c2[x+1]+=a[i]*x;c2[y+1]-=a[i]*x;
     c2[y+1]+=a[i]*(x+y);c2[x+y]-=a[i]*(x+y);
     c1[y+1]-=a[i];c1[x+y]+=a[i];
    }
    for (int i=1;i<=n;i++)
    {
    C1+=c1[i];
    C2+=c2[i];
    ans[i]=((C1*i+C2)*1.0)/((n-i+1)*1.0);
    }
    m=read();
    for (int i=1;i<=m;i++)
    {
    k=read();
    printf("%.9lf\n",ans[k]);
    }   
    return 0;
    }

    LuckyCloud