C116 莫队二次离线 P4887 莫队二次离线

// 莫队二次离线 O(n*sqrt(n)+n*C(k,14))
#include<bits/stdc++.h>
using namespace std;

const int N=100005;
int n,m,k,B,block[N],a[N],t[N],pre[N];
long long ans[N];
vector<int> b;  //二进制中1的个数为k的数
struct F{
  int id,l,r,z;
};
vector<F> f[N]; //待求贡献的信息
struct Q{
  int id,l,r;
  long long ans;
  friend bool operator<(const Q &x, const Q &y) {
    if(block[x.l]!=block[y.l]) return block[x.l]<block[y.l];
    return x.r<y.r;
  }
}q[N];

int count(int x){ //x的二进制中1的个数
  int s=0;
  while(x) s+=x&1,x>>=1;
  return s;
}
int main(){
  scanf("%d%d%d",&n,&m,&k); B=sqrt(n);
  for(int i=1;i<=n;i++)
    scanf("%d",a+i),block[i]=(i-1)/B+1;
  for(int i=1,l,r;i<=m;i++)
    scanf("%d%d",&l,&r),q[i]={i,l,r};
  sort(q+1,q+m+1);
  for(int i=0;i<1<<14;++i)
    if(count(i)==k)b.push_back(i); //最多C(7,14)=3432
  for(int i=1;i<=n;i++){
    pre[i]=t[a[i]];//a1~a[i-1]与ai异或有k个1的数的个数
    for(auto x:b) ++t[a[i]^x];
  }
  for(int i=1,l=1,r=0;i<=m;i++){ //莫队
    //r右移:f(l,x-1)=f(1,x-1)-f(1,l-1), x~[r+1,qr]
    if(r<q[i].r) f[l-1].push_back({i,r+1,q[i].r,-1});
    while(r<q[i].r) q[i].ans+=pre[++r];
    //r左移:-f(l,x-1)=-(f(1,x-1)-f(1,l-1)), x~[qr+1,r]
    if(r>q[i].r) f[l-1].push_back({i,q[i].r+1,r,1});
    while(r>q[i].r) q[i].ans-=pre[r--];
    //l左移:f(x+1,r)=f(1,r)-f(1,x), x~[ql,l-1]
    if(l>q[i].l) f[r].push_back({i,q[i].l,l-1,1});
    while(l>q[i].l) q[i].ans-=pre[--l]+!k;
    //l右移:-f(x+1,r)=-(f(1,r)-f(1,x)), x~[l,ql-1]
    if(l<q[i].l) f[r].push_back({i,l,q[i].l-1,-1});
    while(l<q[i].l) q[i].ans+=pre[l++]+!k;
  }
  //二次离线，累计f(1,l-1)和f(1,r)的贡献
  memset(t,0,sizeof(t));
  for(int i=1,id,l,r,z;i<=n;i++){ //扫描ai
    for(auto& x:b) ++t[a[i]^x];   //与ai配对的数均+1
    for(auto& y:f[i]){            //以ai为边界的f
      for(int x=y.l;x<=y.r;x++)
        q[y.id].ans+=y.z*t[a[x]]; //累计配对贡献
    }
  }
  //后一个查询是前一个查询的增量，故求前缀和
  for(int i=2;i<=m;i++)q[i].ans+=q[i-1].ans;
  for(int i=1;i<=m;i++)ans[q[i].id]=q[i].ans;
  for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
  return 0;
}

C116 莫队二次离线 P4887 莫队二次离线

// 莫队二次离线 O(n*sqrt(n)+n*C(k,14))
#include<bits/stdc++.h>
using namespace std;

const int N=100005;
int n,m,k,B,block[N],a[N],t[N],pre[N];
long long ans[N];
vector<int> b;  //二进制中1的个数为k的数
struct F{
  int id,l,r,z;
};
vector<F> f[N]; //待求贡献的信息
struct Q{
  int id,l,r;
  long long ans;
  friend bool operator<(const Q &x, const Q &y) {
    if(block[x.l]!=block[y.l]) return block[x.l]<block[y.l];
    return x.r<y.r;
  }
}q[N];

int count(int x){ //x的二进制中1的个数
  int s=0;
  while(x) s+=x&1,x>>=1;
  return s;
}
int main(){
  scanf("%d%d%d",&n,&m,&k); B=sqrt(n);
  for(int i=1;i<=n;i++)
    scanf("%d",a+i),block[i]=(i-1)/B+1;
  for(int i=1,l,r;i<=m;i++)
    scanf("%d%d",&l,&r),q[i]={i,l,r};
  sort(q+1,q+m+1);
  for(int i=0;i<1<<14;++i)
    if(count(i)==k)b.push_back(i); //最多C(7,14)=3432
  for(int i=1;i<=n;i++){
    pre[i]=t[a[i]];//a1~a[i-1]与ai异或有k个1的数的个数
    for(auto x:b) ++t[a[i]^x];
  }
  for(int i=1,l=1,r=0;i<=m;i++){ //莫队
    //r右移:f(l,x-1)=f(1,x-1)-f(1,l-1), x~[r+1,qr]
    if(r<q[i].r) f[l-1].push_back({i,r+1,q[i].r,-1});
    while(r<q[i].r) q[i].ans+=pre[++r];
    //r左移:-f(l,x-1)=-(f(1,x-1)-f(1,l-1)), x~[qr+1,r]
    if(r>q[i].r) f[l-1].push_back({i,q[i].r+1,r,1});
    while(r>q[i].r) q[i].ans-=pre[r--];
    //l左移:f(x+1,r)=f(1,r)-f(1,x), x~[ql,l-1]
    if(l>q[i].l) f[r].push_back({i,q[i].l,l-1,1});
    while(l>q[i].l) q[i].ans-=pre[--l]+!k;
    //l右移:-f(x+1,r)=-(f(1,r)-f(1,x)), x~[l,ql-1]
    if(l<q[i].l) f[r].push_back({i,l,q[i].l-1,-1});
    while(l<q[i].l) q[i].ans+=pre[l++]+!k;
  }
  //二次离线，累计f(1,l-1)和f(1,r)的贡献
  memset(t,0,sizeof(t));
  for(int i=1,id,l,r,z;i<=n;i++){ //扫描ai
    for(auto& x:b) ++t[a[i]^x];   //与ai配对的数均+1
    for(auto& y:f[i]){            //以ai为边界的f
      for(int x=y.l;x<=y.r;x++)
        q[y.id].ans+=y.z*t[a[x]]; //累计配对贡献
    }
  }
  //后一个查询是前一个查询的增量，故求前缀和
  for(int i=2;i<=m;i++)q[i].ans+=q[i-1].ans;
  for(int i=1;i<=m;i++)ans[q[i].id]=q[i].ans;
  for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
  return 0;
}