.png)
由于zkw线段树的特征，其实现主席树时不能自底向上做区间查询，也许记录父节点也可以？我没有再考虑。
不过可以麻烦一点自上而下做。
今天上午对着P10814 【模板】离线二维数点导管的时候想用zkw实现主席树在线做一下，后来发现 2e6 其实已经把空间卡爆了（）
总之我研究了一种从上往下做区间查询的写法，比较丑陋，不过好在是对的，并且这种做法对于zkw线段树的其他形式也能用（就是把从下往上查的做法颠倒了下顺序，有些时候完全没必要）
爆炒 lxl 失败了，但还是纪念一下...
放个代码:
点击查看代码
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define db double
#define ili inline
#define fir first
#define sec second
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define pb push_back
template <typename T>
ili void rd(T &x){
int f=1;x=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
x*=f;
}
template <typename T,typename...Args>
ili void rd(T&x,Args&...args){
rd(x),rd(args...);
}
template <typename T>
ili void wr(T x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x+'0');
else wr<T>(x/10),putchar(x%10+'0');
}
using namespace std;
const int N=1e6+1e6;
const int LG=20;
int n,m,a[N];
int son[N*3+N*LG][2],rt[N],t[N*3+N*LG];
int P=1,DEP,OST;s
ili void add(int i,int ver,int l,int k){
int tl=l+P;
int v=rt[ver];
rt[i]=l=++OST;
t[l]=t[v]+k;
for(int dep=DEP-1;dep>=0;dep--){
if((tl>>dep)&1) son[l][0]=son[v][0],son[l][1]=++OST,v=son[v][1];
else son[l][1]=son[v][1],son[l][0]=++OST,v=son[v][0];
l=OST,t[l]=t[v]+k;
}
}
ili int query(int ver,int x){
int tl=1+P-1,tr=x+P+1;
//左链右链指向的节点
int nowl,nowr;
nowl=nowr=rt[ver];
int res=0;
for(int dep=DEP-1;dep>=0;dep--){
//当前指向的原树左右节点
int nl=(tl>>dep),nr=(tr>>dep);
//相等即两条链的公共祖先，不需要计算，往下指
if(nl==nr){
if(~nl&1) nowl=nowr=son[nowl][0];
else nowl=nowr=son[nowl][1];
}
//互为兄弟，不需要计算，但需要更新指向这一层
else if((nl^1^nr)==0){
nowl=son[nowl][0];
nowr=son[nowr][1];
}
//这层可能计算，具体看原树节点是否满足选取标准
else{
//左链为左子树，选右子树，选完指向左边
if(~nl&1) res=res+t[son[nowl][1]],nowl=son[nowl][0];
//否则指向右边继续选取
else nowl=son[nowl][1];
//右链为右子树，选左子树
if(nr&1) res=res+t[son[nowr][0]],nowr=son[nowr][1];
else nowr=son[nowr][0];
}
}
return res;
}
void xpigeon(){
rd(n,m);
while(P<=n+1) P<<=1,++DEP;
OST=(P<<1)-1;
for(int i=1;i<=n;i++){
rd(a[i]);
}
rt[0]=1;
for(int i=P-1;i;i--) son[i][0]=i<<1,son[i][1]=i<<1|1;
for(int i=1;i<=n;i++){
add(i,i-1,a[i],1);
}
for(int i=1,l,r,x;i<=m;i++){
rd(l,r,x);
int ans=query(r,x)-query(l-1,x);
cout<<ans<<'\n';
}
}
signed main(){
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
xpigeon();
return 0;
}