题解：P12765 [POI 2018 R3] 三座塔 2 Three towers 2

· · 题解

题解没满，水一发。

首先发现优化查询比较困难，考虑优化查询范围，这里有一个结论：最终答案一定要么左端点在最左的三个之一，要么右端点在最右的三个之一。

怎么证明呢？给出一个证明方法：

当不合法是三个字符出现次数全部相等时，向外扩展一个一定会形成一个更长的且合法的串。

当有两个字符出现次数相等时，若待扩展的字符是这两个之一，扩展后一定更长且合法。现在考虑带扩展的字符是第三种的情况，分两种情况讨论：

第三个字符的出现次数比这两种出现次数少 1。那么扩展后就转化为了三个字符出现次数全部相等的情况，一定可以再次扩展。 第三个字符出现次数比这两种出现次数少不止 1。那么这个区间可能无解，排除。

综上，结论是对的。

前缀和一下就是线性的了，我写了个粗劣的树状数组。

:::info[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,n;
int tree[1000001][4],ans;
int law(int a){
    return a&(-a);
}
int add(int u,int s,int k){
    while(u<=n){
        tree[u][k]+=s;
        u+=law(u);
    }
    return 0;
}
int qu(int u,int k){
    int s=0;
    while(u>0){
        s+=tree[u][k];
        u-=law(u);
    }
    return s;
}
signed main(){
    cin>>n;
    char c;
    for(int i=1;i<=n;i++){
        cin>>c;
        if(c=='B') add(i,1,0);
        if(c=='C') add(i,1,1);
        if(c=='S') add(i,1,2);
    }
    for(int i=1;i<=3;i++){
        for(int j=i;j<=n;j++){
            if(j>=i){
            int s[4];
            for(int k=0;k<=2;k++) s[k]=qu(j,k)-qu(i-1,k);
            sort(s,s+3);
            if(s[0]!=s[1]&&s[1]!=s[2]&&s[2]!=s[0]) ans=max(ans,j-i+1);    
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=n-2;j<=n;j++){
            if(j>=i){
            int s[4];
            for(int k=0;k<=2;k++) s[k]=qu(j,k)-qu(i-1,k);
            sort(s,s+3);
            if(s[0]!=s[1]&&s[1]!=s[2]&&s[2]!=s[0]) ans=max(ans,j-i+1);    
            }
        }
    }
    if(ans==0){
       cout<<"NIE";
        return 0;
    }
    cout<<ans;
    return 0;
}

:::