LINK:模闆莫隊二次離線
很早以前學的知識點 不過 很久了忘了。
考慮暴力 :每次莫隊更新的時候 嘗試更新一個點到一個區間的答案 可以枚舉二進制下位數為k的數字 看一下區間内的這種數字有多少個。
不過這樣每次移動的複雜度為 C(14,k)的。
考慮 将每次移動操作進行離線 答案進行差分。
那麼隻需要求出指針移動的變換量即可 由于左端點和右端點的變換量都是nsqrt(n)的
如果直接開空間這麼存 空間複雜度nsqrt(n).吃不消。
考慮将一個f(L,[L+1,R])的這種形式的貢獻進行前後差分 f(L,1~R)-f(L,[1,L-1]).
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;
}