BZOJ4964 : 加长的咒语

把$($看作$-1$，$)$看作$1$，设$a$为前缀和，则相当于找两个位置$x,y$使得$a[x]=a[y]$，且$a[x]$是$[x,y]$的区间最大值。

求出询问区间的最大值$o$，然后找到$o$在该区间内最左和最右的出现位置，将其作为答案。

那么剩下的答案只可能在$[l,o)$或$(o,r]$，以$[l,o)$为例。

通过单调栈求出每个位置$i$往右最长延伸长度$g[i]$，使得中间$a[i]$是区间最大值，且$a[i]=a[i+g[i]]$。

那么在$[l,o)$中，因为$o$的阻隔，必然满足$i+g[i]<o$，找到最大的即可。

时间复杂度$O(n\log n)$。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef pair<int,int>P;

const int N=400010,M=1050000,inf=~0U>>1;

int n,m,i,x,y,l,r,o,ans,a[N],q[N],t,f[N],g[N],v[M],vf[M],vg[M];P b[N];char s[N];

inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

inline void up(int&a,int b){a<b?(a=b):0;}

void build(int x,int a,int b){

  if(a==b){

    v[x]=::a[a];

    vf[x]=f[a];

    vg[x]=g[a];

    return;

  }

  int mid=(a+b)>>1;

  build(x<<1,a,mid),build(x<<1|1,mid+1,b);

  v[x]=max(v[x<<1],v[x<<1|1]);

  vf[x]=max(vf[x<<1],vf[x<<1|1]);

  vg[x]=max(vg[x<<1],vg[x<<1|1]);

}

int ask(int x,int a,int b,int c,int d,int*v){

  if(c<=a&&b<=d)return v[x];

  int mid=(a+b)>>1,t=-inf;

  if(c<=mid)t=ask(x<<1,a,mid,c,d,v);

  if(d>mid)up(t,ask(x<<1|1,mid+1,b,c,d,v));

  return t;

}

int main(){

  scanf("%d%d%s",&n,&m,s+2);n++;

  for(i=2;i<=n;i++)a[i]=a[i-1]+(s[i]==')'?1:-1);

  for(i=1;i<=n;i++)b[i]=P(a[i],i);

  sort(b+1,b+n+1);

  for(q[t=0]=0,i=1;i<=n;q[++t]=i++){

    while(t&&a[i]>=a[q[t]])t--;

    f[i]=i-upper_bound(b+1,b+n+1,P(a[i],q[t]))->second;

  }

  for(q[t=0]=n+1,i=n;i;q[++t]=i--){

    while(t&&a[i]>=a[q[t]])t--;

    g[i]=(lower_bound(b+1,b+n+1,P(a[i],q[t]))-1)->second-i;

  }

  build(1,1,n);

  while(m--){

    read(x),read(y);y++;

    o=ask(1,1,n,x,y,v);

    l=lower_bound(b+1,b+n+1,P(o,x))->second;

    r=(upper_bound(b+1,b+n+1,P(o,y))-1)->second;

    ans=r-l;

    if(l>x)up(ans,ask(1,1,n,x,l-1,vg));

    if(r<y)up(ans,ask(1,1,n,r+1,y,vf));

    printf("%d\n",ans);

  }

  return 0;

}