由于and比or的优先级高，我们可以把整个表达式看成是一个个与段的连续或之后的结果
![[Pasted image 20250409153010.png]]

对于每个and区间，我们只需要关注里面是不是有0即可，有一个0这一段的结果就是false。对于整个or的结果，我们只需要关注是不是有一段and区间的结果为1，有一个1最终的结果都会是true
于是我们用前缀和来记录这些区间有0和1的数量。用ones[cnt]表示从开始到第cnt段and区间中，and区间的结果为1的数量。用zeros[i]表示第i个布尔值所在的and区间的起点开始，到i这一段内0的数量。

要注意，有几段and就有几个ones，而zeros表示的并不是全局含义，而是在每个and块中0的数量，因为对于每个and区间，我们只需要关注里面是不是有0

所以在划出修改区间之后，我们可以把整个串分成五段
![[Pasted image 20250409154526.png]]

其中1和2用ones来表示，3和4用zeros来判断，5可以改成true和false两种情况，枚举一下即可

#include <iostream>

using namespace std;

const int N = 2e5 + 10;

int n, m;
int q[N];       // q[i] 表示第 i 个位置的关键字类型：1 为 true 或 or，0 为 false 或 and
int id[N];      // id[i] 表示第 i 个位置（奇数位置）所属的“块”编号
int l[N], r[N]; // l[cnt] 和 r[cnt] 分别表示第 cnt 个“块”的左边界和右边界
int ones[N];    // ones[cnt] 表示前 cnt 个“块”中值为 true 的“块”的数量（前缀和）
int zeros[N];   // zeros[i] 表示从所在“块”开头到位置 i 的 false 数量（前缀和）
int cnt;        // cnt 表示“块”的总数
string s;

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        if (s == "true" or s == "or")
            q[i] = 1;

        // 只处理奇数位置（布尔值位置）
        if (i & 1)
        {
            // 如果是第一个布尔值 (i == 1) 或前一个位置是 "or" (q[i-1] = 1)，则开始一个新“块”
            if (i == 1 or q[i - 1])
            {
                cnt++;
                l[cnt] = i;
                // 注意每次遇见一个新块才能确定上一个块的右边界位置
                r[cnt - 1] = i - 2;
                // 初始化当前“块”的 false 计数：q[i] = 0 时为 1，否则为 0
                zeros[i] = !q[i];
                // 如果不是第一个“块”，更新前一个“块”的 ones 值
                // ones[cnt-1] = 前 cnt-2 个“块”的 true 数量 + 前一个“块”是否为 true
                // 前一个“块”为 true 当且仅当其 false 数量为 0，即 !zeros[i-2]
                if (cnt > 1)
                    ones[cnt - 1] = ones[cnt - 2] + !zeros[i - 2];
            }
            // 如果不开始新“块”，则累加当前“块”的 false 数量
            // zeros[i] = 前一个布尔位置的 false 数量 + 当前位置是否为 false
            else
                zeros[i] = zeros[i - 2] + !q[i];

            id[i] = cnt;
        }
    }

    // 处理最后一个块
    r[cnt] = n;
    ones[cnt] = ones[cnt - 1] + !zeros[n];

    while (m--)
    {
        int left, right;
        cin >> left >> right >> s;
        int lid = id[left], rid = id[right];
        bool res = s == "true" ? true : false;
        // a是1和2，b是3和4
        int a = ones[lid - 1] + ones[cnt] - ones[rid];
        int b = zeros[r[rid]] - zeros[right];
        // 如果left是开头，则没有3
        if (l[lid] != left)
            b += zeros[left - 2];
        // 枚举改为false和true的情况
        cout << (((a or !b and false) == res or (a or !b and true) == res) ? "Y" : "N");
    }

    return 0;
}