BZOJ 2217: [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”。
显然，这个序列最多只有 $O(n)$ 级别的取值.
有一个小性质：任何一个小于等于 $n$ 的 $q$ 肯定能被一个前缀或者一个前缀减去 $1$ 来表示出来.
对于直接可以被一个前缀表示来的 $l,r$ 好处理，现在考虑如何处理被一个前缀减去 $1$ 的情况.
想让值减小 $1,$ 其实就是将一个 $2$ 替换成 $1$.
令 $len[i]$ 表示第 $i$ 位开始极长连续 $2$ 的长度（包括自己).
如果 $len[i]>len[1]$，那么可以将 $len[1]$ 这部份的 $2$ 直接移接到 $i$ 后，然后取到 $len[1]+1$ 的 $1.$
如果 $len[1]>=len[i]$，那么可以将 $len[i]$ 这部分的 $2$ 移接到 $1$ 后，然后取道 $i+len[i]+1$ 处的 $1$. 当然，这个的前提是 $len[i]<n-i+1$.
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
void setIO(string s) {
string in=s+".in";
freopen(in.c_str(),"r",stdin);
}
const int maxn=1000005;
char str[maxn];
int a[maxn],L[maxn<<1],R[maxn<<1],len[maxn];
int main() {
// setIO("input");
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",str+1);
for(int i=1;i<=n;++i) {
if(str[i]=='T') a[i]=2;
else a[i]=1;
}
for(int i=n;i>=1;--i) len[i]=a[i]==2?(len[i+1]+1):0;
int Sum=0;
for(int i=1;i<=n;++i) {
Sum+=a[i];
L[Sum]=1,R[Sum]=i;
if(a[i]==2) {
if(len[i]>len[1]) L[Sum-1]=len[1]+2,R[Sum-1]=i+len[1];
else if(len[i]!=n-i+1) R[Sum-1]=i+len[i],L[Sum-1]=len[i]+1;
}
}
while(m--){
int k;
scanf("%d",&k);
if(L[k]) printf("%d %d
",L[k],R[k]);
else printf("NIE
");
}
return 0;
}