cjb-poi2011lollipop

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define N 1000010
int n,m;
char s[N];
int a[N];
pair<int,int> ans[2*N];
void fuck(int l,int r)
{
    int now=0; for(int i=l;i<=r;i++)now+=a[i];
    while (l<=r)
    {
        //cout<<now<<" "<<l<<" "<<r<<endl;
        ans[now]=mp(l,r);
        if (a[l]+a[r]==2)l++,r--;
        else if (a[l]==2)l++;
        else r--;
        now-=2;
    }
}
int main()
{
    cin>>n>>m;
    scanf("%s",s+1);
    rep(i,n)a[i]=(s[i]=='T')?2:1;

    int t1=1; while (t1<=n && a[t1]==2)t1++;
    int t2=n; while (t2>=1 && a[t2]==2)t2--;
    fuck(1,n); fuck(t1+1,n); fuck(1,t2-1);

    rep(i,m)
    {
        int k;
        scanf("%d",&k);
        if (ans[k].first==0)puts("NIE");
        else printf("%d %d\n",ans[k].first,ans[k].second);
    }
    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define N 1000010
int n,m;
char s[N];
int a[N];
pair<int,int> ans[2*N];
void fuck(int l,int r)
{
    int now=0; for(int i=l;i<=r;i++)now+=a[i];
    while (l<=r)
    {
        //cout<<now<<" "<<l<<" "<<r<<endl;
        ans[now]=mp(l,r);
        if (a[l]+a[r]==2)l++,r--;
        else if (a[l]==2)l++;
        else r--;
        now-=2;
    }
}
int main()
{
    cin>>n>>m;
    scanf("%s",s+1);
    rep(i,n)a[i]=(s[i]=='T')?2:1;
    int t1=1; while (t1<=n && a[t1]==2)t1++;
    int t2=n; while (t2>=1 && a[t2]==2)t2--;
    fuck(1,n); fuck(t1+1,n); fuck(1,t2-1);
    rep(i,m)
    {
        int k;
        scanf("%d",&k);
        if (ans[k].first==0)puts("NIE");
        else printf("%d %d\n",ans[k].first,ans[k].second);
    }
    return 0;
}