BZOJ 2217 Poi2011 Lollipop - c++编程基础

题目大意：给定一个由1和2组成的序列，多次询问是否存在一个区间满足区间和= x
如果 x>sum 显然无解
如果存在一个前缀和为 x 则直接输出
否则一定存在一个前缀和 [1,i] 等于 x+1
然后我们将左右端点同时右移显然如果某一时刻 a[l]=1 或者 a[r+1]=1 那么我们就找到解了

记录 exti 表示从 i 开始有多少个连续的 2
如果 ext1 ，那么解为 [1+ext1+1,i+ext1]
如果 ext1≥exti 且 i+exti≠n+1 ，那么解为 [1+exti,i+exti]
否则无解
O(n) 预处理所有答案即可

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define M 2002002 using namespace std; int n,m,sum; char s[M>>1]; int ext[M],l[M],r[M]; int main() { int i,x; cin>>n>>m; scanf("%s",s+1); for(i=n;i;i--) { ext[i]=ext[i+1]+1; if(s[i]=='W') ext[i]=0; } for(i=1;i<=n;i++) { sum+=s[i]=='W'?1:2; l[sum]=1;r[sum]=i; if(s[i]=='T') { if(ext[1]
       
        sum || !l[x] ) puts("NIE"); else printf("%d %d\n",l[x],r[x]); } return 0; }