%%%%%%%%%%%lst神仙 这是他的做法 吊了标算
对于这种有多少区间满足要求的 我们套路的用分治做 每次都统计左端点在左半边 右端点在右半边的个数
设f(i) 表示当前点到中间分割点的最大值，g(i)表示当前点到中间分割点的或和
我们发现 g(i)≥f(i) 所以只需找到g[i]=f[i]的区间就好
然后f肯定是单调递增的
所以可以维护双指针
边界条件很坏坏 膜lst神仙啊
#include<bits/stdc++.h> #define N 1000005 #define int long long using namespace std; template<class T> inline void read(T &x) { x=0; int f=1; static char ch=getchar(); while((!isdigit(ch))&&ch!='-') ch=getchar(); if(ch=='-') f=-1; while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); x*=f; } int n,s[N],f[N],g[N],ans; inline void solve(int l,int r) { if(l>=r) return; int mid=(l+r)>>1; f[mid]=s[mid],f[mid+1]=s[mid+1]; for(int i=mid-1;i>=l;i--) f[i]=max(s[i],f[i+1]); for(int i=mid+2;i<=r;i++) f[i]=max(s[i],f[i-1]); g[mid]=s[mid],g[mid+1]=s[mid+1]; for(int i=mid-1;i>=l;i--) g[i]=s[i]|g[i+1]; for(int i=mid+2;i<=r;i++) g[i]=s[i]|g[i-1]; int pos=mid; for(int i=mid;i>=l;i--) //左端点 { if(f[i]==g[i]) { while(pos<r&&((g[pos+1]|g[i])==g[i])&&f[pos+1]<=f[i]) pos++; //1.没越界 2.是子集 3.最大值在左边 ans-=pos-mid; } } pos=mid+1; for(int i=mid+1;i<=r;i++) { if(f[i]==g[i]) { while(pos>l&&((g[pos-1]|g[i])==g[i])&&f[pos-1]<f[i]) pos--; ans-=mid-pos+1; } } solve(l,mid); solve(mid+1,r); } main() { read(n); for(int i=1;i<=n;i++) read(s[i]); ans=n*(n-1)/2; solve(1,n); cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9877788.html
相关资源：各显卡算力对照表！