洛谷题单指南-线段树-P5522 [yLOI2019] 棠梨煎雪

原题链接：https://www.luogu.com.cn/problem/P5522

题意解读：有若干0/1/?组成的字符串，支持两种操作：1.将制定位置字符串修改成新字符串；2.查询区间内字符串能否统一成一个字符串，求有多少种可能；将2的所有结果异或起来，再和0异或，输出最终答案。注意：?表示可以用0或1取代。

解题思路：单点修改，区间查询，可以用线段树解决。

关键看线段树节点维护什么信息？

字符串要能统一成一个，对应位置字符必须符合：1.都是'1' 2.都是'0' 3.有一个是'?'

对于1/2是固定的，对于3，如果一个是'?'一个是非'?'那么情况也是唯一的，如果两个都是'?'那么既可以都是'1'又可以都是'0'，这样就会有2中可能

因此对于两个字符串能统一成多少种相同的串，就是要找到有多少个位置都是'?'，设有x个，则一共有2^x中可能。

如果直接维护字符串，在进行pushup等操作的时候每次常数都比较高，需要一种更优化的方式，如果将对应位置的值映射到二进制就好处理了。

方式如下：

设v1是一个整数，其二进制表示一个01?字符串中确定是'1'的位置为1，如0?1，第2个位置是'1'，那么v1二进制为100，v1=4

设v2是一个整数，其二进制表示一个01?字符串中确定是'0'的位置为1，如0?1，第0个位置是'0'，那么v2二进制为001，v2=1

有了以上定义，

1、在进行节点合并时，root.v1 = left.v1 | right.v1，root.v2 = left.v2 | right.v2

2、在进行区间查询时，直接返回合并后的结果即可，再进一步进行判断和统计?的个数，

- 判断逻辑：如果v1 & v2不为0，说明多个字符串相同位置既有'1'又有'0'，不可能统一成一种，结果是0

- 统计方式：如果v1 & v2为0，将v1 | v2，统计其中字符串长度范围内0的个数x，即表示'?'的个数，再取2^x，即表示可以统一成多少种字符串

3、单点修改操作就是常规的修改，注意将字符串转化成v1、v2

具体细节参考代码。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

struct Node
{
    int l, r;
    int v1; //v1的二进制表示中，[l,r]区间内所有字符串位置i为'1'才是1
    int v2; //v1的二进制表示中，[l,r]区间内所有字符串位置i为'0'才是1
} tr[N * 4];
string a[N];
int n, m, q, ans;

void pushup(Node &root, Node &left, Node &right)
{
    root.v1 = left.v1 | right.v1;
    root.v2 = left.v2 | right.v2;
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if(l == r)
    {
        for(int i = 0; i < a[l].length(); i++)
        {
            if(a[l][i] == '1') tr[u].v1 |= (1 << i);
            else if(a[l][i] == '0') tr[u].v2 |= (1 << i);
        }
    }
    else
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

Node query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    else if(tr[u].l > r || tr[u].r < l) return Node{};
    else
    {
        Node res = {};
        Node left = query(u << 1, l, r);
        Node right = query(u << 1 | 1, l, r);
        pushup(res, left, right);
        return res;
    }
}

void update(int u, int pos, string t)
{
    if(tr[u].l == tr[u].r) 
    {
        tr[u].v1 = tr[u].v2 = 0; //先清空
        for(int i = 0; i < t.length(); i++)
        {
            if(t[i] == '1') tr[u].v1 |= (1 << i);
            else if(t[i] == '0') tr[u].v2 |= (1 << i);
        }
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(pos <= mid) update(u << 1, pos, t);
        else update(u << 1 | 1, pos, t);
        pushup(u);
    }
}

int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++) cin >> a[i];
    build(1, 1, m);
    int op, l, r, pos;
    string t;
    while(q--)
    {
        cin >> op;
        if(op == 0)
        {
            cin >> l >> r;
            Node res = query(1, l, r);
            if(res.v1 & res.v2) //说明有'1'的位置也有'0'，不能统一成一个字符串
            {
                ans ^= 0; //结果是0
            }
            else
            {
                int x = res.v1 | res.v2;
                int cnt = 0;
                for(int i = 0; i < n; i++)
                {
                    if(x >> i & 1) cnt++; //统计确定是'1'或'0'的位置数量
                }
                int ques = n - cnt; //'?'的个数
                ans ^= (1 << ques); // 2^ques即有多少种字符串组合
            }
        }
        else
        {
            cin >> pos >> t;
            update(1, pos, t);
        }
    }
    cout << ans;
    return 0;
}