题解：P12391 「RiOI-6」帝国少女

· · 题解

P12391 「RiOI-6」帝国少女 题解

思路产生

首先显然 m>2 和 m=2 是两种情况需要分讨。

我们先考虑 m>2 的情况：

有一个贪心策略就是对于任意一段相同的数的连续段，都把在这个连续段中的偶数位的数变成一个不同于其左右相邻的数。

比如 2 1 1 1 1 1 1 2 就要变成 2 1 2 1 2 1 3 2。

这个贪心策略的正确性是显然的，因为对于任意一对相邻且相同的数，都要选择一个选择其中一个，给成另一个数字，因为我们的可以选择换成的数字至少有 3 个，一定可以做到改完后和左右相邻的数各不相同。我们只需要考虑怎么做可以让相邻的数对尽可能少。对于奇数长度的段我们都改变偶数位的数一定更优的，而对于偶数长度的段我们改变偶数位的数一定是不劣的。

有了贪心策略，我们就要想怎么才能在时间复杂度限制内求出答案。

我们考虑每一个数对会对多少个子段产生贡献。我们求出来每一个子段的左端点的有多少种取法，右端点有多少种取法，这样根据乘法原理，我们就能求出来能让点对做出贡献的子段数。

对于右端点，只要大于等于点对的右端点是都能取的。

对于左端点，在小于点对左端点的同时，还要满足让点对的右端点成为一段连续相同的数的连续段的偶数位。

这些都是可求的，根据连续段长度奇偶分讨一下就好了。

我们接下来考虑 m=2 的情况

比如按照原来的贪心策略：`2 1 1 1 1 1 1 2` 就要变成 `2 1 2 1 2 1 2 2` 然后你就发现假了。 这该怎么办？ 考虑把所有的 $2$ 都替换成 $0$，这样对于一个子区间，我们都要转换成 $0101010 \dots$ 或者 $1010101\dots

感觉 01 交替有点抽象。我们直接把原序列上的所有偶数位的数全部都 01 反转，这样我们就只需要求把一段区间变成全 1 或者全 0 就好了。

这样我们又有了一个贪心策略：对于一个子区间，1 的个数多就把区间所有 0 变成 1， 0 的个数多就把区间所有 1 变成 0。

那么我们就把题转化成了求：

\sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n}\operatorname{g}(i,j)

这里 \operatorname{g}(i,j) 表示对于从 i 到 j 的子区间，0 的个数和 1 的个数较小值。

我们前缀和分别维护出区间 0 和 1 的个数，然后枚举区间，这样 O(n^2) 的做法就做好了，拿到 60 分。

考虑优化。设子区间有 a 个 0 和 b 个 1，那么有：

\min(a,b)=\dfrac{a+b-|a-b|}2

而我们要求的所有子区间最小值之和可转化为：

\dfrac{(\sum (a+b) - \sum |a+b|)}2

其中 \sum (a+b) 代表的是所有子区间长度之和，\sum (a+b) 代表的是所有子区间 0 和 1 数量差的绝对值之和。

对于前者我们发现长度为 1 的区间有 n 个，长度为 2 的区间有 n-1 个，长度为 3 的区间有 n-2 个，以此类推……

那么前者其实就是：

=\sum\limits_{i=1}^nn\times i-\sum\limits_{i=1}^ni^2+\sum\limits_{i=1}^n i\\ =\frac{n(n+1)^2}2-\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\\ =\frac{n(n+1)(n+2)}{2}

那么下面就是求后者了。

我们再进行进一步的转化：

将 0 视作 -1，则子区间的 1 和 0 的个数差就等于该区间的和。我们再做一下前缀和。设前缀和数组为 s 问题就又转换成了对于所有的 i<j 的 |s[j]-s[i]| 的和。

我们考虑拆绝对值。

对于每个s[j]，贡献值为：

\sum_{i<j}|s[j]-s[i]|

拆分为两部分：

我们可以开两个权值树状数组分别记录次数和总和，由于前缀和数组可能有负数，所以不要忘了离散化一下。

然后在枚举 j 的同时，快速求出所有上文所提到的较小元素的个数，较大元素个数，较小元素的和，较大元素的和。然后每求出一个 j 的贡献再把 j 加到权值树状数组里面。

最后根据公式求一下就好了，最后时间复杂度是O(n\log n)。

附上代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N],s[N],b[N];
int lowbit(int x){
    return x&(-x);
}
struct Tree{
    int n;
    vector<int> tr;
    Tree(int n):n(n),tr(n+2){}
    void update(int x,int c){
        for (;x<=n;x+=lowbit(x)) tr[x]+=c;
    }
    int query(int x){
        int res=0;
        for (;x;x-=lowbit(x)) res+=tr[x];
        return res;
    }
};
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if(m>2){
        int ans=0;
        int nw=0,len=0;
        for(int i=1;i<n;i++){
            if(a[i]==nw){
                len++;
            }else{
                nw=a[i];
                len=1;
            }
            if(a[i]==a[i+1]){
                if(len%2==0){
                    ans+=(len/2)*(n-i);
                }else{
                    ans+=(len/2+(i-len)+1)*(n-i);
                }
            }           
        }
        cout<<ans<<"\n";
    }else{
        for(int i=1;i<=n;i++){
            if(a[i]==2)a[i]=0;
        }
        for(int i=2;i<=n;i+=2){
            a[i]^=1;
        }
        for (int i=1;i<=n;i++) a[i]=(a[i]==0?1:-1);
        for(int i=1;i<=n;i++){
            s[i]=a[i]+s[i-1];
            b[i]=s[i];
        }
        sort(b+1,b+n+1);
        int tot=unique(b+1,b+n+1)-b-1;
        Tree cnt(tot),sum(tot);
        int ans=0;
        for (int i=0;i<=n;i++){
            int x=s[i];
            int k=lower_bound(b+1,b+tot+1,x)-b;
            int cl=cnt.query(k-1),sl=sum.query(k-1);
            int ct=cnt.query(tot),st=sum.query(tot);
            int cs=ct-cl,ss=st-sl;
            ans+=x*cl-sl+ss-x*cs;
            cnt.update(k,1);
            sum.update(k,x);
        }
        cout<<(n*(n+1)*(n+2)/6-ans)/2;
    }
}