线段树 ---- CF1004F Sonya and Bitwise OR（线段树上分治合并区间信息 + or 前缀和的log性质）_在前缀和上的线段树

题目链接

---

题目大意：

---

解题思路：

1. 考虑只有一次询问时怎么做。
   分治。每次考虑$L$位于左半边，$R$位于右半边的情况（也就是“跨过中点”的答案）。再分别递归左、右两边。计算跨过中点的答案时，可以先求出【左半边的$\mathrm{or}$值后缀和】和【右半边的$\mathrm{or}$值前缀和】。然后用two pointers求出满足条件的$(L,R)$数量，
2. 例如，可以枚举$R$，则左半边的$L$可选范围单调增加，也就是从最左边不断向右移。这样，不算递归，每次做two pointers的复杂度都是$O(\text{len})$的，一次询问总复杂度就是$O(\text{len}\log \text{len})$。
3. 分治时的左、右两边，天然就是线段树的左、右节点，这有很多相似之处。但是我们面临的问题是：如果向分治时一样，维护出每个区间的前缀、后缀$\mathrm{or}$和，则一次修改、查询的复杂度，都高达$O(n\log n)$，无法承受。
4. 这里还要一个重要的性质就是前缀$\text{or}$和最多有$\text{log}$个不同的结果！！就是有$\text{log}$个段，每个段里面的值都说一样的，就是共同的位1是一样的,那么合并的时候复杂度就降到$\text{logn}$的复杂度了！！！那么总的复杂度就是$O(nlo{g}^{2}n)$

---

AC code

1. 我们开一个线段树支持区间查询，单点修改
2. 线段树里面有个两个数组分别是前缀或pre和后缀或suf 里面还要记录每个块长度
3. 还要一个统计区间的答案cnt
4. 合并的时候直接合并就好了，每次暴力往外区间延申，是可以直接合并的。例如：假设你要统计前缀$\text{or}$那你就要从左儿子的$\text{pre}$去合并到右儿子的$\text{pre}$,为啥可以直接合并呢？因为对于每个块最左的端的数是包含了这个块内所有位置的1，所以即使你跨边界最先$\text{or}$的还是最左端的数，一旦$\text{or}$这个数，后面的$\text{or}$结果都不会变了

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 500010;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {
   x = 0;char ch = getchar();ll f = 1;
   while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
   while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
   read(first);
   read(args...);
}

struct node {
   ll cnt;
   vector<PII> pre, suf;
}tr[maxn << 2];
int n, m, x;
int arr[maxn];

inline node merge(node a, node b) {
   if(!a.pre.size()) return b;
   if(!b.pre.size()) return a;
   node res;
   res.cnt = a.cnt + b.cnt;
   ll tot = 0;
   for(auto ita : a.suf)
     for(auto itb : b.pre) {
        if((ita.first|itb.first) >= x)
          tot += 1ll * ita.second * itb.second;
     }
   res.cnt += tot;
   res.pre = a.pre;
   ll num = a.pre.back().first;
   for(auto itb : b.pre) {
      if((itb.first|num)==num) res.pre.back().second += itb.second;
      else {
         res.pre.push_back({itb.first|num,itb.second});
         num = num | itb.first;
      }
   }
   res.suf = b.suf;
   ll num1 = b.suf.back().first;
   for(auto ita : a.suf) {
      if((ita.first|num1)==num1) res.suf.back().second += ita.second;
      else {
         res.suf.push_back({ita.first|num1,ita.second});
         num1 = num1 | ita.first;
      }
   }   
   return res;
}

inline void pushup(int rt) {
   tr[rt] = merge(tr[rt<<1],tr[rt<<1|1]);
}

inline void build(int rt, int l, int r) {
   if(l == r) {
      tr[rt].pre.push_back({arr[l],1});
      tr[rt].suf.push_back({arr[l],1});
      tr[rt].cnt = (arr[l] >= x);
      return ;
   }
   build(Lson);
   build(Rson);
   pushup(rt);
}

node query(int rt, int l, int r, int L, int R) {
   if(L <= l && r <= R) return tr[rt];
   if(mid < L) return query(Rson,L,R);
   else if(mid >= R) return query(Lson,L,R);
   else return merge(query(Lson,L,R),query(Rson,L,R));
}

void update(int rt, int l, int r, int pos, int val) {
   if(l == r) {
      tr[rt].pre.back().first = val;
      tr[rt].suf.back().first = val;
      tr[rt].cnt = (val >= x);
      return;
   }
   if(pos <= mid) update(Lson,pos,val);
   else update(Rson,pos,val);
   pushup(rt);
}

int main() {
     IOS;
     cin >> n >> m >> x;
     for(int i = 1; i <= n; ++ i) cin >> arr[i];
     build(1,1,n);
     while(m--) {
        int op;
        cin >> op;
        if(op == 1) {
           int x, y;
           cin >> x >> y;
           update(1,1,n,x,y);
        } else {
           int l, r;
           cin >> l >> r;
           cout << query(1,1,n,l,r).cnt << endl;
        }
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127