看到 \(\oplus\)，肯定想到 trie。当我们一位可以是 \(1\) 但是变成 \(0\) 时，一个子树内的都合法。特殊的，最后走到的叶子也合法。
想法负一：我会莫队！时间复杂度 \(\mathcal{O}(n\sqrt{n}\log n)\)，待更新。
想法零：我会树套树！待更新。
想法一：我会 HH 的项链！我们按照 \(r\) 离线，每一次查询变成了找到合法的上一次出现 \(\ge l\) 的个数。按照 trie 上的 dfn 序建成一个线段树（每个节点维护上一次出现的位置），因为 trie 两个不互为祖先的子树不相交，问题变成了：一个询问做多有 \(\log n\) 个区间，问区间内大于等于一个数的个数。可以二分+主席树做到 \(\mathcal{O}(n\log^3 n)\)，或者主席树上二分做到 \(\mathcal{O}(n\log^2 n)\)。
这东西常数又大又难写，能不能再给力一点？
想法二：HH 的项链记录的贡献是最后一个出现的位置！那么我们一个数对 \((c,pos)\)（这个数，这个数出现的位置）在 \([L,R]\) 贡献到不仅要 \(c\) 本生合法，要 \(L\le pos\le R<nxt\)，\(nxt\) 是下一个的位置。那么如果没有 trie 的限制（HH 的项链），就是一个普通的二维数点问题，数 \(L\le l\le R<r\) 的个数，右端点排序，相同先排询问来解决。其实有了 trie 的限制也是简单的。现在已经知道总共有 \(\mathcal{O}(n\log n)\) 个子树会有贡献，子树叶子数量之和是 \(\mathcal{O}(n\log n)\) 的（因为我们是 trie），那么我们可以离线下来，对于每一个子树算出会对哪些询问产生贡献，子树内做一个二维数点即可。这个是均摊 \(\mathcal{O}(n\log n)\) 的。
Code for 2
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+5;
int n,q,cnt=1,c[N],nxt[N],ch[N*18][2],ans[N],L[N],R[N];
vector<pair<int,int> > g[N*18];
vector<int> as[N*18];
void ins(int x,int p1,int p2){
int cur=1;
g[1].push_back({p1,p2});
for (int i=17; i>=0; i--){
int f=(x>>i&1);
if (!ch[cur][f]) ch[cur][f]=++cnt;
cur=ch[cur][f];
g[cur].push_back({p1,p2});
}
}
void qy(int id,int a,int b){
int cur=1;
for (int i=17; i>=0; i--){
int f1=(a>>i&1),f2=(b>>i&1);
if (f2==0){
cur=ch[cur][f1];
}
else{
as[ch[cur][f1]].push_back(id);
cur=ch[cur][f1^1];
}
}
as[cur].push_back(id);
}
struct node {
int l,r,id;
bool operator < (const node &x) const {
return r!=x.r?r>x.r:id>x.id;
}
} a[N*18];
int top,bit[N];
void M(int p,int v){
while (p<N){
bit[p]+=v,p+=p&-p;
}
}
int Q(int p){
int res=0;
while (p){
res+=bit[p],p-=p&-p;
}
return res;
}
void sol(int id){
top=0;
for (auto u : g[id]) a[++top]={u.first,u.second,0};
for (auto u : as[id]) a[++top]={L[u],R[u],u};
sort(a+1,a+1+top);
for (int i=1; i<=top; i++){
if (!a[i].id) M(a[i].l,1);
else ans[a[i].id]+=Q(a[i].r)-Q(a[i].l-1);
}
for (int i=1; i<=top; i++){
if (!a[i].id) M(a[i].l,-1);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for (int i=1; i<=n; i++){
cin>>c[i];
nxt[i]=n+1;
}
for (int i=n; i; i--){
ins(c[i],i,nxt[c[i]]);
nxt[c[i]]=i;
}
cin>>q;
for (int i=1; i<=q; i++){
int a,b;
cin>>L[i]>>R[i]>>a>>b;
qy(i,a,b);
}
for (int i=1; i<=cnt; i++){
sol(i);
}
for (int i=1; i<=q; i++){
cout<<ans[i]<<"\n";
}
return 0;
}