【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
1
61
5
1 2 3 4 5
5
10187 17517 24636 19706 18756
Sample Output
3721
148
821283048
148
821283048
题解：感觉这个套路还是比较常见的，即我们讨论每个数作为最大值时的贡献。可以用单调栈或笛卡尔树（类似于启发式合并）实现。
先求出每个数左边第一个比它大的数ls和右边第一个大于等于它的数rs（这个去重套路很常见了），然后我们只需要统计左端点∈(ls,i]，右端点∈[i,rs)的区间即可。具体如何处理？拆位，然后对于每一位都维护一个前缀和即可。
#include <cstdio>
#include <cstring>
#include <iostream>
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]]<v[i]) rs[st[top--]]=i-1;
ls[i]=st[top]+1,st[++top]=i;
}
while(top) rs[st[top--]]=n;
for(i=1;i<=n;i++)
{
for(j=0;j<30;j++) ans=(ans+(((ll)(s[1][j][i-1]-((ls[i]==1)?0:s[1][j][ls[i]-2]))*(s[0][j][rs[i]]-s[0][j][i-1])+(ll)(s[0][j][i-1]-((ls[i]==1)?0:s[0][j][ls[i]-2]))*(s[1][j][rs[i]]-s[1][j][i-1]))<<j)%P*v[i])%P;
}
printf("%lld
",ans);
}
int main()
{
int T=rd();
while(T--) work();
return 0;
}//3 1 61 5 1 2 3 4 5 5 10187 17517 24636 19706 18756