Description:

有若干个任务，第 $i$ 个任务从 $S_i$ 开始， $E_i$ 结束，优先级为 $P_i$ ，求在某一时刻下优先级最小的 $K_i$ 个任务的优先级之和，强制在线。

$1\le N\le 100000$

Solution:

对时间建主席树，在 $S_i$ 插入 $P_i$ ，在 $E_i+1$ 删除 $P_i$ ，每次查询时像区间第 $K$ 大一样在线段树上二分，注意离散化后有多个相同的值可能不全被取到，这时要只取出需要的。注意主席树的建树，可能在一棵里插入多个值，这时每一次插入重建一条链的做法行不通，于是每次判断这次要修改的点和上一棵树对应的点是否一样，一样说明这个点没有被操作过，此时新建一个点并上一颗树对应点的信息赋给他。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

typedef long long ll;

int n,m;

int read()

{

	char c = getchar();

	int res = 0;

	while(c < '0' || c > '9')c = getchar();

	while('0' <= c && c <= '9')

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

#define MAXN 100010

int s[MAXN],to[MAXN],tot = 0;

map<int,int> p;

struct option

{

	int t,pr;

	bool type;

}q[MAXN << 1];

int optnum = 0;

void addquery(int a,int b,bool type)

{

	++optnum;

	q[optnum].t = a;

	q[optnum].pr = b;

	q[optnum].type = type;

	return;

}

bool cmp(option a,option b)

{

	return a.t < b.t;

}

struct node

{

	int c[2],siz;

	ll sum;

	node(){c[0] = c[1] = siz = 0;sum = 0;}

}t[MAXN * 50];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

void build(int rt,int l,int r)

{

	if(l == r)return;

	int mid = ((l + r) >> 1);

	build(t[rt].c[0] = newnode(),l,mid);

	build(t[rt].c[1] = newnode(),mid + 1,r);

	return;

}

void insert(int &rt,int rt_,int k,bool type,int l,int r)

{

	if(rt == rt_)

	{

		rt = newnode();

		t[rt] = t[rt_];

	}

	if(type){t[rt].siz += 1;t[rt].sum += to[k];}

	else    {t[rt].siz -= 1;t[rt].sum -= to[k];}

	if(l == r)return;

	int mid = ((l + r) >> 1);

	if(k <= mid)insert(t[rt].c[0],t[rt_].c[0],k,type,l,mid);

	else insert(t[rt].c[1],t[rt_].c[1],k,type,mid + 1,r);

	return;

}

ll query(int p,ll tot)

{

	if(tot >= t[root[p]].siz)return t[root[p]].sum;

	int l = 1,r = n;

	int cur = root[p];

	ll res = 0;

	while(l < r)

	{

		if(cur == 0)break;

		if(tot <= t[t[cur].c[0]].siz)

		{

			cur = t[cur].c[0];

			r = ((l + r) >> 1);

		}

		else

		{

			res += t[t[cur].c[0]].sum;

			tot -= t[t[cur].c[0]].siz;

			cur = t[cur].c[1];

			l = ((l + r) >> 1) + 1;

		}

		if(l == r && tot <= t[cur].siz)

		{

			res += t[cur].sum / t[cur].siz * tot;

		}

	}

	return res;

}

int main()

{

	n = read();m = read();

	int a,b,c;

	for(int i = 1;i <= n;++i)

	{

		a = read();b = read();c = s[i] = read();

		addquery(a,c,true);addquery(b + 1,c,false);

	}

	sort(s + 1,s + 1 + n);

	for(int i = 1;i <= n;++i)

	{

		if(s[i] != s[i - 1])

		{

			p[s[i]] = ++tot;

			to[tot] = s[i];

		}

	}

	sort(q + 1,q + 1 + 2 * n,cmp);

	build(root[0] = newnode(),1,n);

	for(int i = 1,j = 1;i <= m;++i)

	{

		root[i] = root[i - 1];

		for(;q[j].t <= i && j <= 2 * n;++j)

		{

 			insert(root[i],root[i - 1],p[q[j].pr],q[j].type,1,n);

		}

	}

	ll pre = 1;

	int x;

	for(int i = 1;i <= m;++i)

	{

		x = read();a = read();b = read();c = read();

		pre = 1 + (a * pre + b) % c;

		printf("%lld\n",pre = query(x,pre));

	}

	return 0;

}