Wuyanru's blog
0%

[BalkanOI2018] Election

发表于 分类于 ，

今天又是降智的一天。

题目链接

题意

给定一个长度为 的字符串 ，由 C 和 T 两种字符构成。

次询问，每一次询问给出 ，要求在字符串 内删除若干字符。

使得对于该子串的任何一个前缀、后缀，都有 C 的数量大于 T 的数量。

求出最小删除字符数。

题解

首先经典的题意转化，将 C 视作 ，T 视作 ，则要求所有前后缀和 。

那么我们删除的只可能是 ，而不可能是 。

首先来想，假如只考虑前缀和 该怎么做呢？

显然，最小个数一定是 ，因为对于每一个位置 ，只有删除至少 个数字，才能使前缀和 。

考虑构造这个删除方案，直接找到第一个前缀和为 的位置，并把他们删掉即可，这个方案显然是合法的。

再来考虑后缀和，我们发现，最优的方案，一定是正着做一遍上面的构造，再反着做一遍上面的构造。

我们在正着的构造中删除数字的时候，一定删除的是能删的"最靠后"的位置，这样可以尽可能地增大更多的后缀和。正着做完之后，我们就把问题转化成了只考虑后缀和的子问题，所以再反着做一遍就好了。

设正着做完后，第 个位置的后缀和是 。

那么我们要求的答案就是 。

考虑 的值是多少，一定有 ，其中 为正着构造时，在 内删除的数字个数。

那么就会有 ，其中 为删除的数字总数， 是在区间 内删除的数字个数，两者做差即为 。

所以 。

则答案为

也就是说，我们需要找到一段前缀与一段后缀，使得他们不相交，且和最小（答案为它们的相反数）。

即答案为区间最大子段和-区间和，线段树维护即可。

时间复杂度为 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
struct node
{
    int lma,rma;
    int c,sum;
    inline node operator + (node b)
    {
        node ans;
        ans.sum=sum+b.sum;
        ans.lma=max(lma,sum+b.lma);
        ans.rma=max(b.rma,b.sum+rma);
        ans.c=max(max(c,b.c),rma+b.lma);
        return ans;
    }
}num[2000001];
char s[500005];
int n,m;
void build(int p,int pl,int pr)
{
    if(pl==pr)
    {
        if(s[pl]=='C') num[p].sum=num[p].lma=num[p].rma=num[p].c=1;
        else num[p].sum=-1;
        return ;
    }
    int mid=(pl+pr)>>1;
    build(p*2,pl,mid);
    build(p*2|1,mid+1,pr);
    num[p]=num[p*2]+num[p*2|1];
}
node get(int p,int pl,int pr,int l,int r)
{
    if(l<=pl&&pr<=r) return num[p];
    int mid=(pl+pr)>>1;
    if(l<=mid)
    {
        if(mid>=r) return get(p*2,pl,mid,l,r);
    }
    if(mid<r)
    {
        if(l>mid) return get(p*2|1,mid+1,pr,l,r);
    }
    return get(p*2,pl,mid,l,r)+get(p*2|1,mid+1,pr,l,r);
}
int main()
{
    n=read();
    scanf("%s",s+1);
    build(1,1,n);
    m=read();
    for(int i=1;i<=m;i++)
    {
        int l=read(),r=read();
        node ans=get(1,1,n,l,r);
        printf("%d\n",ans.c-ans.sum);
    }
    return 0;
}

感谢观看！