BZOJ-4750: 密码安全

Description

求一个序列所有子区间亦或和与子区间最大值乘积的和。多组数据，T<=200 n<=10^5 <=10^6 Ai<=10^9

对于每个点，单调栈求出其能作为最大值的子区间有哪些。求出区间两端点的范围，将亦或前缀值拆位，统计前缀和计算答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=1000000061;
ll ans;
int n,a[101000],L[101000],R[101000],z[101000],w[101000],sum[101000][30];
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
    x=0; char ch=nc(),f=1;
    while(ch<'0'||ch>'9') {if(ch=='-') f=0; ch=nc();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=nc(); x= f ? x : -x;
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        memset(sum,0,sizeof sum);
        read(n); int now=0; ans=0;
        for(int i=1;i<=n;++i)
        {
            read(a[i]);
            now^=a[i];
            for(int j=0;j<30;++j) sum[i][j]=sum[i-1][j]+((now&(1<<j))?1:0);
        }
        int top=0,i; z[0]=0;
        for(i=1;i<=n;++i)
        {
            while(top&&a[z[top]]<a[i]) top--;
            L[i]=z[top]; z[++top]=i;
        }
        top=0; z[0]=n+1;
        for(i=n;i;--i)
        {
            while(top&&a[z[top]]<=a[i]) top--;
            R[i]=z[top]-1; z[++top]=i;
        }
        ll l1,l0,r1,r0;
        for(int i=1;i<=n;++i)
        {
            for(int j=0;j<30;++j)
            {
                l1=sum[i-1][j]-sum[L[i]-1][j];
                l0=i-L[i]-l1;
                r1=sum[R[i]][j]-sum[i-1][j];
                r0=R[i]-i+1-r1;
                ans=(ans+(ll)a[i]*((l1*r0+l0*r1)%mod)%mod*(1ll<<j)%mod)%mod;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}