P3564 [POI2014]BAR-Salad Bar（树状数组）

题意：

给定长度为n的字符串，每一位只会是p或j。
求一个最长子串，使得不管是从左往右还是从右往左取，都保证每时每刻已取出的p的个数不小于j的个数。
输出最长子串的长度

数据范围：n<=1e6

解法：

将p视为1，j视为-1，那么问题就变为求一个最长子串，满足这个子串的前缀和与后缀和都是>=0的

容易想到求出以每个位置为起点能向左和向右扩展的最大位置L[]和R[]，求法：
计算前缀和，对于第i个位置，设其左边第一个大于sum[i]的位置pos那么L[i]=pos+1
怎么找左边第一个满足条件的位置呢？可以用last[k]记录上一次k出现的位置，
然后利用last[]找到左边第一个大于sum[i]的位置，假如当前sum[i]=S,那么L[i]=last[S+1]+1。
计算R[]则利用后缀和
注意：因为sum[]会出现负数，所以要么last用map，要么给last设置偏移量。实测map会超时，我的代码把偏移量设为了n。（也许unordered_map不会超时，没试过）

如果串[x,y]是合法的，那么显然L[y]<=x，R[x]>=y，我们要的答案就是满足这个条件的最大的y-x+1
发现条件只有二维，那么可以通过枚举的方法消除一维的限制。
发现当x增加时，满足L[y]<=x的y仍然满足L[y]<=x+1，是单调的
因此对每个位置按L[]从小到大排序，然后从小到达枚举x，将满足L[y]<=x的所有y加入树状数组（维护前缀max）
然后查询小于等于R[x]的y的最大值y1，用y1-x+1更新答案。枚举完所有x后即可计算出答案。
注意：x和y位置上一定是字母p（区间端点一定是p，即以p开始）

code：

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int maxm=2e6+5;
struct BIT{
    int c[maxm];
    int lowbit(int i){
        return i&-i;
    }
    void add(int i,int t){
        while(i<maxm)c[i]=max(c[i],t),i+=lowbit(i);
    }
    int ask(int i){
        int ans=0;
        while(i)ans=max(ans,c[i]),i-=lowbit(i);
        return ans;
    }
}T;
struct Node{
    int y,ly;
    friend bool operator<(Node a,Node b){
        return a.ly<b.ly;
    }
}e[maxm];
char s[maxm];
int a[maxm];
int sum[maxm];
int last[maxm];
int L[maxm],R[maxm];
int n;
signed main(){
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='p')a[i]=1;
        else a[i]=-1;
    }
    //计算L[],last[]偏移量为n
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
        if(last[sum[i]+1+n])L[i]=last[sum[i]+1+n]+1;
        else L[i]=1;
        last[sum[i]+n]=i;
    }
    //计算R[]
    for(int i=0;i<=n*2;i++)last[i]=0;
    for(int i=n;i>=1;i--){
        sum[i]=sum[i+1]+a[i];
        if(last[sum[i]+1+n])R[i]=last[sum[i]+1+n]-1;
        else R[i]=n;
        last[sum[i]+n]=i;
    }
    //按L[]排序
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]==1){//开头一定要是p
            e[++cnt]={i,L[i]};
        }
    }
    sort(e+1,e+1+cnt);
    //
    int k=1;
    int ans=0;
    for(int x=1;x<=n;x++){
        while(k<=cnt&&e[k].ly<=x){
            T.add(e[k].y,e[k].y);
            k++;
        }
        if(a[x]==1){
            ans=max(ans,T.ask(R[x])-x+1);
        }
    }
    printf("%d\n",ans);
    return 0;
}

---