考虑每个数作为最大值的贡献。
有单调栈求出每个数作为最大值能向左向右扩展的区间,为了避免重复计算,我们让每个区间的最右边的最大值来当最大值计算
对于异或的处理,我们用前缀异或和的异或来表示一个区间的异或
即sum[l...r]=sum[r]^sum[l-1]
异或进行拆位处理,一个区间的异或的第k位为1,就是sum[l-1]和sum[r]的第k位的数字不同
然后细节看代码吧
const int N = 1e5 + 79;
const int mod = 1e9 + 61;
#define int long long
int n;
lxl a[N], sum[N];
int L[N], R[N];
int top, s[N];
int sm[N];
inline lxl calc(int p) {
lxl ans(0);
rep(i, 1, n) {
sm[i] = sm[i - 1] + ( (sum[i] >> p) & 1);
}
rep(i, 1, n) {
lxl l = i - L[i] + 1;
lxl r = R[i] - i + 1;
lxl w = sm[i - 1] - sm[max(0ll, L[i] - 2)];//左边1的个数
lxl t = sm[R[i]] - sm[i - 1];//右边1的个数
ans = (ans + w * (r - t) % mod * a[i]) % mod;//左边1的个数*右边0的个数
ans = (ans + t * (l - w) % mod * a[i]) % mod;//右边1的个数*左边0的个数
}
return ans;
}
main() {
freopen("pwd.in", "r", stdin);
freopen("pwd.out", "w", stdout);
int T(0);
read(T);
while(T--) {
read(n);
rep(i, 1, n) {
read(a[i]);
sum[i] = sum[i - 1] ^ a[i];
}
lxl ans(0);
a[0] = a[n + 1] = 3e9;
s[top = 1] = 0;
rep(i, 1, n) {
while(a[s[top]] < a[i]) {
--top;
}
L[i] = s[top] + 1;
s[++top] = i;
}
s[top = 1] = n + 1;
drp(i, n, 1) {
while(a[s[top]] <= a[i]) {
--top;
}
R[i] = s[top] - 1;
s[++top] = i;
}
rep(i, 0, 60) {
ans = (ans + calc(i) * (1ll << i) % mod) % mod;
}
out(ans, '\n');
}
return 0;
}