Logical Moos (USACO Bronze 2024 US Open)

每年最后一次考试是US Open，时长比前三次比赛多一个小时，题目更难更繁琐一些，但青铜组总体难度还是不高，仔细思考一定能解决。

给定一个不带括号但是遵守优先级的逻辑表达式，由"true"和"false"以及"and"和"or"组成，如果将[l,r]区间内的表达式替换为true或false，整个表达式是否能取得给定的值（true或者false）？

根据题目的数据规模，我们希望找到一个能够 $\mathcal{O}(1)$ 或者 $\mathcal{O}(\log N)$ 回答每次查询的算法。

逻辑运算在CSP-J的一试的时候就学过了，这里没有括号的话，首先我们可以有一个观察，就是这个表达式是由一系列"and'连接的组，互相用"or"连接起来，形成的一个两层的结构。在一个“组”的内部，只要有一个false，则整个组都取值false；而组间，只要有一个组是true，那么整个表达式就是true。

有了这个理解之后，我们再考虑将[l,r]范围设为true/false的时候，对整个表达式的值的影响，就可以有以下观察：

如果存在有一个组是true，而且这个组不在[l,r]范围内，那么整个表达式就永远是true。
如果l和r所在的组（同一个，或者单独的两个），存在有一个false在l的左侧，有一个false在r的右侧，那么对应的组就永远是false。

因为这样的判断，所以有以下算法：

记录第一个全true的组的位置，和最后一个全true的组的位置，如果[l,r]范围不覆盖这个区间，那么结果就一定是true。
记录每个组的第一个false和最后一个false的位置，如果[l,r]不覆盖l所在组的第一个false，而且不覆盖r所在组的最后一个false，那么表达式的值就一定是false。
其它情况下，表达式的值可以是true或者false。

所以我们需要预处理一遍数据，得到每个组里第一个和最后一个false的位置，以及整个表达式的第一个全true的组的位置，以及最后一个全true的组的位置。然后对每个查询，我们就可以 $\mathcal{O}(1)$ 的时间内回答。整体复杂度为 $\mathcal{O}(N+Q)$ 。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
#define MAX 200001
 
vector<string> ss;
int group_start[200005];
int first_true_group = MAX;
int last_true_group = -1;
int first_false[200005], last_false[200005];       // first and last "false" in each group
int group[200005];
 
int n, Q;
 
int main() {
    cin >> n >> Q;
    ss.resize(n);
    for (int i = 0; i < n; i++) {
        first_false[i] = MAX;
        last_false[i] = -1;
    }
    for (int i = 0; i < n ; i++)
        cin >> ss[i];
    int g = 0;
    group_start[0] = 0;
    bool all_true = true;
    for (int i = 0; i < n; i+=2) {
        group[i] = g;
        if (ss[i] == "false") {
            if (first_false[g] == MAX)
                first_false[g] = i;
            last_false[g] = i;
            all_true = false;
        }
        if (i == n-1 || ss[i+1] == "or") {  // end of group
            if (all_true) {
                if (first_true_group == MAX)
                    first_true_group = g;
                last_true_group = g;
            }
            all_true = true;
            if (i < n-1) {
                g++;
                group_start[g] = i+2;
            }
        }
    }
 
    for (int i = 0; i < Q; i++) {
        int l, r;
        string expect;
        cin >> l >> r >> expect;
        l--; r--;
        int left_group = group[l];
        int right_group = group[r];
        if (left_group > first_true_group || right_group < last_true_group) {
            // result always true
            if (expect == "true") 
                cout << "Y";
            else 
                cout << "N";
            continue;
        } else if (l > first_false[left_group] || r < last_false[right_group]) {
            // result always false
            if (expect == "true") 
                cout << "N";
            else 
                cout << "Y";
            continue;
        } else {
            cout << "Y";
        }
    }
 
    cout << endl;
 
 
    return 0;
}