BZOJ2217 Poi2011 Lollipop 【思维+模拟】

Description

有一个长度为n的序列a1,a2,...,an。其中ai要么是1("W")，要么是2("T")。

现在有m个询问，每个询问是询问有没有一个连续的子序列，满足其和为q。

Input

第一行n，m (1<=n,m<=1000000)

第二行这个序列，起始编号为1，终止编号为n

下面每行一个询问q，询问有没有一个连续的子序列，满足其和为q (1<=q<=2000000)

Output

对于每个询问，输出一行，如果有，输出这个序列的起点和终点(如果有多个输出任意一个)；如果没有，输出“NIE”。

Sample Input

5 3

TWTWT

5

1

7

Sample Output

1 3

2 2

NIE

有一个结论，如果可以凑出x那么一定可以凑出x-2

分情况讨论，如果区间中有一个2那么直接删掉这个二

如果没有那么删掉两边的1

直到没有数

所以直接求出最大的奇数和偶数就可以了

#include<bits/stdc++.h>

using namespace std;

#define fu(a,b,c) for(int a=b;a<=c;++a)

#define fd(a,b,c) for(int a=b;a>=c;--a)

#define N 1000010

int a[N],n,m;

int l_line[N<<1],r_line[N<<1];

int main(){

  scanf("%d%d",&n,&m);

  getchar();

  int sum=0;

  fu(i,1,n){

    char c=getchar();

    if(c=='W')a[i]=1;

    else a[i]=2;

    sum+=a[i];

  }

  int l=1,r=n,now=sum;

  while(l<=r){

    l_line[now]=l,r_line[now]=r;

    if(a[l]>1)l++,now-=2;

    else if(a[r]>1)r--,now-=2;

    else if(l<r-1)l++,r--,now-=2;

    else break;

  }

  l=0,r=0;

  fu(i,1,n)if(a[i]==1){l=i;break;}

  fd(i,n,1)if(a[i]==1){r=i;break;}

  if(l&&r){

    now=max(sum-(n-r)*2-1,sum-l*2+1);

    if((n-r)>l-1)r=n,l++;

    else l=1,r--;

  }

  while(l<=r){

    l_line[now]=l,r_line[now]=r;

    if(a[l]>1)l++,now-=2;

    else if(a[r]>1)r--,now-=2;

    else if(l<r-1)l++,r--,now-=2;

    else break;

  }

  fu(i,1,m){

    int x;scanf("%d",&x);

    if(x>sum||!l_line[x])printf("NIE\n");

    else printf("%d %d\n",l_line[x],r_line[x]);

  }

  return 0;

}

巴特西