给定长度为 \(n\) 的序列，里面的元素为1或2，求是否有一种方案，取出连续的一段，使得到的元素和等于给定的值，若可以则输出一种方案。多组询问， \(n,q\leq 10^6\) 。
感觉有点水，典型构造题，首先可以知道权值和 \(sum\) 一定可以取到，方案为 \([1,n]\) 。假设我们现在知道了大小为 \(len\) 的合法方案 \([l,r]\) ，那么思考推出别的。若最左边/最右边有2，那么可以去掉那个2，得到大小为 \(len-2\) 的合法构造 \([l+1,r]\) 或 \([l,r-1]\) ，反之则左右都是1，那么直接都删掉得到大小为 \(len-2\) 的构造 \([l-1,r-1]\) 。然而这只能解决所有与 \(sum\) 奇偶性相同的长度，不同的需要额外解决。考虑从 \([1,n]\) 的两侧分别枚举，直到找到第一个1为止，那么奇偶性发生变化，贪心选两侧中更优的，再重复刚才的步骤。关于为什么不综合两端得到答案，因为那样一定不如只取一端好，因为只有一边会影响奇偶性，另一边就白删了，那么预处理所有可能情况的方案，可以做到 \(O(n)\) 预处理， \(O(1)\) 查询。
#include<bits/stdc++.h>
using namespace std;
int n,q;
char s[1000005];
int ss[1000005];
int l[1000005],r[1000005];
int main(){
scanf("%d %d",&n,&q);
scanf("%s",s+1);
int sum=0;
for(int i=1;i<=n;++i){
ss[i]=(s[i]=='T')?2:1;
sum+=ss[i];
}
int max1=sum,max2=sum,maxid1,maxid2;
for(int i=1;i<=n;++i){
if(ss[i]==2)
max1-=2;
else{
maxid1=i+1;
max1-=1;
break;
}
}
for(int i=n;i>=1;--i){
if(ss[i]==2)
max2-=2;
else{
maxid2=i-1;
max2-=1;
break;
}
}
if(max1>max2){
l[max1]=maxid1;
r[max1]=n;
}
else{
l[max2]=1;
r[max2]=maxid2;
}
for(int i=max(max1,max2)-2;i>=1;i-=2){
if(ss[l[i+2]]==2){
l[i]=l[i+2]+1;
r[i]=r[i+2];
}
else if(ss[r[i+2]]==2){
l[i]=l[i+2];
r[i]=r[i+2]-1;
}
else{
l[i]=l[i+2]+1;
r[i]=r[i+2]-1;
}
}
l[sum]=1,r[sum]=n;
for(int i=sum-2;i>=1;i-=2){
if(ss[l[i+2]]==2){
l[i]=l[i+2]+1;
r[i]=r[i+2];
}
else if(ss[r[i+2]]==2){
l[i]=l[i+2];
r[i]=r[i+2]-1;
}
else{
l[i]=l[i+2]+1;
r[i]=r[i+2]-1;
}
}
while(q--){
int x;
scanf("%d",&x);
if(r[x]==0 && l[x]==0)
puts("NIE");
else
printf("%d %d\n",l[x],r[x]);
}
return 0;
}