[POI2011]LIZ-Lollipop

构造 思维

题面

给一个只有$1$和$2$的序列，每次询问有没有一个子串的和为$x$。

• $n\leq10^6$

解析

一道挺不错的思维题。

只有$1$和$2$的性质其实很妙。这意味着大多数的$x$都是存在的。
先预处理前缀和。
如果当前$x$不是某一前缀和，那么$x+1$一定是某一前缀和。（因为$x$不为前缀和当且仅当$s_{i-1}=x-1,a_i=2$)
那么我们可以利用一下前缀和为$x+1$的区间来得到所求区间。

显然我们需要在左端或右端删掉一个$1$。
可以预处理一下每个点右边最近的$1$在哪里。
然后两边跳同样的距离即可（让一边删掉一个$1$，另一边没删）。
注意一下边界（比如尽量内缩而不是外伸），问题就解决了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=2e6+100;
int las[N],n,m,a[N],pos[N];
char s[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=gi();
  scanf("%s",s+1);
  fp(i,1,n) a[i]=a[i-1]+(s[i]=='W'?1:2),pos[a[i]]=i;
  fq(i,n,1) if(s[i]=='T') las[i]=las[i+1]+1;
  while(m--)
    {
      re int x=gi();
      if(x>a[n]) puts("NIE");
      else if(pos[x]) printf("%d %d\n",1,pos[x]);//x+1一定存在
      else if(las[pos[x+1]]>las[1]) printf("%d %d\n",2+las[1],pos[x+1]+las[1]);//前面删1（记得是1~1+las[1]删了，所以从1+las[1]+1开始）
      else if(las[pos[x+1]]+pos[x+1]<=n) printf("%d %d\n",1+las[pos[x+1]],pos[x+1]+las[pos[x+1]]);//后面删1
      else puts("NIE");
    }
  return 0;
}