RT
不太懂为什么我主席树的常数是别人的两倍左右

这是我的写法

struct Node{
	int l,r,sum;
}tr[N*40];
#define ls(pos) tr[pos].l
#define rs(pos) tr[pos].r
#define sum(pos) tr[pos].sum
int rt[N];
int tot = 0;
void push_up(int pos){
	sum(pos) = sum(ls(pos)) + sum(rs(pos));
}
void build(int last, int &now, int l, int r,int x){
	now = ++tot;
	ls(now) = ls(last);
	rs(now) = rs(last);
	sum(now) = sum(last);
	if(l == r){
		sum(now)++;
		return;
	}
	int mid = (l+r)>>1;
	if(x <= mid){
		build(ls(last),ls(now),l,mid,x);
	}else{
		build(rs(last),rs(now),mid+1,r,x);
	}
	push_up(now);
} 
int kth(int L, int R, int l, int r,int k){
	if(l == r){
		return l;
	}
	int mid = (l+r)>>1;
	if(sum(ls(R)) - sum(ls(L)) < k) return kth(rs(L),rs(R),mid+1,r,k-(sum(ls(R)) - sum(ls(L))));
	else return kth(ls(L),ls(R),l,mid,k);
}
int query(int L, int R, int l, int r,int x){
	if(l == r){
		return sum(R) - sum(L);
	}
	int mid = (l+r)>>1;
	if(x <= mid) return query(ls(L),ls(R),l,mid,x);
	else return query(rs(L),rs(R),mid+1,r,x);
}