题目见上。
有一个套路（虽然我到现在还不会），就是固定一个端点，二分查右端点。
显然这题的正解是O(nlogn)的，那么这个套路没准好用。
考虑固定了左端点，因为每次区间gcd都要比上一个区间gcd/2或不变，能够证明一共有O(log)种取值。
而或同理，每次在一个进制位上+1，同样有O(log)种取值。
因此我们二分求出每块gcd值相等的块，然后再求出每块或值相等的块，按照题目要求取个或就行了，可以st表维护，为O(nlog^2)的复杂度。
这个多出来的log是因为我们对于log gcd块内每次log或块，自然变慢，考虑能不能后来的块继承前面的块的信息。
当然可以，于是你就有了下面的正解（代码很好读我就不写解释了），到这篇博客写完为止，开O2 rk1.
#include#include #include #include #include #include #include #include using namespace std;typedef long long ll;const int N=5e5+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct range{ int l,r,v;}g[N],o[N];int n,k,a[N],mp[4*N];inline int gcd(int a,int b){ return b?gcd(b,a%b):a;}inline void merge(range t[],int &l){ int len=0; for(int i=1;i<=l;i++){ if(!len||t[len].v!=t[i].v)t[++len]=t[i]; else t[len].l=t[i].l; } l=len;}int main(){ n=read(),k=read(); for(int i=1;i<=n;i++)a[i]=read(); ll sum=0;int r1=0,r2=0; for(int i=n;i>=1;i--){ for(int j=1;j<=r1;j++)g[j].v=gcd(g[j].v,a[i]); for(int j=1;j<=r2;j++)o[j].v=o[j].v|a[i]; g[++r1]=(range){i,i,a[i]};o[++r2]=(range){i,i,a[i]}; merge(g,r1);merge(o,r2); for(int j=1;j<=r2;j++)mp[o[j].v]=j; for(int j=1;j<=r1;j++){ int p=mp[g[j].v^k]; if(!p)continue; int l=g[j].l,r=g[j].r; l=max(l,o[p].l),r=min(r,o[p].r); if(l<=r)sum+=r-l+1; } for(int j=1;j<=r2;j++)mp[o[j].v]=0; } printf("%lld\n",sum); return 0;}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：+
+++++++++++++++++++++++++++++++++++++++++++