【BZOJ4750】密码安全

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

题解：感觉这个套路还是比较常见的，即我们讨论每个数作为最大值时的贡献。可以用单调栈或笛卡尔树（类似于启发式合并）实现。

先求出每个数左边第一个比它大的数ls和右边第一个大于等于它的数rs（这个去重套路很常见了），然后我们只需要统计左端点∈(ls,i]，右端点∈[i,rs)的区间即可。具体如何处理？拆位，然后对于每一位都维护一个前缀和即可。

#include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const ll P=1000000061;const int maxn=100010;ll ans;int n,top;int st[maxn],ls[maxn],rs[maxn],s[2][31][maxn],v[maxn],pre[maxn];inline int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();	return ret*f;}void work(){	n=rd(),ans=0;	int i,j;	for(i=1;i<=n;i++)	v[i]=rd(),pre[i]=v[i]^pre[i-1];	for(j=0;j<=n;j++)	for(i=0;i<30;i++)		s[0][i][j]=(!j)?0:s[0][i][j-1],s[1][i][j]=(!j)?0:s[1][i][j-1],s[(pre[j]>>i)&1][i][j]++;	for(top=0,i=1;i<=n;i++)	{		while(top&&v[st[top]]