数据结构是该好好补补拉。
1. 线段树
2. 平衡树
3. 莫队
3.1 普通莫队
莫队解决的问题一般是区间查询，并且可以离线。利用一种排序区间的方式，保证暴力移动最有指针的复杂度。
我们考虑将序列分块，设一个点 \(i\) 在块 \(b_i\) 内。
假设我们有 \(q\) 个询问，对其进行这样的简单排序：
定义 \(\text{cmp}\) 函数，比较两个区间时，先比较左端点的块编号；相等则比较右端点编号。
排序完成后，我们通过暴力移动指针的方式解决问题。
复杂度？
观察左端点的移动，每次都在同一个块中移动，换块的部分是 \(O(n)\) 的也忽略不计，总的移动次数是 \(O(n^{1.5})\)。
观察右端点的移动，当左端点在同一块内时，右端点递增，那么每个块最多 \(O(n)\)，总的也是 \(O(n^{1.5})\)。这就是莫队的精髓。
3.1 莫队二次离线
最近新 get 到的一个东东。
我们知道，设暴力移动指针的复杂度是 \(x\)，那么莫队可以做到 \(O(n^{1.5} \times x)\) 的复杂度。如果 \(x\) 过大，有可能无法接受。
那么莫队二次离线可以做到什么效果呢？实际上，为了严格一点，设 修改一个元素 的复杂度是 \(x\)，查询一个元素 的复杂度是 \(y\)（两者需要结合使用，必须相对而言，不能各取最小值），那么可以做到的是 \(O(n \times x + n ^{1.5} \times y)\)。
开始讲具体怎么做。我们设一个元素 \(x\) 对区间 \((l,r)\) 的贡献是 \(f(l,r,x)\)。
移动指针时，我们可能需要求出这样的 \(f(l,r,x)\)。我们以把右端点向右移动一格为例，贡献是：\(f(l,r-1,r)\)。如果能拆，我们可以把它拆成 \(f(1,r-1,r) - f(1,l-1,r)\)。（不一定是减号）
现在我们 二次离线，这些移动端点的贡献我们再离线下来去计算。因为被我们拆成了前缀，所以好算了很多，复杂度也轻松做到上述的。
但是！我们发现移动了 \(O(n^{1.5})\) 次指针，也就是如果全部离线下来用 vector 存，那么空间寄了。
但是！每次移动指针都是一个区间，所以存储这个区间。就做完了 /cf
现在我们上代码讲解 P4887
// 首先为了降低查询的复杂度，考虑维护 tong 表示一个数的贡献
// a^b=c 等价于 b=a^c
// 我们假设 c 是合法数字，那么加入一个数的时候去枚举 c 暴力改桶
// 修改复杂度虽然高，但是查询成了 O(1)
// 完美解决
ll n,m,k,block,bl[100005];
struct Ques{
ll l,r,id,ans;
}ques[100005];
bool operator< (Ques A,Ques B){
if(bl[A.l]==bl[B.l]) return A.r<B.r;
else return bl[A.l]<bl[B.l];
}
ll popcount(ll x){
ll res=0;
while(x){
res+=(x&1);
x>>=1;
}
return res;
}
ll pre[100005], tong[100005], ans[100005], a[100005];
vector<tuple<ll,ll,ll,ll> >vec[100005];
void solve(){
n=read(), m=read(), k=read();
if(k>=14){
for(ll i=1;i<=m;i++){
cout<<0<<endl;
}
return;
}
block = n / sqrt(m);
for(ll i=1;i<=n;i++) bl[i]=(i-1)/block+1;
for(ll i=1;i<=n;i++) a[i]=read();
for(ll i=1;i<=m;i++)
ques[i].l=read(), ques[i].r=read(), ques[i].id=i;
sort(ques+1, ques+m+1);
vector<ll>allow;
for(ll i=0;i<16384;i++){
if(popcount(i)==k){
allow.emplace_back(i);
}
} // 预处理合法数字
ll l=1, r=0;
for(ll i=1;i<=n;i++){
pre[i]=tong[a[i]];
for(auto x: allow) ++tong[a[i]^x];
}
memset(tong, 0, sizeof(tong));
for(ll i=1;i<=m;i++){
if(l>ques[i].l) vec[r].emplace_back(ques[i].l, l-1, i, 1);
while(l>ques[i].l) --l, ques[i].ans-=pre[l];
//如果左端点需要向左移动，那么 [l-1, ques[i].l] 这一段的贡献都得加上，对应前缀为 r，但是要减掉 pre 预处理的前缀（对前面的贡献多加了）
if(r<ques[i].r) vec[l-1].emplace_back(r+1, ques[i].r, i, -1);
while(r<ques[i].r) ++r, ques[i].ans+=pre[r];
// 向上面这样分析就好了
if(l<ques[i].l) vec[r].emplace_back(l, ques[i].l-1, i, -1);
while(l<ques[i].l) ques[i].ans+=pre[l], ++l;
if(r>ques[i].r) vec[l-1].emplace_back(ques[i].r+1, r, i, 1);
while(r>ques[i].r) ques[i].ans-=pre[r], --r;
} // 核心，重点
for(ll i=1;i<=n;i++){
for(auto x: allow) ++tong[a[i]^x];
for(auto P: vec[i]){
for(ll j=get<0>(P); j<=get<1>(P); j++){
if(j<=i && k==0) ques[get<2>(P)].ans+=get<3>(P)*(tong[a[j]]-1);
else ques[get<2>(P)].ans+=get<3>(P)*(tong[a[j]]);
}
// 大力枚举区间修改贡献
}
}
for(ll i=1;i<=m;i++) ques[i].ans += ques[i-1].ans; // 注意我们只维护了答案的差分，最后求一遍前缀和
for(ll i=1;i<=m;i++)
ans[ques[i].id]=ques[i].ans;
for(ll i=1;i<=m;i++) printf("%lld\n", ans[i]);
}