題目鏈接

題目大意

給出N個數(shù)(N<=10^5)世分，定義區(qū)間[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的區(qū)間的價值總和猖闪。答案對 10^9+7 取模鲜棠。

解答

固定一個左端點L，由于所有數(shù)都是10^9以內(nèi)的培慌，所以在包含同一個左端點L的情況下豁陆，所有的[L,Ri] (L<=Ri<=N)區(qū)間最多只有l(wèi)og(10^9)個不同的or值和and值。所以我們只要枚舉L吵护，二分下一個不同的or值和and值( 下稱為變化點 )盒音，每次找最近的變化點求解，上一個變化點到下一個變化點的or值和and值都是一樣的馅而，變化點最多有2×log(10^9)個祥诽。
對于求解區(qū)間的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;
}