3521: [Poi2014]Salad Bar
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 226 Solved: 104
[Submit][Status][Discuss]
Description
有一个长度为n的字符串，每一位只会是p或j。你需要取出一个子串S（从左到右或从右到左一个一个取出），使得不管是从左往右还是从右往左取，都保证每时每刻已取出的p的个数不小于j的个数。你需要最大化|S|。
Input
第一行一个数n，第二行一个长度n的字符串。
Output
S的最大长度。
Sample Input
6
jpjppj
jpjppj
Sample Output
4
HINT
【样例解释】
取pjpp这个串。
【数据范围】
n≤1000000
Source
把j看成-1，p看成1。。然后询问的串就可以改为l到r中r的前缀和最大且l-1的前缀和最小。。
然后我们用单调队列求出每一个点向前第一个比他大的点的位置。。然后枚举r用线段树查询以他为结尾的区间最靠前的最小值的位置。。然后更新答案。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
struct Tree{int l,r,Min;} tree[N<<2];
char s[N];
int n,a[N],ans,pos,val,h,t,q[N],l[N];
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Build(int pos,int l,int r){
tree[pos].l = l;tree[pos].r = r;
if (l==r) {tree[pos].Min = a[l];return;}
int mid = (l+r)>>1;
Build(pos<<1,l,mid);Build(pos<<1|1,mid+1,r);
tree[pos].Min = min(tree[pos<<1].Min,tree[pos<<1|1].Min);
}
int QueryMin(int pos,int l,int r){
if (tree[pos].l==l && tree[pos].r==r) return tree[pos].Min;
int mid = (tree[pos].l+tree[pos].r)>>1;
if (r<=mid) return QueryMin(pos<<1,l,r);
else if (l>mid) return QueryMin(pos<<1|1,l,r);
else return min(QueryMin(pos<<1,l,mid),QueryMin(pos<<1|1,mid+1,r));
}
int find(int pos){
if (tree[pos].l==tree[pos].r) return tree[pos].l;
if (tree[pos<<1].Min==val) find(pos<<1);
else find(pos<<1|1);
}
int Querypos(int pos,int l,int r){
if (tree[pos].l==l && tree[pos].r==r){
if (tree[pos].Min==val) return find(pos);
else return 1e9;
}
int mid = (tree[pos].l+tree[pos].r)>>1;
if (r<=mid) return Querypos(pos<<1,l,r);
else if (l>mid) return Querypos(pos<<1|1,l,r);
else return min(Querypos(pos<<1,l,mid),Querypos(pos<<1|1,mid+1,r));
}
int main(){
n = read();
scanf("%s",s+1);
for (int i=1;i<=n;i++)
if (s[i]=='j') a[i] = a[i-1]-1;else a[i] = a[i-1]+1;
Build(1,0,n);
a[0] = 1e9;
q[0] = 0;t = 0;
for (int i=1;i<=n;i++){
while (t && a[q[t]]<=a[i]) t--;
l[i] = q[t];q[++t] = i;
}
for (int i=1;i<=n;i++){
val = QueryMin(1,l[i],i);
pos = Querypos(1,l[i],i);
if (i-pos>ans) ans = i-pos;
}
printf("%d",ans);
}
评论 (0)
