BZOJ 2217: [Poi2011]Lollipop 构造 + 思维

// 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\n",L[k],R[k]); 
        else printf("NIE\n"); 
    }
    return 0; 
}