「题解」Luogu3514 [POI2011]LIZ-Lollipop

发表于 更新于 分类于
Luogu3514 [POI2011]LIZ-Lollipop 题解

题目链接：Luogu3514 [POI2011]LIZ-Lollipop

#题意简述

给定一个长度为 \(n(n\leq10^6)\) 的仅由 \(1,2\) 组成的序列，\(q(q\leq10^6)\) 次询问，每次询问是否存在一个子串使得子串和为 \(k\)，不存在输出 NIE，否则输出任意一个可行的区间左右端点。

#大致思路

首先，观察到询问次数较多，需要考虑将所有可能组成的值的区间全部处理出来，由于所有可能的值的数量较大，于是需要考虑通过寻找所有可能的值的区间之间的关系进行递推。

假设我们已知 \(k\) 的表示区间，考虑将该区间进行微量的改动可能造成的影响。考虑到添加只是删除操作的逆操作，且需要考虑的边界问题较少，于是这里讨论删除操作。假设当前边界两端都是 \(1\)，显然可以得到 \(k-1\) 和 \(k-2\) 的区间；假设当前边界的两端为 \(1\) 和 \(2\)，那么可以得到 \(k-1\) 和 \(k-2\) 的区间；如果两边都是 \(2\)，那么只能得到 \(k-2\) 的区间。

综上，我们发现，如果 \(k(k>2)\) 能够被组成，那么 \(k - 2\) 一定可以被组成，只需要删除至多两个位置即可。

于是，我们只需要找到最大的可表示的奇数与最大的可表示的偶数即可，显然是一个前缀或后缀的形式。

参考代码

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int N = 2000010;
const int INF = 0x3f3f3f3f;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int n, q, sum[N], a[N], mx[2], l[N], r[N]; char c[N];

inline void update(int x, int lp, int rp) {
    if (mx[x & 1] < x) mx[x & 1] = x, l[x] = lp, r[x] = rp;
}

inline void get_pos(int x) {
    if (a[l[x + 2]] == 1 && a[r[x + 2]] == 1)
      l[x] = l[x + 2] + 1, r[x] = r[x + 2] - 1;
    else if (a[l[x + 2]] == 2)
      l[x] = l[x + 2] + 1, r[x] = r[x + 2];
    else l[x] = l[x + 2], r[x] = r[x + 2] - 1;
}

int main() {
    read(n), read(q); scanf("%s", c + 1);
    for (int i = 1; i <= n; ++ i) a[i] = c[i] == 'T' ? 2 : 1;
    for (int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + a[i];
    for (int i = n; i >= 1; -- i) update(sum[i], 1, i);
    for (int i = 1; i <= n; ++ i) update(sum[n] - sum[i - 1], i, n);
    for (int i = mx[1] - 2; i > 0; i -= 2) get_pos(i);
    for (int i = mx[0] - 2; i > 0; i -= 2) get_pos(i);
    while (q --) {
        int x = 0; read(x);
        if (x > mx[x & 1]) printf("NIE\n");
        else printf("%d %d\n", l[x], r[x]);
    }
    return (0 - 0);
}