c/c++语言开发共享BZOJ5312: 冒险(势能均摊线段树)

#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  */