专栏文章

题解：P4786 [BalkanOI 2018] Election

SSunburstFan
P4786题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miomf84u
此快照首次捕获于
2025/12/02 21:35
3 个月前
此快照最后确认于
2025/12/02 21:35
3 个月前
查看原文

P4786 [BalkanOI 2018] Election

题目大意

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

解题思路

首先我们需要转化题意，对于“让 T 和 C 个数相等”这类问题，我们联想到构造一个新的序列 aa，ai=(si=S⁡)−(si=T⁡)a_i = (s_i = \operatorname{S})-(s_i = \operatorname{T})。
此时问题就转化为了：求至少给多少个数加 11 使得序列 aa 的前缀和满足 min⁡(prei)≥0\min(pre_i) \geq 0 且其后缀和满足 min⁡(sufi)≥0\min(suf_i) \geq 0。
这个问题很容易用贪心解决，先从前往后遍历 aia_i， 再从后往前遍历，只要遇到 prei≤0pre_i \le 0 或 sufi≤0suf_i \le 0 就让其变成 00。
于是就获得了一个 O(Q×N)O(Q\times N) 的做法，考虑继续优化。
再进行贪心时不难发现，对于每次询问，其答案就等于 min⁡i=lrprei+min⁡j=lrsufj′\min _{i=l}^{r} pre_i + \min _{j=l}^{r} suf'_j。
注意这里的 sufj′≠sufjsuf'_j \neq suf_j，因为在第一次从前往后遍历的时候，aja_j 和 sufjsuf_j 都已经被改变。
这里可以用到类似于容斥的思想，我们发现：
ans=min⁡i=lrprei+min⁡i=lrsufi′ans = \min _{i=l}^{r} pre_i + \min _{i=l}^{r} suf'_i
ans=min⁡i=lrprei+min⁡j=lrsufj−Δsufjans = \min _{i=l}^{r} pre_i + \min _{j=l}^{r} suf_j - \Delta suf_j
ans=min⁡i=lrprei+min⁡j=lrsufj+min⁡k=jiprek−min⁡i=lrpreians = \min _{i=l}^{r} pre_i + \min _{j=l}^{r} suf_j + \min _{k=j}^{i} pre_k - \min _{i=l}^{r} pre_i
ans=min⁡j=lrsufj+min⁡k=ljprekans = \min _{j=l}^{r} suf_j + \min _{k=l}^{j} pre_k
要求的就是最小后缀和加上最小后缀和之前的最小前缀和。
这句话看上去十分拗口，但是稍微理解一下就发现这就是一个序列中不重合的最小前后缀的和，等于序列总和减去最大子段和。
然后用自己喜欢的数据结构维护即可。

代码

这里给出使用线段树维护区间和、最大子段和的代码。
最大子段和具体实现的方法是：对于每个节点，维护最大前缀、最大后缀、总和、最大字段和，然后进行合并。
子节点合并的代码有一点细节。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...