WC2019 全国模拟赛第一场 T1 题解

由于只会T1，没法写游记，只好来写题解了…

题目大意

给你一个数列，每次可以任取两个不相交的区间，取一次的贡献是这两个区间里所有数的最小值，求所有取法的贡献和，对 $10^9+7$ 取模。

数列长度 $2\times 10^5$ ，值域 $1$ ~ $10^9$ 。

$O(n^4)$ 做法

预处理区间最小值，枚举选的两个区间。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int M=1000000007;

int n,a[60][60],ans;

int main()
{
    int i,j,k,l;

    cin>>n;

    for (i=1;i<=n;++i)
    {
        cin>>a[i][i];
    }

    for (i=1;i<n;++i)
    {
        for (j=i+1;j<=n;++j)
        {
            a[i][j]=min(a[i][j-1],a[j][j]);
        }
    }

    for (i=1;i<n;++i)
    {
        for (j=i;j<n;++j)
        {
            for (k=j+1;k<=n;++k)
            {
                for (l=k;l<=n;++l)
                {
                    ans=(ans+min(a[i][j],a[k][l]))%M;
                }
            }
        }
    }

    cout<<ans;

    return 0;
}

$O(nlogn)$ 做法

warning：接下来的文章里“的”字嵌套情况非常严重，文字叙述比较繁杂，看不懂十分正常，建议看懂一小部分然后自己推。

考虑每个元素作为贡献的区间是哪些，为了把每个区间分给唯一的元素，规定一个区间的贡献是最小值里最靠左的（ e.g. 4 3 2 4 2 2 的贡献是 $3$ 号元素，即最左边的 $2$ ）。所以，可以利用栈在 $O(n)$ 的时间内预处理出每个元素作为贡献的区间的左端点和右端点的范围：

for (i=1;i<=n;++i)
{
    while (top&&a[sta[top]].w>a[i].w)
    {
        a[sta[top--]].r=i-1;
    }
    sta[++top]=i;
}

while (top)
{
    a[sta[top--]].r=n;
}

for (i=n;i>=1;--i)
{
    while (top&&a[sta[top]].w>=a[i].w)
    {
        a[sta[top--]].l=i+1;
    }
    sta[++top]=i;
}

while (top)
{
    a[sta[top--]].l=1;
}

每个元素作为贡献的区间就是 $[x,y] (l_i\le x\le i\le y\le r_i)$，每个元素作为贡献的区间数就是 $t_i=(i-l_i+1)\times(r_i-i+1)$ 。

然后，将元素按值从大到小排序，就能计算出区间数的后缀和 $suf[i]$，但一个元素的总贡献并不是 $t_i\times suf[i+1]$，因为这些区间可能与当前元素作为贡献的区间相交。

注意到，要想和当前元素作为贡献的区间相交，必须 $[x,y] (l_i\le x\le y\le r_i)$ ，而这样的区间除了当前元素作为贡献的区间，贡献都排在当前元素之后（值比当前元素大或值相等但位置靠后），所以这样的区间除了当前元素作为贡献的区间，都是我们要找的与当前元素作为贡献的区间相交的贡献更靠后的区间。

注：下面这段话中“相交的区间对”指（与当前元素作为贡献的区间相交的贡献更靠后的区间，当前元素作为贡献的区间）这样的一对区间；“相交的区间”指与当前元素作为贡献的区间相交的贡献更靠后的区间。

接下来就要计算相交的区间有多少对。首先，相交的区间不可能跨过当前元素，否则就是当前元素作为贡献的区间；所以，相交的区间要么是 $[x,y] (l_i\le x\le y<i)$ ，要么是 $[x,y] (i<x\le y\le r_i)$。先计算 $[x,y] (l_i\le x\le y<i)$ 与当前元素作为贡献的区间相交的对数，先考虑 $y$ 固定时，个数为 $(r_i-i+1)\times(y-l_i+1)^2$ ，其中：$y-l_i+1$ 既是相交的区间左端点的个数，也是与相交的区间相交的当前元素作为贡献的区间的左端点的个数；$r_i-i+1$ 是与相交的区间相交的当前元素作为贡献的区间的右端点的个数。所以，总数是 $(r_i-i+1)\times\sum\limits_{y=l_i}^{i-1}(y-l_i+1)^2$ ，乘号右边是自然数平方和，可以用公式计算，所以就是 $(r_i-i+1)\times\frac{(i-l_i)\times(i-l_i+1)\times(2i-2l_i+1)}6$ 。$[x,y] (i<x\le y\le r_i)$ 同理，总数为 $(i-l_i+1)\times\frac{(r_i-i)\times(r_i-i+1)\times(2r_i-2i+1)}6$ 。

所以，把相交的总对数减掉就可以了。

参考代码：

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;

int read()
{
    int out=0;
    char c;
    while (!isdigit(c=getchar()));
    for (;isdigit(c);c=getchar())
    {
        out=out*10+c-'0';
    }
    return out;
}

const int N=200010;
const int M=1000000007;
const int SIX=166666668; //6模1e9+7的逆元

struct Node
{
    long long id,w,l,r,t;
    bool operator<(const Node& b) const
    {
        return w<b.w;
    }
} a[N];

long long n,suf[N],sta[N],top,ans;

int main()
{
    int i;

    n=read();

    for (i=1;i<=n;++i)
    {
        a[i].w=read();
        a[i].id=i;
    }

    for (i=1;i<=n;++i)
    {
        while (top&&a[sta[top]].w>a[i].w)
        {
            a[sta[top--]].r=i-1;
        }
        sta[++top]=i;
    }

    while (top)
    {
        a[sta[top--]].r=n;
    }

    for (i=n;i>=1;--i)
    {
        while (top&&a[sta[top]].w>=a[i].w)
        {
            a[sta[top--]].l=i+1;
        }
        sta[++top]=i;
    }

    while (top)
    {
        a[sta[top--]].l=1;
    }

    for (i=1;i<=n;++i)
    {
        a[i].t=(i-a[i].l+1)*(a[i].r-i+1)%M;
    }

    sort(a+1,a+n+1);

    for (i=n;i>=1;--i)
    {
        suf[i]=(suf[i+1]+a[i].t)%M;
    }

    for (i=1;i<=n;++i)
    {
        ans=(ans+(a[i].w*suf[i+1]%M)*a[i].t)%M;
        ans=(ans-(a[i].id-a[i].l)*(a[i].id-a[i].l+1)%M*(2*a[i].id-2*a[i].l+1)%M*SIX%M*(a[i].r-a[i].id+1)%M*a[i].w%M+M)%M; //重复区间在左
        ans=(ans-(a[i].r-a[i].id)*(a[i].r-a[i].id+1)%M*(2*a[i].r-2*a[i].id+1)%M*SIX%M*(a[i].id-a[i].l+1)%M*a[i].w%M+M)%M; //重复区间在右
    }

    cout<<ans;

    return 0;
}

文章目录

题目大意

$O(n^4)$ 做法

$O(nlogn)$ 做法