「CQOI2015」任务查询系统 - 主席树/可持久化treap

题目大意

    最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。
    超级计算机中的任务用三元组$(S_i,E_i,P_i)$描述，$(S_i,E_i,P_i)$表示任务从第$S_i$秒开始，在第$E_i$秒后结束（第$S_i$秒和$E_i$秒任务也在运行），其优先级为$P_i$。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。
    调度系统会经常向查询系统询问，第$X_i$秒正在运行的任务中，优先级最小的$K_i$个任务（即将任务按照优先级从小到大排序后取前$K_i$个）的优先级之和是多少。特别的，如果$K_i$大于第$X_i$秒正在运行的任务总数，则直接回答第$X_i$秒正在运行的任务优先级之和。上述所有参数均为整数，时间的范围在$1$到$n$之间（包含$1$和$n$）。

---

题目分析

点到区间的映射不好搞，转化为点到点的映射。
将区间$(l,r)$的$l$处打上添加标记，$r+1$处打上删除标记。
那么每个时刻的所有任务就是对时间作前缀和后的结果。

那么我们就可以用主席树来维护了。
才学了可持久化treap，因此想用可持久化treap来搞一搞。
可持久化treap的空间需求似乎要大一点点，因此必须使用概率交换，不能记录随机值。

注意在插入和删除的时候维护优先级的有序性。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

#define pii pair<int,int>
#define mp make_pair
typedef long long LL;
mt19937 g(rand());

const int maxn=100005;

struct Tree {
	int l,r,size;
	int val;
	LL sum;
	Tree() {} 
	Tree(int _l,int _r,int s,int v,LL _s):l(_l),r(_r),size(s),val(v),sum(_s) {}
};

struct Treap { //以根作为接口
	Tree tree[maxn*110];
	int size;
#define val(x) tree[x].val
#define size(x) tree[x].size
	int newnode(int v) {
		tree[++size]=Tree(0,0,1,v,v);
		return size;
	}
	void push_up(int index) {
		int l=tree[index].l,r=tree[index].r;
		size(index)=size(l)+size(r)+1;
		tree[index].sum=tree[l].sum+val(index)+tree[r].sum;
	}
	pii split(int index,int num) {
		if(!index)return mp(0,0);
		int l=tree[index].l,r=tree[index].r;
		int now=++size;
		tree[now]=tree[index];
		if(num<=size(l)) {
			pii lt=split(l,num);
			tree[now].l=lt.second;
			push_up(now);
			return mp(lt.first,now);
		} else {
			pii rt=split(r,num-size(l)-1);
			tree[now].r=rt.first;
			push_up(now);
			return mp(now,rt.second);
		}
	}
	int merge(int a,int b) {
		if(!a||!b)return a+b;
		int now=++size;
		if(g()%(size(a)+size(b))<size(a)) {
			tree[now]=tree[a];
			tree[now].r=merge(tree[a].r,b);
		} else {
			tree[now]=tree[b];
			tree[now].l=merge(a,tree[b].l);
		}
		push_up(now);
		return now;
	}
	int get_rank(int index,int v) {
		if(!index)return 0;
		if(v<val(index))return get_rank(tree[index].l,v);
		else return size(tree[index].l)+1+get_rank(tree[index].r,v);
	}
	int insert(int index,int v) {
		int k=get_rank(index,v);
		pii tmp=split(index,k); //保证v的有序性
		return merge(merge(tmp.first,newnode(v)),tmp.second);
	}
	int remove(int index,int v) {
		int k=get_rank(index,v);
		return merge(split(index,k-1).first,split(index,k).second);
	}
	LL query(int index,int k) {
		if(!index||!k)return 0;
		if(k<=size(tree[index].l))return query(tree[index].l,k);
		else return tree[tree[index].l].sum+tree[index].val+query(tree[index].r,k-size(tree[index].l)-1);
	}
} bbt;

int n,q,root[maxn];
LL lastans=1;
vector<pii>a[maxn];

int main() {
	srand(time(NULL));
	n=Get_Int();
	q=Get_Int();
	for(int i=1; i<=n; i++) {
		int l=Get_Int(),r=Get_Int(),v=Get_Int();
		a[l].push_back(mp(1,v));
		a[r+1].push_back(mp(-1,v));
	}
	for(int i=1; i<=q; i++) {
		root[i]=root[i-1];
		for(pii tmp:a[i]) {
			int opt=tmp.first,v=tmp.second;
			if(opt==1)root[i]=bbt.insert(root[i],v);
			else root[i]=bbt.remove(root[i],v);
		}
	}
	while(q--) {
		int x=Get_Int(),a=Get_Int(),b=Get_Int(),c=Get_Int();
		int k=1+(lastans*a+b)%c;
		if(k>=bbt.tree[root[x]].size)lastans=bbt.tree[root[x]].sum;
		else lastans=bbt.query(root[x],k);
		printf("%lld\n",lastans);
	}
	return 0;
}