题意
题目链接
sol
这玩意儿是听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("%dn", query(1, l, r)); } return 0; } /* 3 2 7 11 1 5 3 8 4 7 */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/608137.html