【and or分块】51Nod1674[区间的价值 V2]题解

题目概述

给出一个序列 {An} ，求 ∑ni=1∑nj=iand(ai,ai+1,⋯,aj)∗or(ai,aI+1,⋯,aj) 。

解题报告

要了解裸题的做法，这道题是and or分块的裸题，对于任意一个点 i ，有下面的结论：

定义And(i,j)=and(ai,ai+1,⋯,aj)，对于所有 j ，将And(i,j)去重之后只会剩下 log2n 个。

定义 Or(i,j)=or(ai,ai+1,⋯,aj) ，对于所有 j ，将Or(i,j)去重之后只会剩下 log2n 个。

由于and（单调递减）和or（单调递增）的单调性，上述结论其实很显然。

对于 i ，我们维护若干个块(a,b,len)表示 And(i,j)=a,Or(i,j)=b 且长度为 len ，那么对于 i−1 ，只需要从 i 的块推过来并去重就行了。

由于只有2log2n个块（and块和or块夹在一起所以是 2 <script type="math/tex" id="MathJax-Element-21">2</script> 倍），所以暴力搞就行了。

示例程序

#include<cstdio>#include<algorithm>using namespace std;const int maxn=100000,Log=17,MOD=1e9+7;typedef long long LL;int n,a[maxn+5],ans,blk;struct data {int a,b,len;};data b[2*Log+5];inline void AMOD(int &x,int tem) {x+=tem;if (x>=MOD) x-=MOD;}inline void Work(int ID){b[++blk]=(data){a[ID],a[ID],1};for (int i=1;i<=blk;i++) b[i].a&=a[ID],b[i].b|=a[ID];int now=blk;blk=1;for (int i=2;i<=now;i++) if (b[i].a==b[blk].a&&b[i].b==b[blk].b) b[blk].len+=b[i].len; elseb[++blk]=b[i];for (int i=1;i<=blk;i++) AMOD(ans,(LL)b[i].a*b[i].b%MOD*b[i].len%MOD);}int main(){freopen("program.in","r",stdin);freopen("program.out","w",stdout);scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=n;i>=1;i--) Work(i);return printf("%d\n",ans),0;}