2020 wannafly camp day6 H 异或询问 —— 异或 + 前缀

题目链接：点我啊╭(╯^╰)╮

解题思路：

    如果只考虑${\sum }_{i=1}^{n}f(i)$，也就是一段连续的区间，预处理前缀即可
    而$\sum f(ixorx)$，加上了一个异或后，区间就不连续了
    根据异或性质，会分成最多 $log$ 个连续区间
    从高位到低位考虑，如果 $n$ 的第 $pos$ 位为 $1$，若不考虑 $n$ 的低位
    若 $x$ 的这一位为 $0$ ，则异或后是一段连续的区间:$（0,2^{pos}?1）$
    若 $x$ 的这一位为 $1$ ，则加上这一位，再计算新的区间

    每一位考虑完之后，要加上这一位的影响，再去考虑低位
    最后要清空影响，其实最后的影响就是 $nxorx$ 了

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <int,int>;
const ll mod = 998244353;
const int maxn = 1e5 + 5;
int n, q, a[maxn];
ll pre[maxn];
vector <int> v;ll gao(ll x){if(x < a[1]) return 0;int pos = upper_bound(v.begin(), v.end(), x) - v.begin() - 1;ll ret = pre[pos];if(x == v[pos]) return ret;ll num = upper_bound(a+1, a+1+n, x) - a - 1;ret += 1ll * (x - v[pos]) * num % mod * num % mod;return ret % mod;
}ll query(int l, int r){return (gao(r) - gao(l-1) + mod) % mod;
}ll solve(int n, int x){if(n < 0) return 0;ll ret = 0; int cur = 0;for(int i=30; ~i; i--){int u = x >> i & 1;if(n >> i & 1){ret += query(cur|(u<<i), (cur|(u<<i)) + (1<<i)-1);cur |= ((u ^ 1) << i);} else cur |= (u << i);}ret = (ret + query(cur, cur)) % mod;return ret;
}int main() {scanf("%d%d", &n, &q);for(int i=1; i<=n; i++) scanf("%d", a+i), v.push_back(a[i]);sort(a+1, a+1+n);sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());ll cnt = v.size(), num, lnum;for(int i=0; i<cnt; i++){num = upper_bound(a+1, a+1+n, v[i]) - a - 1;if(i == 0) pre[i] = num * num % mod;else pre[i] = pre[i-1] + num * num % mod + \(v[i] - v[i-1] - 1) * lnum % mod * lnum % mod;pre[i] %= mod;lnum = num;}while(q--){int l, r, x;scanf("%d%d%d", &l, &r, &x);ll ans = solve(r, x) - solve(l-1, x);printf("%lld\n", (ans + mod) % mod);}
}