BZOJ5312: 冒险(势能均摊线段树)

题意

题目链接

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("%d\n", query(1, l, r));
    }
    return 0;
}
/*
3 2
7 11
1 5
3 8
4
7
*/