LOJ2430：[POI2014]沙拉餐厅Salad Bar—

LOJ2430：[POI2014]沙拉餐厅Salad Bar——题解

阅读量：6808 次

发布时间：2019-06-26

本文共 1261 字，大约阅读时间需要 4 分钟。

是的我BZOJ又没卡过……懒得卡了。

参考：

参考的$O(n)$预处理我反正没看懂……设$L[i]$为i向左能够取到的最远位置，$R[i]$同理。

则我们$O(nlogn)$就能求出来，就是前缀和维护一个st表区间最小值，这样二分答案只要check这个区间最小值+前面没有取到的贡献就行了。

判断的话实际转换成求$L,R$必须满足$L[R]<=L$ $R<=R[L]$

我们可以对R进行排序然后树状数组维护L，具体的做法可以看代码画个图，你就知道为啥对了。

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long ll;const int N=1e6+5;const int INF=1e9;char s[N];int n,a[N],tr[N];int f[N][20],lg[N],L[N],R[N];inline int qpow(int a){ return 1<
                
                 n)break; f[i][j]=min(f[i][j-1],f[i+qpow(j-1)][j-1]); }}struct node{ int R,id; bool operator <(const node &a)const{ return R
                 
                  >1; if(qry(i,mid)-a[i-1]>=0)l=mid; else r=mid-1; } g[i].R=l,g[i].id=i; } for(int i=1;i<=n;i++) if(s[n-i+1]=='p')a[i]=a[i-1]+1; else a[i]=a[i-1]-1; for(int i=1;i<=n;i++)f[i][0]=a[i]; st(); for(int i=1;i<=n;i++){ int l=i-1,r=n; while(l
                  
                   >1; if(qry(i,mid)-a[i-1]>=0)l=mid; else r=mid-1; } L[n-i+1]=n-l+1; } sort(g+1,g+n+1); int now=1,ans=0; for(int i=1;i<=n;i++){ while(now<=g[i].R){ add(L[now],now);now++; } int r=query(g[i].id); ans=max(ans,r-g[i].id+1); } printf("%d\n",ans); return 0;}