27.CF1004F Sonya and Bitwise OR 区间合并线段树

27.CF1004F Sonya and Bitwise OR 区间合并线段树

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定序列，要求支持操作： 1.单点修改 2.查询区间内按位或和至少为X的子区间数

考虑分治。现在需要计算跨越区间中点的左、右端点对数。记录以区间中点为一端的前后缀，搭配双指针就可以 $O(n)$ 计算

洛谷传送门：CF1004F Sonya and Bitwise OR - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：F. Sonya and Bitwise OR (codeforces.com)

题目思路

如果要检查合法性的话，只需要维护$20$棵线段树就能支持。但是本题要求计数，问题就麻烦了。

• 假设只有一个全局询问，考虑分治。现在需要计算跨越区间中点的左、右端点对数。记录以区间中点为一端的前后缀，搭配双指针就可以 $O(n)$ 计算。

我们可以发现，由于或运算的性质，不同的前缀/后缀区间或 至多只有 $\log a$ 种。

• 对于每个区间，我们分别记录前缀、后缀或和及区间答案，上传时分别传递前缀后缀、更新前缀后缀。

• 考虑如何区间合并，我们分别开$vector$记录不同的前后缀或值，在合并左右区间时，对于前缀序列，插入右区间中所有与整个左区间或产生的不同的值，右区间类比这么处理。

• 考虑合并时如何更新答案：计算符合条件的$L,R$对数，我们设置两个指针分别指向左右区间的左区间首和右区间尾，然后对于每个左端点缩右端点，然后暴力计数即可。

• 对于答案的计算，直接双指针扫一遍，枚举在带合并的两个区间内分别枚举$L,R$，然后计算符合条件的$L,R$个数，就能实现两个区间的答案合并。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
int a[N], n, m, x;

namespace ffastIO {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}

using ffastIO::read;

#define pii pair<int, int>

namespace SegTree{
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    #define lson ls, l, mid
    #define rson rs, mid + 1, r

    struct Info{
        vector<pii> pre, suf;
        int ans, pl, pr;
        Info(): ans(0) { pre.clear(), suf.clear(); }
        void clear() { pre.clear(), suf.clear(), ans = 0; }
        void add_pre(int x, int y) { pre.emplace_back(pii{x, y}); }
        void add_suf(int x, int y) { suf.emplace_back(pii{x, y}); }
        Info operator+ (Info b) {
            if(!pre.size()) return b;
            if(!b.pre.size()) return *this;
            Info res;
            res.ans = this -> ans + b.ans;
            res.pre = this -> pre;
            res.pl = pl, res.pr = b.pr;
            for(auto now : b.pre){
                if((pre.back().first | now.first) != res.pre.back().first)
                    res.add_pre(pre.back().first | now.first, now.second);
            }
            res.suf = b.suf;
            for(auto now : suf){
                if((b.suf.back().first | now.first) != res.suf.back().first)
                    res.add_suf(b.suf.back().first | now.first, now.second);
            }
            for(int i = 0, j = b.pre.size() - 1; i < (int)suf.size(); i++){
                while(j >= 0 && (suf[i].first | b.pre[j].first) >= x) j--;
                if(j + 1 < (int)b.pre.size())
                    res.ans += 1ll * (suf[i].second - (i + 1 < (int)suf.size() ? suf[i + 1].second : pl - 1)) * (b.pr - b.pre[j + 1].second + 1);
            }
            return res;
        }
    }tree[N << 2];
    
    void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }

    void build(int rt, int l, int r){
        if(l == r){
            tree[rt].pl = tree[rt].pr = l;
            tree[rt].add_pre(a[l], l);
            tree[rt].add_suf(a[l], l);
            tree[rt].ans = (a[l] >= x);
            return;
        }
        int mid = l + r >> 1;
        build(lson), build(rson);
        push_up(rt);
    }

    void update(int rt, int l, int r, int pos, int val){
        if(l == r){
            tree[rt].clear();
            tree[rt].add_pre(val, pos);
            tree[rt].add_suf(val, pos);
            tree[rt].ans = (val >= x);
            return;
        }
        int mid = l + r >> 1;
        if(mid >= pos) update(lson, pos, val);
        else update(rson, pos, val);
        push_up(rt);
    }

    Info query(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R) return tree[rt];
        int mid = l + r >> 1; Info ans;
        if(mid >= L) ans = ans + query(lson, L, R);
        if(mid < R) ans = ans + query(rson, L, R);
        return ans;
    }

    #undef ls
    #undef rs
    #undef lson
    #undef rson
}

#define SEGRG 1, 1, n

inline void solve(){
    n = read(), m = read(), x = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    SegTree::build(1, 1, n);
    while(m--){
        int op = read(), l = read(), r = read();
        if(op == 1) SegTree::update(SEGRG, l, r);
        else cout << SegTree::query(SEGRG, l, r).ans << endl;
    }
}

signed main(){
    solve();
    return 0;
}
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