题目描述
模10^9+61
输入
第一行包含一个正整数 T ，表示有 T 组测试数据。
接下来依次给出每组测试数据。对于每组测试数据：
第一行包含一个正整数 n 。
第二行包含 n 个非负整数，表示 A_1,A_2,?,A_n 。
保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。
100% 的数据满足：1≤T≤200,1≤n≤10^5,1≤∑n≤10^6,0≤A_i≤10^9
输出
对于每组数据输出一行，包含一个整数，表示答案对10^9+61 取模的值。
样例输入
3
1
61
5
1 2 3 4 5
5
10187 17517 24636 19706 18756
样例输出
3721
148
821283048
题解
单调栈
区间异或和比较容易处理，关键在于区间最大值
考虑一个数作为最大值的贡献：使用单调栈处理出一个数左边第一个大于等于它的数的位置lp和右边第一个大于它的数的位置rp。那么该数的贡献为：左端点[lp[i]+1,i]，右端点[i,rp[i]-1]。
然后再考虑异或和：区间异或和可以由前缀异或来表示。所以满足条件的区间的异或相当于suml在[lp[i],i-1]，sumr在[i,rp[i]-1]的两个数的异或。
我们可以拆位，然后对于前缀异或和的某一位维护前缀1的个数。如果该为异或为1，则说明左边为1，右边为0或左边为0，右边为1。分别把方案数计算出来即可。
注意在计算suml所在区间的前缀相减时lp[i]-1可能为负数，因此需要把数组下标平移1位处理。
#include <cstdio>
#include <cstring>
#define N 100010
#define mod 1000000061
typedef long long ll;
int a[N] , sum[N] , c[N][30] , lp[N] , rp[N] , sta[N] , tot;
int main()
{
int T;
scanf("%d" , &T);
while(T -- )
{
int n , i , j , ans = 0;
scanf("%d" , &n);
memset(c , 0 , sizeof(c));
for(i = 2 ; i <= n + 1 ; i ++ )
{
scanf("%d" , &a[i]) , sum[i] = sum[i - 1] ^ a[i];
for(j = 0 ; j < 30 ; j ++ ) c[i][j] = c[i - 1][j] + (bool)(sum[i] & (1 << j));
}
tot = 0 , sta[0] = 1;
for(i = 2 ; i <= n + 1 ; i ++ )
{
while(tot && a[sta[tot]] < a[i]) tot -- ;
lp[i] = sta[tot] , sta[++tot] = i;
}
tot = 0 , sta[0] = n + 2;
for(i = n + 1 ; i >= 2 ; i -- )
{
while(tot && a[sta[tot]] <= a[i]) tot -- ;
rp[i] = sta[tot] , sta[++tot] = i;
}
for(i = 2 ; i <= n + 1 ; i ++ )
for(j = 0 ; j < 30 ; j ++ )
ans = (ans + ((ll)(c[i - 1][j] - c[lp[i] - 1][j]) * (rp[i] - i - c[rp[i] - 1][j] + c[i - 1][j])
+ (ll)(i - lp[i] - c[i - 1][j] + c[lp[i] - 1][j]) * (c[rp[i] - 1][j] - c[i - 1][j])) % mod
* (1 << j) % mod * a[i]) % mod;
printf("%d
" , ans);
}
return 0;
}