70分求助awa~
查看原帖
70分求助awa~
210719
Violet___Evergarden楼主2021/10/10 16:09
#include <iostream>
#include <stack>
#include <climits>
using namespace std;
const int kMaxN=1e6+1;
char a[kMaxN];
int n,qzh[kMaxN];
int ri[kMaxN],ans;
stack<int>k;
struct XDS//每个节点记录区间里最大的前缀和数组的下标
{
  int l,r;
  int val;
}tr[kMaxN*4];
void Build(int where,int l,int r)//模板不解释
{
  tr[where].l=l;
  tr[where].r=r;
  if(l==r)
  {
    tr[where].val=l;
    return;
  }
  int mid=(l+r)/2;
  Build(where*2,l,mid);
  Build(where*2+1,mid+1,r);
  tr[where].val=(qzh[tr[where*2].val]>qzh[tr[where*2+1].val]?tr[where*2].val:tr[where*2+1].val);
}
int GetAns(int where,int l,int r)//模板不解释
{
  if(tr[where].l>=l&&tr[where].r<=r)
  {
    return tr[where].val;
  }
  int mid=(tr[where].l+tr[where].r)/2,ans=0;
  if(mid>=l)
  {
    int x=GetAns(where*2,l,r);
    ans=(qzh[ans]>qzh[x]?ans:x);
  }
  if(mid<r)
  {
    int x=GetAns(where*2+1,l,r);
    ans=(qzh[ans]>qzh[x]?ans:x);
  }
  return ans;
}
int main()
{
cin>>n>>a+1;
for(int i=1;i<=n;i++)//处理前缀和数组
{
  qzh[i]=qzh[i-1]+(a[i]=='p'?1:-1);
}
Build(1,1,n);
qzh[0]=INT_MIN;
k.push(n);
for(int i=n;i>=1;i--)//枚举左端点
{
  while(!k.empty()&&qzh[k.top()]>=qzh[i])k.pop();//单调栈
  if(k.empty())ri[i]=n;
  else ri[i]=k.top();
  k.push(i);
  if(i<=ri[i])
  {
    ans=max(ans,GetAns(1,i,ri[i])-i);//求答案
  }
}
cout<<ans;
return 0;
}
2021/10/10 16:09
加载中...