主席树求某一时刻权值第k大的数

地址

int Case = 1, n, m;
struct node{
	int l, r;
	ll sum, cnt;
}tr[maxn<<5];
int root[maxn], tot;
struct date{
	int val;
	int t, flag;
	bool operator<(const date x)const {
		return t < x.t;
	}
}op[maxn<<1];
vector<int>ve;
int getid(int x) {return lower_bound(ve.begin(), ve.end(), x)-ve.begin()+1;}
void build(int &rt, int l, int r) {
	rt = ++tot;
	if(l == r) return;
	int mid = (l+r)/2;
	build(tr[rt].l, l, mid);
	build(tr[rt].r, mid+1, r);
}
void update(int &rt, int x, int l, int r, int pos, int flag) {
	rt = ++tot;
	tr[rt] = tr[x];tr[rt].cnt += flag;tr[rt].sum += ve[pos-1]*flag;
	if(l == r) return;
	int mid = (l+r)/2;
	if(pos<=mid) update(tr[rt].l, tr[x].l, l, mid, pos, flag);
	else update(tr[rt].r, tr[x].r, mid+1, r, pos, flag);
}
ll query(int rt, int l, int r, int k) {
	if(tr[rt].cnt<=k) return tr[rt].sum;
	if(l == r) return tr[rt].sum/tr[rt].cnt*k;
	int mid = (l+r)/2;
	if(k<=tr[tr[rt].l].cnt) return query(tr[rt].l, l, mid, k);
	else return tr[tr[rt].l].sum+query(tr[rt].r, mid+1, r, k-tr[tr[rt].l].cnt);
}
void solve(){
	tot = 0;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= 2*n; i+=2) {
    	int a, b, c;scanf("%d%d%d", &a, &b, &c);
    	ve.push_back(c);
    	op[i].val = op[i+1].val = c;
    	op[i].t = a;op[i+1].t = b+1;
    	op[i].flag = 1;op[i+1].flag = -1;
    }
    sort(op+1, op+1+2*n);
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    int len = ve.size();
    build(root[0], 1, len);
    for(int i = 1; i <= 2*n; i++) {
    	int pos = getid(op[i].val);
    	update(root[op[i].t], root[op[i-1].t], 1, len, pos, op[i].flag);
    }
    for(int i = 1; i <= m; i++) {
    	if(!root[i]) root[i] = root[i-1];
    }
    ll pre = 1;
    for(int i = 1; i <= m; i++) {
    	int x, A, B, C;
    	scanf("%d%d%d%d", &x, &A, &B, &C);
    	int k = 1+(pre*A+B)%C;
    	printf("%lld\n", pre = query(root[x], 1, len, k));
    }
}