LINK：模板莫队二次离线
很早以前学的知识点 不过 很久了忘了。
考虑暴力 :每次莫队更新的时候 尝试更新一个点到一个区间的答案 可以枚举二进制下位数为k的数字 看一下区间内的这种数字有多少个。
不过这样每次移动的复杂度为 C(14,k)的。
考虑 将每次移动操作进行离线 答案进行差分。
那么只需要求出指针移动的变换量即可 由于左端点和右端点的变换量都是nsqrt(n)的
如果直接开空间这么存 空间复杂度nsqrt(n).吃不消。
考虑将一个f(L,[L+1,R])的这种形式的贡献进行前后差分 f(L,1~R)-f(L,[1,L-1]).
这样每次存的都是连续的一堆 离线下来的东西也可以前缀和的时候做 前一步nsqrt(n)。
后一步进行扫描线 nk+nsqrt(n).
很妙的算法。
const int MAXN=100010;
int n,m,k,B,maxx;
int a[MAXN],sum[MAXN],pre[MAXN],v[MAXN];ll ans[MAXN],cc[MAXN];
struct wy{int l,r,id;}t[MAXN];
vector<wy>g[MAXN];
vector<int>p;
inline int cmp(wy a,wy b){return v[a.l]==v[b.l]?a.r<b.r:a.l<b.l;}
int main()
{
freopen("1.in","r",stdin);
get(n);get(m);get(k);
if(k>14)
{
rep(1,m,i)puts("0");
return 0;
}
maxx=16383;
rep(0,maxx,i)
{
sum[i]=sum[i>>1]+(i&1);
if(sum[i]==k)p.pb(i);
}
rep(0,maxx,i)sum[i]=0;
B=(int)sqrt(n*1.0);
rep(1,n,i)
{
get(a[i]);v[i]=(i-1)/B+1;
pre[i-1]=sum[a[i]];
vep(0,p.size(),j)++sum[a[i]^p[j]];
}
rep(1,m,i)t[i]=(wy){read(),read(),i};
sort(t+1,t+1+m,cmp);
int L=1,R=0;
rep(1,m,i)
{
if(L<t[i].l)g[R].pb((wy){L,t[i].l-1,-i});
while(L<t[i].l){ans[i]+=pre[L-1];++L;}
if(L>t[i].l)g[R].pb((wy){t[i].l,L-1,i});
while(L>t[i].l){--L;ans[i]-=pre[L-1];}
if(R<t[i].r)g[L-1].pb((wy){R+1,t[i].r,-i});
while(R<t[i].r){ans[i]+=pre[R];++R;}
if(R>t[i].r)g[L-1].pb((wy){t[i].r+1,R,i});
while(R>t[i].r){ans[i]-=pre[R-1];--R;}
}
rep(0,maxx,i)sum[i]=0;
rep(1,n,i)
{
vep(0,p.size(),j)++sum[a[i]^p[j]];
vep(0,g[i].size(),j)
{
int l=g[i][j].l;int r=g[i][j].r;
int id=g[i][j].id;
rep(l,r,w)
{
int ww=sum[a[w]];
if(k==0&&w<=i)--ww;
if(id<0)ans[-id]-=ww;
else ans[id]+=ww;
}
}
}
rep(1,m,i)ans[i]+=ans[i-1],cc[t[i].id]=ans[i];
rep(1,m,i)putl(cc[i]);
return 0;
}