NOIP模拟赛 密码锁

题意

有把串级连接的锁（前一把的输入连接到后一把的输出），每一把锁将输入和一个操作数进行与，或，异或之一的二元位运算的结果作为输出，给定初始时每把锁的参数和运算类型。接下来个操作共两种：

1. 查询某个数通过这一串锁的结果
2. 修改某个锁的操作数和运算

$n ^5, m ^5 $，保证查询的数和操作数不超过。

解法

从数据范围可知正解的复杂度是级别的，考虑其操作中又有查询又有修改，直觉上我们断定这是一道数据结构题。

那维护什么呢？位运算？肯定是不行的，原因就是位运算是不结合的，比如说(a | b) & c就不一定等于a | (b & c)，而无论是线段树还是树状数组都只能维护有结合律的代数结构，因此直接维护位运算是行不通的。

但是因为二元位运算的一个操作数已经给出，而且每个位的运算有互不干扰，我们可以把给定的一个二元位运算转化为若干个依赖于输入某一位的一元位运算或函数。

那么这样做有什么好处呢？我们看看这样的一元函数有哪些：

1. ：将输入位直接输出。
2. ：将输入位取反输出。
3. ：输出恒为0。
4. ：输出恒为1。

定义它们之间的二元运算为串联：，则有如下性质：

1. 结合律：
2. 单位元：
3. 封闭性：任意两个运算的复合都是这四个运算之一（自己列张表）

可以看到这构成了一个幺半群，因此可以用线段树进行维护。接下来就很简单了，开棵线段树分别维护每一位，然后单点修改全局查询即可。

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
#define rg register

using namespace std;
typedef long long ll;
typedef unsigned int u32;
#define lch (rt << 1)
#define rch (lch | 1)
#define larg lch, l, mid
#define rarg rch, mid + 1, r
#define bit(a, b) (((a) >> (b)) & 1)
const int INF = 0x3f3f3f3f;
const int BITS = 10;
const int N = 200010;
const int T = N * 4;
const int r[4][4] = {
    { 0, 1, 1, 0 }, // 0
    { 0, 1, 0, 1 }, // 1
    { 0, 1, 3, 2 }, // N
    { 0, 1, 2, 3 } // E 
};
const int p[4][2] = {
    { 0, 0 },
    { 1, 1 },
    { 1, 0 },
    { 0, 1 }
};
const int x[3][2] = {
    { 0, 3 }, // AND
    { 3, 1 }, // OR
    { 3, 2 } // XOR
};

char t[BITS][T], a[BITS][N];
char s[5];
int n, m;

inline int read() {
    char ch = getchar(), s = 1;
    while (!isdigit(ch)) {
        if (ch == '-') s = -1;
        ch = getchar();
    }
    int ans = 0;
    while (isdigit(ch)) {
        ans = ans * 10 + ch - 48;
        ch = getchar();
    }
    return ans * s;
}

inline void pushup(int z, int rt) {
    t[z][rt] = r[t[z][lch]][t[z][rch]];
}

void build(int z, int rt, int l, int r) {
    if (l == r) {
        t[z][rt] = a[z][l];
        return;
    }
    int mid = (l + r) >> 1;
    build(z, larg);
    build(z, rarg);
    pushup(z, rt);
}

void update(int z, int rt, int l, int r, int pos, int d) {
    if (l == r) {
        t[z][rt] = d;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(z, larg, pos, d);
    else update(z, rarg, pos, d);
    pushup(z, rt);
}

int main() {
    freopen("cipher.in", "r", stdin);
    freopen("cipher.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (rg int i = 1; i <= n; ++i) {
        int tmp, op;
        scanf("%s%d", s, &tmp);
        if (s[0] == 'A') op = 0;
        else if (s[0] == 'O') op = 1;
        else op = 2;
        for (rg int j = 0; j < BITS; ++j)
            a[j][i] = x[op][bit(tmp, j)];
    }
    for (rg int i = 0; i < BITS; ++i)
        build(i, 1, 1, n);
    while (m--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int tmp; scanf("%d", &tmp);
            int res = 0;
            for (rg int i = 0; i < BITS; ++i)
                res |= p[t[i][1]][bit(tmp, i)] << i;
            printf("%d\n", res);
        } else {
            int pos, tmp;
            scanf("%d%s%d", &pos, s, &tmp);
            if (s[0] == 'A') op = 0;
            else if (s[0] == 'O') op = 1;
            else op = 2;
            for (rg int i = 0; i < BITS; ++i)
                update(i, 1, 1, n, pos, x[op][bit(tmp, i)]);
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}