把离线区间逆序对的代码魔改一下就过了 \(QAQ\)
不过这里 \(pre,suf\) 两个数组可以在询问中求出,不需要提前求出。
此题不卡常,好评、
\(Code\ Below:\)
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=100000+10;
const int lim=16383;
int n,m,k,blo,a[maxn],b[maxn],c[maxn],cnt[maxn],tot;
int pos[maxn],bL[maxn],bR[maxn];ll pre[maxn],suf[maxn],ans[maxn],out[maxn];
namespace IO{
#define gc() (iS==iT?(iT=(iS=ibuff)+fread(ibuff,1,SIZ,stdin),(iS==iT?EOF:*iS++)):*iS++)
const int SIZ=1<<21|1;
char *iS,*iT,ibuff[SIZ],obuff[SIZ],*oS=obuff,*oT=oS+SIZ-1,fu[110],c;int fr;
inline void out(){
fwrite(obuff,1,oS-obuff,stdout);
oS=obuff;
}
template <class T>
inline void read(T &x){
x=0;T y=1;
for(c=gc();(c>'9'||c<'0')&&c!='-';c=gc());
c=='-'?y=-1:x=(c&15);
for(c=gc();c>='0'&&c<='9';c=gc()) x=x*10+(c&15);
x*=y;
}
template <class T>
inline void print(T x,char text='\n'){
if(x<0) *oS++='-',x*=-1;
if(x==0) *oS++='0';
while(x) fu[++fr]=x%10+'0',x/=10;
while(fr) *oS++=fu[fr--];
*oS++=text;out();
}
}
struct Query{
int l,r,v,id;
}q[maxn];
vector<Query> L[maxn],R[maxn];
inline bool cmp(const Query &a,const Query &b){
if((a.l-1)/blo!=(b.l-1)/blo) return (a.l-1)/blo<(b.l-1)/blo;
return a.r<b.r;
}
int main()
{
IO::read(n),IO::read(m),IO::read(k);blo=sqrt(n)+1;
for(int i=1;i<=n;i++) IO::read(a[i]);
for(int i=1;i<=m;i++) IO::read(q[i].l),IO::read(q[i].r),q[i].id=i;
sort(q+1,q+m+1,cmp);q[0].l=1;
for(int i=1;i<=m;i++){
if(q[i-1].r<q[i].r) L[q[i-1].l-1].push_back((Query){q[i-1].r+1,q[i].r,-1,i});
if(q[i].r<q[i-1].r) L[q[i-1].l-1].push_back((Query){q[i].r+1,q[i-1].r,1,i});
if(q[i].l<q[i-1].l) R[q[i].r+1].push_back((Query){q[i].l,q[i-1].l-1,-1,i});
if(q[i-1].l<q[i].l) R[q[i].r+1].push_back((Query){q[i-1].l,q[i].l-1,1,i});
}
for(int i=0;i<=lim;i++){
cnt[i]=cnt[i>>1]+(i&1);
if(cnt[i]==k) b[++tot]=i;
}
for(int i=1;i<=lim;i++){
pos[i]=(i-1)/blo+1;
if(pos[i]!=pos[i-1]) bL[pos[i]]=i,bR[pos[i-1]]=i-1;
}
bR[pos[lim]]=lim;
int sum,l,r,v,id;
for(int i=1;i<=n;i++){
for(int j=1;j<=tot;j++) c[a[i]^b[j]]++;
if(i<n) pre[i+1]=c[a[i+1]];
for(int j=0,siz=L[i].size();j<siz;j++){
l=L[i][j].l;r=L[i][j].r;v=L[i][j].v;id=L[i][j].id;sum=0;
for(int k=l;k<=r;k++) sum+=c[a[k]];
ans[id]+=v*sum;
}
}
memset(c,0,sizeof(c));
for(int i=n;i>=1;i--){
for(int j=1;j<=tot;j++) c[a[i]^b[j]]++;
if(i>1) suf[i-1]=c[a[i-1]];
for(int j=0,siz=R[i].size();j<siz;j++){
l=R[i][j].l;r=R[i][j].r;v=R[i][j].v;id=R[i][j].id;sum=0;
for(int k=l;k<=r;k++) sum+=c[a[k]];
ans[id]+=v*sum;
}
}
for(int i=1;i<=n;i++) pre[i]+=pre[i-1];
for(int i=n;i>=1;i--) suf[i]+=suf[i+1];
for(int i=1;i<=n;i++) ans[i]+=pre[q[i].r]-pre[q[i-1].r]+suf[q[i].l]-suf[q[i-1].l];
for(int i=1;i<=m;i++) ans[i]+=ans[i-1],out[q[i].id]=ans[i];
for(int i=1;i<=m;i++) IO::print(out[i]);
return 0;
}