正題

---

題目大意

序列$a$
求有多少個數$(x,y)$對滿足:
$x<y$和$a_{x}or{a}_{x+1}or{a}_{x+2}...or{a}_y<m$

---

解題思路

首先對于每個y，x滿足單調性。
如果$(x,y)$可以那么$(x+1,y)$也可以，所以我們可以枚舉$y$，然后維護$x$指針，如果不滿足條件就將$x$移動到滿足條件為止。
時間復雜度$O(nlo{g}^{2}m)$

---

$code$

#include<cstdio> #define N 100010 #define W 32 #define ll long long using namespace std; ll n,m,a[N],v[W],last,ans; int main() {freopen("evolve.in","r",stdin);freopen("evolve.out","w",stdout);scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);last=1;for(ll i=1;i<=n;i++){ll z=0;for(ll j=0;j<=30;j++)//加入新的v[j]+=(a[i]>>j)&1,z+=(v[j]!=0)<<j;while(z>=m&&last<i)//移動x{z=0;for(ll j=0;j<=30;j++)//去掉 v[j]-=(a[last]>>j)&1,z+=(v[j]!=0)<<j;last++;}ans+=i-last;//if(i!=last)//printf("%lld-%lld\n",last,i);}printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的jzoj3518-进化序列(evolve)【位运算】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。