题解：P4786 [BalkanOI 2018] Election

SunburstFan · 2025-07-30 18:09:14 · 题解

P4786 [BalkanOI 2018] Election

题目大意

有一个长度为 N 的字符串，由 C 和 T 组成，有 Q 次询问，每次询问给出 [l,r]，问该区间内需删除至少多少个 T 使得 T 和 C 的个数相等。

解题思路

首先我们需要转化题意，对于“让 T 和 C 个数相等”这类问题，我们联想到构造一个新的序列 a，a_i = (s_i = \operatorname{S})-(s_i = \operatorname{T})。

此时问题就转化为了：求至少给多少个数加 1 使得序列 a 的前缀和满足 \min(pre_i) \geq 0 且其后缀和满足 \min(suf_i) \geq 0。

这个问题很容易用贪心解决，先从前往后遍历 a_i， 再从后往前遍历，只要遇到 pre_i \le 0 或 suf_i \le 0 就让其变成 0。

于是就获得了一个 O(Q\times N) 的做法，考虑继续优化。

再进行贪心时不难发现，对于每次询问，其答案就等于 \min _{i=l}^{r} pre_i + \min _{j=l}^{r} suf'_j。

注意这里的 suf'_j \neq suf_j，因为在第一次从前往后遍历的时候，a_j 和 suf_j 都已经被改变。

这里可以用到类似于容斥的思想，我们发现：

要求的就是最小后缀和加上最小后缀和之前的最小前缀和。

这句话看上去十分拗口，但是稍微理解一下就发现这就是一个序列中不重合的最小前后缀的和，等于序列总和减去最大子段和。

然后用自己喜欢的数据结构维护即可。

代码

这里给出使用线段树维护区间和、最大子段和的代码。

最大子段和具体实现的方法是：对于每个节点，维护最大前缀、最大后缀、总和、最大字段和，然后进行合并。

子节点合并的代码有一点细节。

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

const int N=5e5+5;
int n,q,a[N];

namespace SGT{
    const int N=5e5+5;
    const int INF=INT_MAX;
    int sum[N<<2];
    int mxn[N<<2],pre[N<<2],suf[N<<2];
    // mxn:最大字段和, pre:最大前缀和, suf:最大后缀和

    #define ls rt<<1
    #define rs rt<<1|1
    #define lson ls,l,md
    #define rson rs,md+1,r

    void push_up(int rt){
        sum[rt]=sum[ls]+sum[rs];
        pre[rt]=max(pre[ls],sum[ls]+pre[rs]);
        suf[rt]=max(suf[rs],sum[rs]+suf[ls]);
        mxn[rt]=max(mxn[rt],max(pre[rt],suf[rt]));
        mxn[rt]=max(mxn[rt],max(mxn[ls],mxn[rs]));
        mxn[rt]=max(mxn[rt],suf[ls]+pre[rs]);
        return;
    }
    void build(int rt,int l,int r){
        //sum[rt]=pre[rt]=suf[rt]=-INF;
        //mxn[rt]=0;
        if(l==r){
            sum[rt]=mxn[rt]=pre[rt]=suf[rt]=a[l];
            if(a[l]<0){
                mxn[rt]=0;
            }
            return;
        }
        int md=(l+r)>>1;
        build(lson); build(rson);
        push_up(rt);
        return;
    }
    // 0: sum 1: mxn 2: pre 3: suf
    array<int,4> qry(int rt,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            return {sum[rt],mxn[rt],pre[rt],suf[rt]};
        }
        int md=(l+r)>>1;
        array<int,4> res={0,0,0,0};
        if(L<=md&&R>md){
            array<int,4> left=qry(lson,L,R);
            array<int,4> right=qry(rson,L,R);
            res[0]=left[0]+right[0];
            res[2]=max(left[2],left[0]+right[2]);
            res[3]=max(right[3],right[0]+left[3]);
            res[1]=max({left[1],right[1],left[3]+right[2]});
            return res;
        }
        else if(L<=md){
            return qry(lson,L,R);
        }
        else if(R>md){
            return qry(rson,L,R);
        }

    }
}

namespace sunburstfan{
    using namespace SGT;
    const int N=1e6+5;

    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++){
            char c;
            cin>>c;
            a[i]=(c=='C')? 1:-1;
        }
        build(1,1,n);

        cin>>q;
        while(q--){
            int l,r;
            cin>>l>>r;
            auto res=qry(1,1,n,l,r);
            // cout<<qrymxn(1,1,n,l,r)<<" "<<qrysum(1,1,n,l,r)<<"\n";
            int ans=res[1]-res[0];
            cout<<ans<<"\n";
        }
    }
}
using namespace sunburstfan;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int T=1;
    while(T--){
        solve();
    }

    return 0;
}