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

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

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

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

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

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

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

题目思路

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

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

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

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

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

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

• 对于答案的计算，直接双指针扫一遍，枚举在带合并的两个区间内分别枚举 L , R L, R L,R，然后计算符合条件的 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 = 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 > 1; Info ans;
        if(mid >= L) ans = ans + query(lson, L, R);
        if(mid