51nod 1674 区间的价值V2( 二分+ST表 )

题目链接

题目大意

给出N个数(N<=10^5)，定义区间[L,R]的价值是(A[L] or A[L+1] or ... or A[R]) × (A[L] and A[L+1] and ... and A[R])，1<=A[i]<=10^9，求出所有N*(N+1)/2的区间的价值总和。答案对 10^9+7 取模。

解答

固定一个左端点L，由于所有数都是10^9以内的，所以在包含同一个左端点L的情况下，所有的[L,Ri] (L<=Ri<=N)区间最多只有log(10^9)个不同的or值和and值。所以我们只要枚举L，二分下一个不同的or值和and值( 下称为变化点 )，每次找最近的变化点求解，上一个变化点到下一个变化点的or值和and值都是一样的，变化点最多有2×log(10^9)个。
对于求解区间的or值和and值，我们可以先分别预处理出两个ST表。
时间复杂度是O(N × log(N) × 2log(10^9))。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;

#define bll long long
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define Mem(a,b) memset(a,b,sizeof(a))

const int maxn=100000+100;
const int modd=1000*1000*1000+7;
int N,lowtwo[maxn],st1[20][maxn],st2[20][maxn];
int A[maxn];

void Prepare_ST()
{
    lowtwo[1]=0;
    For(i,2,N) lowtwo[i]=lowtwo[i>>1]+1;
    For(i,1,N) st1[0][i]=st2[0][i]=A[i];
    For(j,1,lowtwo[N])
    {
        For(i,1,N-(1<<j)+1)
        {
            int k=i+(1<<(j-1));
            st1[j][i]=st1[j-1][i] | st1[j-1][k];
            st2[j][i]=st2[j-1][i] & st2[j-1][k];
        }
    }
}

int query1(int x,int y)
{
    int j=lowtwo[y-x+1];
    return (st1[j][x] | st1[j][y-(1<<j)+1]);
}

int query2(int x,int y)
{
    int j=lowtwo[y-x+1];
    return (st2[j][x] & st2[j][y-(1<<j)+1]);
}

int find1(int w,int x,int v)
{
    int le=x,ri=N+1;
    while(le+1<ri)
    {
        int mid=(le+ri)>>1;
        if (query1(w,mid)!=v) ri=mid;
            else le=mid;
    }
    return ri;
}

int find2(int w,int x,int v)
{
    int le=x,ri=N+1;
    while(le+1<ri)
    {
        int mid=(le+ri)>>1;
        if (query2(w,mid)!=v) ri=mid;
            else le=mid;
    }
    return ri;
}

int Done(int w)
{
    int ret=0;
    int orv=A[w],andv=A[w];
    int i=w,j=w;
    int ni=find1(w,i,orv),nj=find2(w,j,andv);
    for (int k=w,nk; k<=N; k=nk)
    {
        nk=min(ni,nj);
        ret=(ret+(bll)(nk-k)*orv %modd *andv %modd) %modd;
        if (nk==ni)
        {
            orv=query1(w,ni);
            i=ni;
            ni=find1(w,i,orv);
        }
        if (nk==nj)
        {
            andv=query2(w,nj);
            j=nj;
            nj=find2(w,j,andv);
        }
    }
    return ret;
}

int main(int argc, char* argv[])
{
    for (; scanf("%d",&N)!=EOF; )
    {
        For(i,1,N) scanf("%d",&A[i]);
        Prepare_ST();
        int ans=0;
        For(i,1,N)
            ans=(ans+Done(i)) %modd;
        printf("%d\n",ans);
    }
    return 0;
}