Luogu3168 [CQOI2015] 任务查询系统 - 主席树 - 二分 -

题目链接：https://www.luogu.com.cn/problem/P3168

题解：
主席树可以解决一类j静态区间第 \(k\) 小的问题，我们先来看看这是怎么工作的

• 主席树的本质就是有很多棵线段树，然后发现这些线段树绝大多数都是重叠的，因此可以优化到空间复杂度 \(O(n\log n)\)
• 在这里，我们将序列的每一个位置都开一棵权值线段树，一个位置的线段树中的每个节点就代表了这个权值出现的次数，求法就是上一个位置 + 当前位置的权值带来的影响。例如，\(a_3=5\)，那么 \(rt[3]=rt[2], se[3][区间[5,5]] = se[2][区间[5,5]]+1\)。由于权值当做了下标，因此需要提前离散化。
• 然后找某个区间 \([l,r]\) 的第 \(k\) 小的时候，就是利用第 \(r\) 棵线段树减去第 \(l-1\) 棵线段树求出这段区间里面各个权值的出现次数。然后在这个新的线段树上二分即可。

回到原问题，先将 \(p_i\) 离散化，再将区间问题利用差分化成单点修改，然后对于差分后的每个位置 \(t_i\) 建权值线段树。权值线段树维护两个东西：一个是 \(t_i\) 时刻仍然在运行的任务的权值在权值区间 \([l,r]\) 中出现了几次，一个是这些出现过的权值的和。

维护的时候需要注意，可以开两个 vector 分别记一下开始点和结束点，这样每建一棵权值线段树的时候就加上当前位置对应的开始区间的权值，删去当前位置结束的区间权值

有一些细节，比如只需要继承一次，然后也要考虑不增不删的情况

每次查询的时候，\(x\) 位置就在第 \(x\) 棵权值线段树中查询，前 \(k\) 小之和就在这棵权值线段树上二分。

代码：

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

int n,qu;
int s[maxn], e[maxn], p[maxn], q[maxn], cnt=0;
int rt[maxn];
struct segm{
	int ls,rs,occ;
	ll sum;
}se[maxn << 5];
int clk = 0;
ll cf[maxn];
vector<int>st[maxn], ed[maxn];

void pushup(int num){
	int ls = se[num].ls, rs = se[num].rs;
	se[num].occ = se[ls].occ + se[rs].occ;
	se[num].sum = se[ls].sum + se[rs].sum;
}

void build(int l,int r,int &num){
	num = ++ clk;
	if(l == r){
		se[num].occ = 0;
		se[num].sum = 0;
		return ;
	}
	int mid = l+r>>1;
	build(l,mid,se[num].ls); build(mid+1,r,se[num].rs);
	pushup(num);
}

void update(int l,int r,int to,int sgn, int &num,int pre){
	num = ++ clk;
	se[num] = se[pre];
	if(l == r){
		se[num].occ += sgn;
		se[num].sum += sgn * q[to];
		return ;
	}
	int mid = l+r>>1;
	if(to <= mid)update(l,mid,to,sgn,se[num].ls,se[pre].ls);
	else update(mid+1,r,to,sgn,se[num].rs,se[pre].rs);
	pushup(num);
}

ll query(int l,int r,int rst,int num){
//	printf("hh %d %d %d\n",l,r,rst);
	if(l == r)return 1ll * se[num].sum / se[num].occ * rst;
	int mid = l+r>>1;
	int ls = se[num].ls;
	if(rst <= se[ls].occ)return query(l,mid,rst,ls);
	else return se[ls].sum + query(mid+1,r,rst - se[ls].occ,se[num].rs);
}

signed main(){
//	freopen("P3168_1.in","r",stdin);
	scanf("%d%d",&n,&qu);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&s[i],&e[i],&p[i]), q[++ cnt] = p[i];
	sort(q+1,q+cnt+1);
	cnt = unique(q+1,q+cnt+1) - (q+1);
	for(int i=1;i<=n;i++)
		p[i] = lower_bound(q+1,q+cnt+1,p[i]) - q;
	for(int i=1;i<=n;i++)
		st[s[i]].pb(p[i]), ed[e[i]+1].pb(p[i]);

	build(1,cnt,rt[0]);
	ll now = 0;
	for(int i=1;i<=n;i++){
		int g=0;
		for(int u : st[i])
			// 细节，只需要继承上一个位置的线段树一次 
			update(1,cnt,u,1,rt[i],g ? rt[i] : rt[i-1]), g=1;
//			printf("> %d %d\n",i,u);
		for(int u : ed[i])
			update(1,cnt,u,-1,rt[i],g ? rt[i] : rt[i-1]), g=1;
//			printf(">>> %d\n",u);
		// 如果没有增删，就只继承 
		if(g == 0)update(1,cnt,0,0,rt[i],rt[i-1]);
	}

	ll pre = 1;
	while(qu --){
		int x,a,b,c;scanf("%d%d%d%d",&x,&a,&b,&c);
		int k = 1 + (1ll*a*pre%c + b)%c;
//		int x,k;scanf("%d%d",&x,&k);
//		printf("?? %d\n",k);
		if(k > se[rt[x]].occ)printf("%lld\n",pre = se[rt[x]].sum);
		else printf("%lld\n",pre = query(1,cnt,k,rt[x]));
	}

	return 0;
}