POI2011 棒棒糖

题目:

  Byteasar 在比特镇开了一家糖果店,草莓香草味的棒棒糖是当地孩子们的最爱。这些棒棒糖都是由长度相同的香草味或者草莓味的片段组成的。一整根棒棒糖的价格是每一段棒棒糖的价格之和,每一段香草味的棒棒糖价格为一元,草莓味的棒棒糖价格为两元。
  
  图1:举个例子,这是一根由五段组成的棒棒糖,草莓味和香草味的棒棒糖交替排列,这根棒棒糖的价格为 元。
  现在,Byteasar 只剩下最后一根棒棒糖了。这根棒棒糖太长了,因此 Byteasar 认为绝对没有人会买下这一整根。所以,他想要把这一整根在接缝处掰成几段,每一段单独出售。
  Byteasar 的人生经验告诉他,他的顾客希望把自己的钱花在单独的一根棒棒糖上,于是他想知道这一根棒棒糖有没有连续的一段的价格是 。但这个问题对他来说太难了,他希望你能帮帮他。

思路:

  因为 ,所以如果某个前缀的长度为 ,那 就一定可以是某个前缀。所以只要考虑怎么用 构造出 即可。
  假设当前的前缀为
  首先 的情况就很显然了。
  设 表示 点左侧有多少个连续的
  如果向右移动区间时进来一个 同时又出去一个 ,那权值和肯定是不变的。所以如果 ,就可以右移直到左边的 全部出去时再缩一下左区间,得到的新区间就是
  如果 右侧存在 ,那可以一直右移直到出去一个 并进去一个 ,得到的区间就是
  手玩可以发现这样是可以造出所有情况的,所以就能 解决了。

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 1e6 + 5, M = 2 * N;

int l[M], r[M], cnt[N];
char s[N];

int main() {
    // freopen("data.in", "r", stdin);
    int n, m, k;
    scanf("%d%d", &n, &m);
    scanf("%s", s + 1);
    drep(i, n, 1) cnt[i] = (s[i] == 'W' ? 0 : cnt[i + 1] + 1);
    int sum = 0;
    rep(i, 1, n) {
        sum += (s[i] == 'W' ? 1 : 2);
        l[sum] = 1; r[sum] = i;
        if(s[1] == 'W') {l[sum - 1] = 2; r[sum - 1] = i; continue;}
        if(s[i] == 'W') continue;
        if(cnt[1] < cnt[i]) l[sum - 1] = 2 + cnt[1], r[sum - 1] = i + cnt[1];
        else if(cnt[i] != n - i + 1) l[sum - 1] = 1 + cnt[i], r[sum - 1] = i + cnt[i];
    }
    rep(i, 1, m) {
        scanf("%d", &k);
        if(l[k] == 0) puts("NIE");
        else printf("%d %d\n", l[k], r[k]);
    }
    return 0;
}