这玩意儿是听shadowice说的,好像很厉害的样子
我们维护出区间&,区间|,区间最大值
结论:如果一次操作对区间& 和 区间| 产生的影响是相同的,那么该操作对整个区间的影响都是相同的
证明可以看这里
然后就做完了。。
时间复杂度$O(nklogn)$,$k$是二进制位数,这里是20
#include<cstdio>
#include<algorithm>
#define ull unsigned long long
#define LL long long
// #define int long long
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
const int MAXN = 2 * 1e6 + 10, INF = 1e9 + 7, mod = 998244353;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M;
int a[MAXN];
struct Node {
int l, r, A, O, Mx, f;
}T[MAXN];
void update(int k) {
T[k].A = T[ls].A & T[rs].A;
T[k].O = T[ls].O | T[rs].O;
T[k].Mx = max(T[ls].Mx, T[rs].Mx);
}
void ps(int k, int val) {
T[k].f += val; T[k].A += val; T[k].O += val; T[k].Mx += val;
}
void pushdown(int k) {
if(!T[k].f) return ;
ps(ls, T[k].f); ps(rs, T[k].f);
T[k].f = 0;
}
void Build(int k, int ll, int rr) {
T[k] = (Node) {ll, rr};
if(ll == rr) {T[k].A = T[k].O = T[k].Mx = a[ll]; return ;}
int mid = ll + rr >> 1;
Build(ls, ll, mid); Build(rs, mid + 1, rr);
update(k);
}
void IntAnd(int k, int ll, int rr, int val) {
if((T[k].O & val) == T[k].O) return ;//notice
if((ll <= T[k].l) && (T[k].r <= rr) && ((T[k].A & val) - T[k].A == (T[k].O & val) - T[k].O)) {
ps(k, (T[k].A & val) - T[k].A); return ;
}
pushdown(k);
int mid = T[k].l + T[k].r >> 1;
if(ll <= mid) IntAnd(ls, ll, rr, val);
if(rr > mid) IntAnd(rs, ll, rr, val);
update(k);
}
void IntOr(int k, int ll, int rr, int val) {
if((T[k].A | val) == T[k].A) return ;
if(ll <= T[k].l && T[k].r <= rr && ((T[k].A | val) - T[k].A == (T[k].O | val) - T[k].O)) {
ps(k, (T[k].O | val) - T[k].O); return ;
}
pushdown(k);
int mid = T[k].l + T[k].r >> 1;
if(ll <= mid) IntOr(ls, ll, rr, val);
if(rr > mid) IntOr(rs, ll, rr, val);
update(k);
}
int Query(int k, int ll, int rr) {
int ans = 0;
if(ll <= T[k].l && T[k].r <= rr) return T[k].Mx;
pushdown(k);
int mid = T[k].l + T[k].r >> 1;
if(ll <= mid) ans = Query(ls, ll, rr);
if(rr > mid) ans = max(ans, Query(rs, ll, rr));
return ans;
}
main() {
N = read(); M = read();
for(int i = 1; i <= N; i++) a[i] = read();
Build(1, 1, N);
while(M--) {
int opt = read(), l = read(), r = read();
if(opt == 1) {
int x = read();
IntAnd(1, l, r, x);
} else if(opt == 2) {
int x = read();
IntOr(1, l, r, x);
} else printf("%d\n", Query(1, l, r));
}
return 0;
}
/*
3 2
7 11
1 5
3 8
4
7
*/