重修 分块和莫队
二次离线莫队
设莫队单次修改的时间为 \(t\)，则二次离线莫队将莫队从 \(O(nt\sqrt{n})\) 优化到 \(O(nt+n\sqrt{n})\)，当然前提是满足区间可减性。
例题：P4887 【模板】莫队二次离线
给你一个序列 \(a\)，每次查询给一个区间 \([l,r]\)，查询 \(l \leq i< j \leq r\)，且 \(popcnt(a_i \oplus a_j)=k\) 的二元组 \((i,j)\) 的个数.\(\oplus\) 是指按位异或。\(n,q\le 10^5,0\le a_i,k<2^{14}\)。
设 \(m\) 为 \([0,V)\) 中 \(popcnt=k\) 的个数，我们预处理这些数，最后时间复杂度也和 \(m\) 有关。
设 \(f(x,l,r)\) 表示
\[y\in[l,r],popcnt(a_x\oplus a_y)=k \]的 \(y\) 的个数。
由于区间可减，得到
\[f(x,l,r)=f(x,1,r)-f(x,1,l-1) \]所以下文用 \(f(x,y)\) 来简写 \(f(x,1,y)\)。
只有当 \(k=0\) 时 \(popcnt(a_x\oplus a_x)=k\)，所以得到
\[f(x,x)=f(x,x-1)+[k=0] \]我们先正常莫队（甚至可以奇偶优化）。举个例子（莫队区间设为 \([L,R]\)）。
当 \(L\) 增大至 \(l\) 时，此询问比上次减少
\[\begin{aligned} \sum_{x=L}^{l-1} f(x,x+1,R)&=\sum_{x=L}^{l-1} f(x,R)-f(x,x) \\ &=\sum_{x=L}^{l-1} f(x,R)-\sum_{x=L}^{l-1} (f(x,x-1)+[k=0]) \\ &(p(x):=f(x+1,x)) \\ &=\sum_{x=L}^{l-1} f(x,R)-\sum_{x=L}^{l-1} (p(x-1)+[k=0]) \end{aligned}\]\(L\) 增大、\(R\) 减小、\(R\) 增大 同理，不再赘述。
我们可以用桶 \(O(nm)\) 预处理出 \(p(x)\)。所以剩下的只要拎出 \(\sum_{x=L}^{l-1} f(x,R)\) 类的东西求即可，最后再代回来算答案。
接下来就是二次离线部分了。
我们将每一个形如 \(\sum_{x=l}^{r} f(x,i)\) 的询问挂在 \(i\) 位置上。
然后再用桶扫，同时计算每个位置上的询问。
这部分是 \(O(nm+n\sqrt{n})\)，\(n\sqrt{n}\) 是因为二级询问有 \(O(n\sqrt{n})\) 个，每个只要 \(O(1)\) 回答。
然后就做完了，总时间 \(O(nm+n\sqrt{n})\)，与开头说的相同。
例题代码：
点击查看代码
//Said no more counting dollars. We'll be counting stars.
#include
using namespace std;
#define pb emplace_back
#define mem(x,y) memset(x,y,sizeof(x))
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define int long long
#define N 100010
#define V 16384//值域
vector bu;//0~V-1 popcnt=k 的数
int n,m,k,a[N],b[N],gap;
struct Que{
int l,r,id,ans;//ans:比莫队中上次询问答案的增量
friend bool operator<(Que x,Que y){return b[x.l]==b[y.l]?((b[x.l]&1)?x.ry.r):x.l[1,i]) ct表示贡献
int t[V];//桶
int ans[N];//最终答案
vector > v[N];
//第一次莫队留下的询问v[i].：[l,r] 区间中所有 x，sum ct(x->[1,i])，乘系数 val 贡献给询问 i
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
For(i,0,V-1) if(__builtin_popcount(i)==k) bu.pb(i);
For(i,1,n) scanf("%lld",a+i);
For(i,1,m) scanf("%lld%lld",&q[i].l,&q[i].r),q[i].id=i;
gap=sqrt(n);
For(i,1,n) b[i]=(i-1)/gap+1;
sort(q+1,q+1+m);
For(i,1,n){
for(int j:bu) t[a[i]^j]++;
p[i]=t[a[i+1]];
}
int L=1,R=0,l,r;
For(i,1,m){
l=q[i].l,r=q[i].r;
if(Lr) v[L-1].pb(r+1,R,i,1);
while(R>r){q[i].ans-=p[R-1]; --R;}
if(L>l) v[R].pb(l,L-1,i,1);
while(L>l){q[i].ans-=p[L-2]+(!k);--L;}
if(R