莫队二次离线

莫队是一种离线算法，将询问离线，然后对询问按照一定方式排序，然后暴力移动区间下标指针，很多时候可以优化到 $O(n\sqrt{n})$, 但对于某些问题，下标指针移动时，往往涉及统计整个区间信息，复杂度会陡然提升。

这时可以先做一遍莫队，算出易求部分，离线难求部分。对于难求部分，再寻求方法，也就是二次离线处理，这就是莫队二次离线算法的思想。采用分步处理后，时间复杂度就从 $O(n\sqrt{n}*t(k))$ 降为 $O(n\sqrt{n}+n*t(k))$ , $t(k)$ 为指针移动时更新答案的代价。

例：P4887 【模板】莫队二次离线

题意：给定一个长度为 $n$ 的序列 $a$，$m$ 次查询区间 $[l,r]$ 中 $a_i \oplus a_j$ 的二进制表示下有 $k$ 个 $1$ 的二元组 $(i,j)$ 的个数。$\oplus$ 是指按位异或。

$1 \leq n, m \leq 100000$，$0 \leq a_i, k < 16384$

分析：可以先用莫队进行离线讨论：

【1】当 $r<qr$ , $r$ 向 $qr$ 移动时(简称向右移动) ， 设 $\forall x \in (r,qr]$ ， $x$ 从 $x-1$ 移动到 $x$ 位置, 区间 $[l,x-1]$ 与 $a[x]$ 可能有多个符合条件的配对关系。

即使利用计数数组，也要进行 $C_{14}^k$ 次查询，直接计算复杂度爆炸。

此时我们暂记 $f(l,x-1,x)$ 表示区间 $[l,x-1]$ 与 $a[x]$ 配对符合条件的个数，存在一定的前缀可减性，即

$$f[l,x-1,x]=f[1,x-1,x]-f[1,l-1,x]$$

(增加)

其余 $3$ 种情况，我们也可以分析出类似情况。

（1） 对于 $f[1,x-1,x]$ ，简单记作 $pre[x]$ 表示 $a_1 \sim a_{x-1}$ 中与 $a_x$ 的个数。

可以先把 $[0,16384]$ 范围内二进制中含有 $k$ 个 $1$ 数放入 $b$ 数组。 如果 $a_i\oplus a_j=b_k$ , 等价于 $a_i=a_j \oplus b_k$ ,也就是 $a_i$ 与 $a_j$ 配对。 枚举每个 $a_i$ , 用桶数组累计$a_j \oplus b_k$ 的个数，就可以计算出 $pre[x]$.

  memset(t,0,sizeof(t));
  for(int i=0;i<(1<<14);i++)   // 16348=2^(14) 
      if(popcount(i)==k)b.push_back(i);
  
  for(int i=1;i<=n;i++)
  {
      pre[i]=t[a[i]];
      for(int x:b)t[a[i]^x]++;
  }

(2) 莫队第一次离线

【1】 $r$ 右移, $x \in [r+1,qr]$ , 每次移动，增加配对数 ：

$$f[l,x-1,x]=f[1,x-1,x]-f[1,l-1,x]$$

【2】 $r$ 左移，$x \in [qr+1,r]$ , 每减少一个点 $x$ , 减少配对数 ：

$$-f[l,x-1,x]=-f[1,x-1,x]+f[1,l-1,x]$$

【3】 $l$ 左移，$x \in [ql,l-1]$ , 每增加一个点 $x$ ,增加配对数：

$$f[x+1,r,x]=f[1,r,x]-f[1,x,x]$$

注意：对于 $f[1,x,x]$ 当 $k==0$, $x\oplus x$ 符合条件配对数要增加 $1$ ,即特判一下。

【4】 $l$ 右移，$x \in [l,ql-1]$，每减少一个点 $x$,则减少配对数：

$$-f[x+1,r,x]=-f[1,r,x]+f[1,x,x]$$

注意：对于 $f[1,x,x]$ 当 $k==0$, $x \oplus x$ 符合条件配对数要增加 $1$ ,即特判一下。

对于 $f[1,(l-1),x],f[1,r,x]$ ,$x$ 是区间移动，实际就是区间对区间的影响，可以暂时存下来，等待二次离线处理。

