题目描述

Description

有些人在社交网络中使用过许多的密码，我们通过将各种形式的信息转化为 01 信号，再转化为整数，可以将这个
人在一段时间内使用过的密码视为一个长度为 n 的非负整数序列 A_1,A_2,...,A_n 。一个人相邻几次在社交网络
中使用的密码很有可能是类似的，这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安
全的影响，我们需要计算上述序列的复杂程度。

的值，这将作为我们评估密码复杂程度的一个部分。由于答案可能很大，你只需要给出答案对10^9+61 取模的值即可。

Input

第一行包含一个正整数 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

Output

对于每组数据输出一行，包含一个整数，表示答案对10^9+61 取模的值。

Sample Input

3
1
61
5
1 2 3 4 5
5
10187 17517 24636 19706 18756

Sample Output

3721
148
821283048

题目分析

应该会想到 先用单调栈处理出每个数为最大值管理的区间
那就好办了 在处理出前缀异或值后 记录 前缀亦或的每一位的1的个数 根据每个区间拆位单独计算答案贡献
但是没这么简单
首先 如果有两个相同的数作为最大值 管理的区间会重 所以我们单调栈处理的区间 左区间是第一个小于等于它的数
然后 注意一段区间的异或值 和 拿出一段区间的每位1的个数 计算方式都是 右端点-(左端点-1)
所以数组要整体平移一位

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int T,n;
long long v[100010],a[100010],sum[100010][50];
int l[100010],r[100010];
int sta[100010];
long long mod=1000000061;
void init()
{
    memset(v,0,sizeof v);
    memset(a,0,sizeof a);
    memset(sum,0,sizeof sum);
}
int tot;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d",&n);
        for(int i=2;i<=n+1;i++) scanf("%lld",&v[i]),a[i]=a[i-1]^v[i];
        for(int i=2;i<=n+1;i++)
            for(int j=0;j<30;j++)
                sum[i][j]=sum[i-1][j]+((a[i]&(1ll<<j))?1:0);
        tot=0,sta[0]=1;
        for(int i=2;i<=n+1;i++)
        {
            while(tot&&v[sta[tot]]<v[i]) tot--;
            l[i]=sta[tot],sta[++tot]=i;
        }
        tot=0,sta[0]=n+2;
        for(int i=n+1;i>=2;i--)
        {
            while(tot&&v[sta[tot]]<=v[i]) tot--;
            r[i]=sta[tot],sta[++tot]=i;
        }     
        long long ans=0;  
        for(int i=2;i<=n+1;i++)
            for(int j=0;j<30;j++)
            {
                long long tmp= (long long) ( sum[i-1][j]-sum[l[i]-1][j] )*( r[i]-i-sum[r[i]-1][j]+sum[i-1][j] )%mod;
                long long nmp= (long long) ( i-l[i]-sum[i-1][j]+sum[l[i]-1][j] )*( sum[r[i]-1][j]-sum[i-1][j] )%mod;
                ans=(ans+(tmp+nmp)%mod*(1ll<<j)%mod*v[i]%mod)%mod;
            }
        printf("%lld\n",ans);
    }
}