题解：CF2121G Gangsta

· · 题解

回归的第一场比赛，因为不会打字了导致最后这题时间不够没写出来

先做出一步转化,将0看作-1,1看作1。统计前缀和sum

f(l,r)=(r - l +1 + abs(sum[r] - sum[l - 1])) / 2

我的方法：

以固定左端点为思维的起点

考虑不断将左端点向右移动（每次统计所有左端点为i的区间的绝对值的和）

想象一个水平面（以上为和大于0的区间，以下为小于0的区间），随着左端点右移，维护：

0.将[i - 1,i - 1]踢出

1.水平面的偏转值

2.水平面以上的区间的个数，水平面以下的区间的个数

3.不断更新abs的和

为了方便维护需要用一个map记录sum[i] = x的区间个数

维护的时候要考虑逻辑先后关系，一定要想清楚！

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

#define int long long
#define FOR(i,a,b) for(int i = a;i <= b;i++)
#define _FOR(i,a,b) for(int i = a;i >= b;i--)

template<typename T> void read(T &x)
{
    x = 0;int f = 1;
    char c = getchar();
    for(;!isdigit(c);c = getchar()) if(c == '-') f = -1;
    for(;isdigit(c);c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

map<int,int> mp;
int T,n,a[N],sum[N],pianyi,ans,now,shang,xia,py,num0,sumlen;//
char s[N];

signed main()
{
    //freopen(".in","r",stdin);n
    //freopen(".out","w",stdout);
    scanf("%lld",&T);
    while(T--)
    {
        mp.clear();
        scanf("%lld",&n);
        scanf("%s",s + 1);
        py = ans = shang = xia = now = sumlen = 0;
        FOR(i,1,n)
        {
            if(s[i] == '0') a[i] = -1;
            else a[i] = 1;
            sum[i] = sum[i - 1] + a[i];
            mp[sum[i]]++;
            ans += ( (i + abs(sum[i]) ) / 2 );
            now += abs(sum[i]); 
            if(sum[i] > 0) {shang++; }
            else if(sum[i] < 0){xia++; } 
            sumlen += i;
            //printf("ans: %d\n",ans);
        }

        FOR(i,1,n - 1)
        {
            //printf("???%d shang:%d xia:%d\n",now,shang,xia);
            sumlen -= (n - i + 1);
            now--;
            if(a[i] > 0) 
            {
                shang--;
                mp[1 + py]--;//!!!
                xia += mp[py];

                py++; 

                //mp[1]--;
                now = now - shang + xia;
                shang -= mp[py];
            }
            else
            {
                xia--;
                mp[-1 + py]--;
                shang += mp[py];

                py--;

                //mp[-1]--;
                now = now + shang - xia;
                xia -= mp[py];
            }
            ans += (sumlen + now) / 2;
            //printf("!!!%d %d\n",ans,now);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
/*
1
3 4
1 2 3 2
3 2 1 3
2 1 3 2
*/

官方做法

从整体考虑

考虑 abs(sum[r] - sum[l - 1])

将所有sum由小到大排序，每个sum在与比它小的sum搞时贡献为正的，在与比它大的sum搞时贡献为负的

因此对于排序后的sum[i],它对答案的贡献为i - (n - i) * sum[i]

本题小结

本题是一个整体求和问题，肯定要考虑怎么适当的进行整体打包来提升效率，我通过打包相同左端点的区间来做，这条路是行的通的但这个做法并不契合绝对值问题，因此处理起来比较麻烦，比赛的时候也没有调完。

另外一种解法以绝对值左右无关为出发点，通过绝对值进行拆点解决问题，比较巧妙