「雅礼集训 2018 Day7」A

$\text{link}$

用线段树维护 $\text{And,Or,Min}$ 值，对于操作：

• $\text{And x}$，设当前点为 $u$，区间值分别为 $ta(u),to(u),tm(u)$：

  • 若 $x \And to(u) = to(u)$ ,则该操作对当前区间 $[l(u),r(u)]$ 的值无效；

  • 若 $to(u) \And x = ta(u) \And x$ ,则该操作对当前区间的每个数影响都是一样的，可以打懒标记维护；

  • 否则直接暴力递归下去。

• $\text{Or x}$，类似的有：

  • 若 $ta(u) \And x = x$ ,则该操作对当前区间无效；

  • 若 $to(u) \And x = ta(u) \And x$ ,则该操作对当前区间的每个数影响都是一样的，可以打懒标记维护；

  • 否则直接暴力递归下去。

分析一下时间复杂度：每次暴力递归下去都会使得当前区间内所有数的某一位相同，每个区间不同位的总数为 $\mathrm{O(n\log n\log 值域)}$，时间复杂度即为 $\mathrm{O(n\log n\log 值域)}$ 。

$\text{Code:}$

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0, f = 0; char c = getchar();
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 5e5 + 5;
int n, q, a[maxn];
namespace _Smt {
    struct Node {
        int a, o, m, tg1, tg2;
        void aladd(int x) {a &= x; o &= x; m &= x; tg1 = ~tg1 ? tg1 & x : x; tg2 &= x;}
        void oladd(int x) {a |= x; o |= x; m |= x; tg2 |= x; tg1 = ~tg1 ? tg1 ^ (tg1 & x) : tg1;}
    } t[maxn << 2];
    #define ls u << 1
    #define rs u << 1 | 1
    void up(int u) {
        t[u].a = t[ls].a & t[rs].a;
        t[u].o = t[ls].o | t[rs].o;
        t[u].m = min(t[ls].m, t[rs].m);
    }
    void pd(int u) {
        if (~t[u].tg1) t[ls].aladd(t[u].tg1), t[rs].aladd(t[u].tg1);
        if (t[u].tg2) t[ls].oladd(t[u].tg2), t[rs].oladd(t[u].tg2);
        t[u].tg1 = -1; t[u].tg2 = 0;
    }
    void build(int u, int l, int r) {
        t[u].tg1 = -1;
        if (l == r) {
            t[u].a = t[u].o = t[u].m = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        up(u);
    }
    void mdf1(int u, int l, int r, int x, int y, int z) {
        if ((z & t[u].o) == t[u].o) return;
        if (l ^ r) pd(u);
        if (x <= l && r <= y) {
            if (l == r) {
                t[u].aladd(z);
                return;
            } else if ((t[u].o & z) == (t[u].a & z)) {
                t[u].aladd(z);
                return;
            }
        }
        int mid = (l + r) >> 1;
        if (x <= mid) mdf1(ls, l, mid, x, y, z);
        if (y > mid) mdf1(rs, mid + 1, r, x, y, z);
        up(u);
    }
    void mdf2(int u, int l, int r, int x, int y, int z) {
        if ((t[u].a & z) == z) return;
        if (l ^ r) pd(u);
        if (x <= l && r <= y) {
            if (l == r) {
                t[u].oladd(z);
                return;
            } else if ((t[u].o & z) == (t[u].a & z)) {
                t[u].oladd(z);
                return;
            }
        }
        int mid = (l + r) >> 1;
        if (x <= mid) mdf2(ls, l, mid, x, y, z);
        if (y > mid) mdf2(rs, mid + 1, r, x, y, z);
        up(u);
    }
    int qry(int u, int l, int r, int x, int y) {
        if (x <= l && r <= y) return t[u].m;
        int mid = (l + r) >> 1;
        pd(u);
        if (x > mid) return qry(rs, mid + 1, r, x, y);
        if (y <= mid) return qry(ls, l, mid, x, y);
        return min(qry(ls, l, mid, x, y), qry(rs, mid + 1, r, x, y));
    }
}
using namespace _Smt;
int main() {
    n = read(); q = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    build(1, 1, n);
    while (q--) {
        int opt, l, r, x;
        opt = read(); l = read(); r = read();
        if (opt == 1) {
            x = read();
            mdf1(1, 1, n, l, r, x);
        }
        if (opt == 2) {
            x = read();
            mdf2(1, 1, n, l, r, x);
        }
        if (opt == 3) {
            printf("%d\n", qry(1, 1, n, l, r));
        }
    }
    return 0;
}