Len=sqrt(n);  //块长
sort(q+1,q+m+1,cmp);
for(int i=1,l=1,r=0;i<=m;i++)
{
  //r右移
  if(r<q[i].r)g[l-1].push_back({i,r+1,q[i].r,-1});
  while(r<q[i].r)q[i].ans+=pre[++r];
  //r左移
  if(q[i].r<r)g[l-1].push_back({i,q[i].r+1,r,1});
  while(q[i].r<r)q[i].ans-=pre[r--];
  
  //l左移
  if(q[i].l<l)g[r].push_back({i,q[i].l,l-1,1});
  while(q[i].l<l)q[i].ans-=pre[--l]+!k;
  //l右移
  if(l<q[i].l)g[r].push_back({i,l,q[i].l-1,-1});
  while(l<q[i].l)q[i].ans+=pre[l++]+!k;
}

（3） 二次离线处理

本质就是扫描线累计。

对于【1】中 $f[1,l-1,x]$ 是区间 $[1,l-1]$ 与 $a_x$ 配对的数的个数，扫描 $a_i$ , 每个 $a_i$ 都对与他配对的数贡献 1 次。 扫描 $a_1\sim a_{l-1}$ ，则 $[r+1,qr]$ 区间内与前面配对的数都被贡献了应该的次数，累计配对次数即可。 拥有相同边界的 $f$ 可能有多个，枚举，同理【2】 。

对于【3】 中 $l$ 左移: $x\in [ql,l-1]$

$f[1,r,x]$ 表示 $[1,r]$ 与 $a[x]$ 配对的个数，同理 【4】。

  memset(t,0,sizeof(t));
  //扫描ai 计算 [1,i] 与 [l,r] 符合条件的个数
  for(int i=1; i<=n; i++)
  {
      for(int x:b)t[a[i]^x]++;
  
      for(auto y :g[i])
      {
          for(int j=y.l;j<=y.r;j++)
              q[y.id].ans+=y.fu*t[a[j]];
      }
  }

---

完整参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,k,a[N],Len;
ll ans[N],pre[N],t[N];
//pre[i]: a[1]-a[i-1] 中与 a[i] 异或后 符合条件的个数
vector<int>b;  //二进制中1的个数为k的所有数

struct Q{
    int id,l,r;
    ll ans;
}q[N];
struct G{
    int id,l,r,fu;  //fu代表正负贡献
};
vector<G>g[N];  //暂存移动时难以计算部分的信息，等会扫描线解决，以固定端点排序
int popcount(int x)
{
    int cnt=0;
    while(x>0)
    {
        if(x)cnt++;
        x-=(x&-x);
    }
    return cnt;
}
bool cmp(Q x,Q y)
{
    if(x.l/Len==y.l/Len)return x.r<y.r;
    return x.l<y.l;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int l,r; cin>>l>>r;
        q[i]=(Q){i,l,r,0};
    }
    //预处理 计算pre
    memset(t,0,sizeof(t));
    for(int i=0;i<(1<<14);i++)   // 16348=2^(14) 
        if(popcount(i)==k)b.push_back(i);
    
    for(int i=1;i<=n;i++)
    {
        pre[i]=t[a[i]];
        for(int x:b)t[a[i]^x]++;
    }
    Len=sqrt(n);  //块长
    sort(q+1,q+m+1,cmp);
    for(int i=1,l=1,r=0;i<=m;i++)
    {
        
        //r右移
        if(r<q[i].r)g[l-1].push_back({i,r+1,q[i].r,-1});
        while(r<q[i].r)q[i].ans+=pre[++r];
        //r左移
        if(q[i].r<r)g[l-1].push_back({i,q[i].r+1,r,1});
        while(q[i].r<r)q[i].ans-=pre[r--];
        
        //l左移
        if(q[i].l<l)g[r].push_back({i,q[i].l,l-1,1});
        while(q[i].l<l)q[i].ans-=pre[--l]+!k;
        //while(q[i].l<l)q[i].ans-=pre[--l];
        //l右移
        if(l<q[i].l)g[r].push_back({i,l,q[i].l-1,-1});
        while(l<q[i].l)q[i].ans+=pre[l++]+!k;
        //while(l<q[i].l)q[i].ans+=pre[l++];
    }
    memset(t,0,sizeof(t));
    //扫描ai 计算 [1,i] 与 [l,r] 符合条件的个数
    for(int i=1; i<=n; i++)
    {
        for(int x:b)t[a[i]^x]++;

        for(auto y :g[i])
        {
            for(int j=y.l;j<=y.r;j++)
                q[y.id].ans+=y.fu*t[a[j]];
        }
    }
    //每次都是求的增量，再求一次前缀和
    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++)cout<<ans[i]<<"\n";
    
    return 0;
}

学习完毕

{{ select(1) }}

• YES
• NO