51nod 1674 区间的价值V2(思维+拆位+尺取法)

最近被四区题暴虐。。。

题意:lyk拥有一个区间。

它规定一个区间的价值为这个区间中所有数and起来的值与这个区间所有数or起来的值的乘积。

例如3个数2,3,6。它们and起来的值为2，or起来的值为7，这个区间对答案的贡献为2*7=14。

现在lyk有一个n个数的序列，它想知道所有n*(n+1)/2个区间的贡献的和对1000000007取模后的结果是多少。

区间的and值和区间的or值相乘，实际上等于将and值分解为2的幂次和的形式与or值分解成2的幂次和的形式相乘。

所以对于同一段区间来说，是可以按位来统计的。

首先将数列按位分解成32个位数列。

枚举区间的左端点，,区间的and值要对答案有贡献必须为1，随着右端点右移，and值为不递增的，而区间的or值要对答案有贡献必须为1，随着右端点右移，or值为不递减的。

找到这两个满足条件的最大区间的交集，即可统计出这段区间对答案的贡献。

先用尺取法进行预处理，再依此统计答案。

时间复杂度O(n*loga*loga)。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <bitset>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

inline int Scan() {

    int x=,f=; char ch=getchar();

    while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}

    return x*f;

}

inline void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int R[][N], L[][N], n, mod[];

LL ans;

bool wei[][N];

void init(){

    mod[]=; FOR(i,,) mod[i]=(mod[i-]<<)%MOD;

    FO(i,,) {

        int l=, r=;

        while (l<=n) {

            if (!wei[i][l]) L[i][l]=;

            else {

                r=max(r,l);

                while (r<n&&wei[i][r+]) ++r;

                L[i][l]=r;

            }

            ++l;

        }

    }

    FO(i,,) {

        int l=, r=;

        while (l<=n) {

            if (wei[i][l]) R[i][l]=l;

            else {

                r=max(l,r);

                while (r<=n&&!wei[i][r]) ++r;

                R[i][l]=r;

            }

            ++l;

        }

    }

}

void sol(){

    FO(i,,) FOR(j,,n) {

        if (!wei[i][j]) continue;

        FO(k,,) {

            if (R[k][j]>L[i][j]) continue;

            ans=(ans+(LL)(L[i][j]-R[k][j]+)*mod[i+k])%MOD;

        }

    }

}

int main ()

{

    int x;

    n=Scan();

    FOR(i,,n) {

        x=Scan();

        FO(j,,) wei[j][i]=x%, x/=;

    }

    init();

    sol();

    printf("%lld\n",ans);

    return ;

}

巴特西

51nod 1674 区间的价值V2(思维+拆位+尺取法)

最新文章

热门文章