Logical Moos

题意

给定一个布尔表达式，奇数位置是 true/false，偶数位置是 $and/or$ 。求值时 and 优先级高于 or。

每次询问给出一段 [l,r]，删除这段 token，并用一个单独的 true 或 false 替换。问是否存在一种替换值，使整个表达式的结果等于询问给定的目标值。

思路

暴力想法

对每个询问，可以分别尝试把 [l,r] 替换成 true 和 false，然后重新计算表达式。

计算表达式时，先把连续的 and 段算成一个布尔值，再把这些值用 or 合并。

这个暴力适合小数据和对拍：

cpp

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 12:39
 * update_at: 2026-07-11 12:40
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int n, q;
vector<string> words;

bool eval_expression(vector<string> expr) {
    vector<string> groups;
    int i = 0;

    // 先把连续 and 段计算成一个 boolean。
    while (i < (int)expr.size()) {
        bool value = (expr[i] == "true");
        int j = i + 1;
        while (j < (int)expr.size() && expr[j] == "and") {
            bool next_value = (expr[j + 1] == "true");
            value = value && next_value;
            j += 2;
        }
        groups.push_back(value ? "true" : "false");
        i = j + 1; // 跳过当前 group 后面的 or。
    }

    // group 之间都是 or，只要有一个 true 即可。
    for (int k = 0; k < (int)groups.size(); k++) {
        if (groups[k] == "true") {
            return true;
        }
    }
    return false;
}

bool check_query(int l, int r, string want) {
    bool target = (want == "true");

    for (int value = 0; value <= 1; value++) {
        vector<string> expr;
        for (int i = 1; i < l; i++) {
            expr.push_back(words[i]);
        }
        expr.push_back(value == 1 ? "true" : "false");
        for (int i = r + 1; i <= n; i++) {
            expr.push_back(words[i]);
        }

        if (eval_expression(expr) == target) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    words.assign(n + 1, "");
    for (int i = 1; i <= n; i++) {
        cin >> words[i];
    }

    for (int i = 1; i <= q; i++) {
        int l, r;
        string want;
        cin >> l >> r >> want;
        cout << (check_query(l, r, want) ? 'Y' : 'N');
    }
    cout << '\n';

    return 0;
}

每个询问重新计算一次表达式需要 $O(N)$ ，满分数据中 $N,Q$ 都很大，需要进一步预处理。

按 `or` 分组

因为 and 优先级高于 or，可以把表达式按 or 切成若干个 group。

例如：

text

1false and true or true

等价于：

text

1(false and true) or (true)

一个 group 是若干个布尔值用 and 连接。它为 true 当且仅当组内没有 false。整个表达式为 true 当且仅当至少一个 group 为 true。

回答询问

对每个布尔位置预处理它属于哪个 group。对每个 group 记录：

第一个 false 的位置；
最后一个 false 的位置。

同时记录原表达式中最左和最右的 true group。

询问 [l,r] 时，设：

text

1
2gl = group[l]
gr = group[r]

如果 gl 左边或 gr 右边存在 true group，那么无论替换什么，整个表达式都一定为 true。因此目标为 true 时可行，目标为 false 时不可行。

否则，区间外所有 group 都是 false。如果目标是 false，直接把删除段替换成 false 即可。

如果目标是 true，只能靠替换后新形成的 group 变成 true。这要求它没有残留的 false：

text

1
2gl 中不能有 false 在 l 左边
gr 中不能有 false 在 r 右边

用 first_false[gl] 和 last_false[gr] 就能 $O(1)$ 判断。

代码

cpp

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 12:39
 * update_at: 2026-07-11 12:40
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int INF = 1000000000;

int n, q;
string token_word[MAXN];
int group_id[MAXN];      // boolean 位置所在的 and-group 编号
int first_false[MAXN];   // 每组最左边的 false 位置
int last_false[MAXN];    // 每组最右边的 false 位置
int group_cnt;
int first_true_group, last_true_group;

void read_input() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> token_word[i];
    }
}

void build_groups() {
    group_cnt = 1;
    for (int i = 1; i <= n; i++) {
        if (token_word[i] == "or") {
            group_cnt++;
        } else if (i % 2 == 1) {
            group_id[i] = group_cnt;
        }
    }

    for (int i = 1; i <= group_cnt; i++) {
        first_false[i] = INF;
        last_false[i] = -1;
    }

    for (int i = 1; i <= n; i += 2) {
        int g = group_id[i];
        if (token_word[i] == "false") {
            if (first_false[g] == INF) {
                first_false[g] = i;
            }
            last_false[g] = i;
        }
    }

    first_true_group = INF;
    last_true_group = -1;
    for (int g = 1; g <= group_cnt; g++) {
        // 一个 and-group 没有 false，整个组才为 true。
        if (first_false[g] == INF) {
            if (first_true_group == INF) {
                first_true_group = g;
            }
            last_true_group = g;
        }
    }
}

bool can_make(int l, int r, string want) {
    int gl = group_id[l];
    int gr = group_id[r];

    // 被删区间外面如果还存在 true group，整个表达式一定为 true。
    if (first_true_group < gl || last_true_group > gr) {
        return want == "true";
    }

    if (want == "false") {
        return true;
    }

    // 想得到 true，就要替换后的这个 group 没有残留 false。
    if (first_false[gl] < l) {
        return false;
    }
    if (last_false[gr] > r) {
        return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    build_groups();

    for (int i = 1; i <= q; i++) {
        int l, r;
        string want;
        cin >> l >> r >> want;
        cout << (can_make(l, r, want) ? 'Y' : 'N');
    }
    cout << '\n';

    return 0;
}

复杂度

预处理时间复杂度 $O(N)$ 。

每个询问 $O(1)$ 回答，总时间复杂度 $O(N+Q)$ 。

空间复杂度 $O(N)$ 。

总结

这题的关键是把布尔表达式转成“多个 and-group 做 or”的结构。

一旦知道每个 group 是否含有 false，以及查询区间外是否已经有 true group，就可以把替换询问化成几个位置比较。

目录

题意

思路

暴力想法

按 or 分组

回答询问

代码

复杂度

总结

按 `or` 分组