abc229g

· · 题解

分享一个 O(n \log^2 n) 的 麻烦的 另一个角度的二分做法。

在某个地方看到这题有数据结构的标签，昨晚发现并不用数据结构，前缀和就可以。所以为什么有数据结构标签呢？

首先还是转换这个问题。将 Y 下标塞进一个数组里，然后减去其在新数组里的下标，得到数组 a，于是问题可以转化为：让 a 里的一些数 +1/-1 若干次，问最多有多少个数能变得相同。

样例1 里的 a 数组就是 0,0,3,4,5。可以发现，a 一定是单调不降的。

可以枚举最终变得相同的数 x。显然最终答案对应的 x 一定是原先有 Y 的位置。

然后二分出能够在 k 次操作下都变成 x 的最远区间 [L,R]。这个怎么二分呢，可以对区间到 x 的最大操作次数 p 进行二分，因为我们发现这个 p 一定在 L 或者 R 的位置取到，方便确定整个区间。

对于一个 p 和最终都变成的数 x，先 lower_bound 出 L,R 的位置，然后用前缀和处理这个区间都变成 x 需要操作的次数。具体来说，就是把 [L,R] 拆成 [L,x],[x,R] 分别计算。

如果需要操作的次数 >k 那么 p 就是不合法的，反之就是合法的。

但是！！ 还有可能碰到这样的情况：a=\{1,2,2,2,2,2,2,2\},k=3。此时你的 [L,R] 是 [1,1]，但显然可以是 [1,4]。这时就要把 L,R 往两边再扩展。因为你不知道 [L,R] 哪一头能再往外扩，所以两边都试一下，设这个能被外扩的数为 w。

具体地说，如果通过二分得到的 [L,R] 已经花费了 d 次操作，那么还剩下 k-d 次外扩的操作。因为外扩的每个数所需操作都是 |a_x-w|，直接用 k-d 去除一下就可以了。

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define endl "\n"
#define int long long
#define pii pair<int,int>
#define mem(a,b) memset(a,(b),sizeof(a))
using namespace std;
const int N=2e5+5;
int n,k,ans,mx;
char s[N];
int a[N],t[N];
int dis(int l,int r,int op){
    if(op==1) return t[r]-t[l-1]-(r-l+1)*a[l];
    return (r-l+1)*a[r]-(t[r]-t[l-1]);
}
bool check(int x,int p){
    int L=lower_bound(a+1,a+n+1,max(0ll,a[x]-p))-a,R=upper_bound(a+1,a+n+1,a[x]+p)-a-1;
    if(dis(L,x,-1)+dis(x,R,1)>k) return 0;
    return 1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>s+1;
    cin>>k;
    int len=strlen(s+1); 
    FOR(i,1,len){
        if(s[i]=='Y') a[++n]=i-n,mx=max(mx,a[n]);
    }
    FOR(i,1,n) t[i]=t[i-1]+a[i];
    FOR(i,1,n){
        int l=0,r=max(a[i],mx-a[i]);
        while(l<r){
            int mid=(l+r+1)>>1;
            if(check(i,mid)) l=mid;
            else r=mid-1;
        }
        int L=lower_bound(a+1,a+n+1,max(0ll,a[i]-r))-a,R=upper_bound(a+1,a+n+1,a[i]+r)-a-1;
        ans=max(ans,R-L+1);
        int qwq=dis(L,i,-1)+dis(i,R,1);
        if(k==qwq) continue;
        int res=0;
        if(L!=1&&L!=0) ans=max(ans,res=max(res,R-L+1+(k-qwq)/abs(a[i]-a[L-1])));
        if(R!=n-1&&R!=n) ans=max(ans,res=max(res,R-L+1+(k-qwq)/abs(a[i]-a[R+1])));
    }
    cout<<ans<<endl;
    return (0-0);
}