codeforces Educational Codeforces Round 65 （补完）

向右看齐 2023-10-11 10:11 30阅读 0赞

## 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;
    }

转载于:https://www.cnblogs.com/kickit/p/10897606.html