codeforces Educational Codeforces Round 65 （补完）-蒲公英云

C News Distribution

并查集水题

D Bicolored RBS

括号匹配问题，如果给出的括号序列nesting depth为n，那么最终可以分成两个nesting depth为n / 2的序列。
在进行匹配的时候，如果当前栈中的左括号大于等于 n / 2，那么剩下的括号就要进行标记，最终标记和不标记的分成两个部分。

E Range Deleting

对一个序列去掉一个区间范围内的数字，使得剩下的序列是一个非降序的序列。
这题是一道较好的思维题。
首先可以预处理出1到\(pref\)，只保留\([1,pref]\)内的数字，序列是非降序的；也可以预处理出\(suf\)到\(x\)，保留\([suf,x]\)内的数字，序列是非降序的。
然后可以发现，如果去掉\([l,r]\)满足条件，那么去掉\([l,r+1],[l,r+2],…,[l,x]\)也一定是满足条件的。
可以枚举\(l\)，枚举的范围是\([1,pref+1]\)，\(pref+1\)是因为\([1,pref]\)的序列都是有序的，所以去掉\(pref+1\)也是有序的；对于每一个\(l\)，要找出满足条件的\(r\)的数量；
因为去掉了\(l\)到某个数字，前面剩下的数字就是\([1,l-1]\)，那么\(r\)满足的条件就是首先要大于等于\(suf\)，大于等于\(l\)，然后还要满足在\([1,l-1]\)当中出现的最大的数字的最后一个下标之前，这个数字没有出现过，换个角度，假设\([1,l-1]\)当中出现的最大的数字的最后一个下标是\(ind\)，那么\(r\)的最小值就是\(max(a[1],….,a[ind])+1\)，于是\(r\)的最小值就由之前的3个条件共同求出，满足条件的\(r\)的个数就分为两种情况：
1.\(l == r\)，那么就有\(x - r + 1\)种；
2.\(l != r\)，那么就有\(x - r + 2\)种，因为\(r\)是可以保留在序列当中的，所以可以去掉的范围是\([r-1,x]\)，也就是说去掉\([l,r-1]\)这个区间也是满足条件的。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 10;
vector<int> G[N];
set<int> s;
int pre[N],sub[N];
int a[N];
bool L[N],R[N];
int main()
{
    int n,x;
    scanf("%d%d",&n,&x);
    for (int i = 1;i <= n;i++) 
    {
        scanf("%d",&a[i]);
        s.insert(a[i]);
    }
    if (x == 1)
    {
        puts("1");
        return 0;
    }
    pre[0] = -inf;
    for (int i = 1;i <= n;i++)
    {
        pre[i] = max(pre[i-1],a[i]);
    }
    sub[n+1] = inf;
    for (int i = n;i >= 1;i--)
    {
        sub[i] = min(sub[i+1],a[i]);
    }
    for (int i = 1;i <= n;i++)
    {
        G[a[i]].push_back(i);
    }
    int pref,suf;
    L[1] = 1;
    for (int i = 2;i <= x;i++)
    {
        if (G[i].empty())
        {
            L[i] = L[i-1];
        }
        else
        {
            int p = G[i][0];
            int x = sub[p];
            if (x < i)
            {
                L[i] = 0;
            }
            else
            {
                L[i] = L[i-1];
            }
        }
    }
    R[x] = 1;
    for (int i = x - 1;i >= 1;i--)
    {
        if (G[i].empty())
        {
            R[i] = R[i+1];
        }
        else
        {
            int sz = G[i].size();
            int p = G[i][sz-1];
            int x = pre[p];
            if (x > i)
            {
                R[i] = 0;
            }
            else
            {
                R[i] = R[i+1];
            }
        }
    }
    for (int i = 1;i <= x;i++)
    {
        if (L[i]) pref = i;
    }
    for (int i = x;i >= 1;i--)
    {
        if (R[i]) suf = i;
    }
    ll ans = 0;
    for (int i = 1;i <= x;i++)
    {
        if (i == 1)
        {
            for (int j = 1;j <= x;j++)
            {
                if (R[j+1])
                {
                    ans += x - j + 1;
                    //printf("%d *\n",x - j + 1);
                    break;
                }
            }
        }
        else
        {
            if (!L[i-1]) break;
            int l = i-1;
            if (l < (*s.begin()) || l > (*--s.end()))
            {
                int tmp = max(l + 1,suf);
                if (tmp == l + 1)
                {
                    ans += x - tmp + 1;
                }
                else
                {
                    ans += x - tmp + 2;
                    //printf("%d *\n",x - tmp + 2);
                }
            }
            else
            {
                if (G[l].empty())
                {
                    int xx = *--s.lower_bound(l);
                    int sz = G[xx].size();
                    int p = G[xx][sz-1];
                    int tmp = max(pre[p] + 1,suf);
                    tmp = max(l + 1,tmp);
                    if (tmp == l + 1)
                    {
                        ans += x - tmp + 1;
                    }
                    else
                    {
                        ans += x - tmp + 2;
                    }
                }
                else
                {
                    int sz = G[l].size();
                    int p = G[l][sz-1];
                    int tmp = max(pre[p] + 1,suf);
                    if (tmp == l + 1)
                    {
                        ans += x - tmp + 1;
                    }
                    else
                    {
                        ans += x - tmp + 2;
                    }
                }
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

F Scalar Queries

题意：

有一个数组\(a\)，里面的数字两两不同，\(f(l,r)\)表示选出下标从\(l\)到\(r\)的数字，然后排序，排序之后的数组为\(b\)，\(\sum_{i = 1}^{r - l + 1}b_i * i\)。
需要求每一个\(f(l,r)\)的和。

思路：

又是一道很好的思维题。
可以转化为求每一个数字对最终答案的贡献。
假设\(low(l,r,a[i])\)表示在区间\([l,r]\)内小于\(a[i]\)的数字，那么\(a[i]\)对于\((l,r)\)的贡献就是\(a[i] * low(l,r,a[i])+1\)。
\(low(l,r,a[i])+1\)就相当于\(a[i]\)在\((l,r)\)内的rank。
这个rank又转化为每一个小于\(a[i]\)的数字出现的次数之和。
首先对于\(a_i\)本身，它自己出现的次数是\(i * (n - i - 1)\)；
然后对于\(a_j < a_i,j < i\)的数字，它的出现次数是\(j * (n - i + 1)\)；
对于\(a_j < a_i,j > i\)的数字，它的出现次数是\(i * (n - j + 1)\)；
如上三个数字相加，假设为\(sum\)，那么\(sum * a_i\)就是\(a_i\)对答案的贡献。
对于小于某个数字的所有数字出现的位置，可以用树状数组求前缀和。大的也同理。
又出现了\(int * int\) 爆\(int\) 的问题！！！

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 5e5 + 10;
const ll mod = 1000000000LL + 7;
ll c[N],d[N];
int n;
int lowbit(int x)
{
    return x&(-x);
}
void addl(int x,int y)
{
    for (int i = x;i <= n;i += lowbit(i)) c[i] += y; 
}
void addr(int x,int y)
{
    for (int i = x;i <= n;i += lowbit(i)) d[i] += y;
}
ll getlsum(int x)
{
    ll ans = 0;
    for (int i = x;i >= 1;i -= lowbit(i)) 
    {
        ans += c[i];
        ans %= mod;
    }
    return ans;
}
ll getrsum(int x)
{
    ll ans = 0;
    for (int i = x;i >= 1;i -= lowbit(i)) 
    {
        ans += d[i];
        ans %= mod;
    }
    return ans;
}
pii a[N];
int main()
{
    scanf("%d",&n);
    for (int i = 1;i <= n;i++)
    {
        scanf("%d",&a[i].first);
        a[i].second = i;
    }
    sort(a+1,a+1+n);
    ll ans = 0;
    for (int i = 1;i <= n;i++)
    {
        ll x = getlsum(a[i].second);
        ll tmp = 0;
        tmp += x * (n-a[i].second+1);
        tmp %= mod;
        ll y = getrsum(n-a[i].second+1);
        tmp += y * a[i].second;
        tmp %= mod;
        tmp += 1LL * a[i].second * (n-a[i].second + 1);
        tmp %= mod;
        ans += tmp * a[i].first;
        ans %= mod;
        addl(a[i].second,a[i].second);
        addr(n-a[i].second + 1,n-a[i].second+1);
    }
    ans += mod;
    printf("%lld\n",ans % mod);
    return 0;
}