记录编号	158347	评测结果	AAAAAAAAAA
题目名称	[CQOI2015]任务查询系统	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	2.484 s
提交时间	2015-04-14 17:56:07	内存使用	277.63 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
//#define USEFREAD
#ifdef USEFREAD
#define InputLen 4000000
char *ptr=(char *)malloc(InputLen);
#define getc() (*(ptr++))
#else
#define getc() (getchar())
#endif
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout))
template<class T>inline void getd(T &x){
    char ch = getc();bool neg = false;
    while(!isdigit(ch) && ch != '-')ch = getc();
    if(ch == '-')ch = getc(), neg = true;
    x = ch - '0';
    while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
    if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 100004;
typedef long long LL;
struct Event{bool Add;int Time, P;}E[maxn << 1], *Eend = E;
inline bool operator < (const Event &a, const Event &b){return a.Time < b.Time;}

int Plist[maxn], *Pend = Plist;
#define id(x) (lower_bound(Plist, Pend, x) - Plist)

struct SegT *Pool;
struct SegT{
	int L, R, cnt, mid;
	LL Sum;
	SegT *ls, *rs;
	inline void init(int l, int r){
		L = l, R = r, mid = (L + R) >> 1;
		if(r - l == 1)return;
		ls = Pool++;rs = Pool++;
		ls->init(L, mid), rs->init(mid, R);
	}
	void Add(int i, int d){
		if(R - L == 1){cnt += d;Sum += Plist[L] * d;return;}
		SegT *t = Pool++;
		if(i < mid)*t = *ls, t->Add(i, d), ls = t;
		else *t = *rs, t->Add(i, d), rs = t;
		cnt += d;Sum += d * Plist[i];
	}
	LL Query(int K){
		if(R - L == 1)return (LL)K * Plist[L];
		if(K >= cnt)return Sum;
		if(K <= ls->cnt)return ls->Query(K);
		return ls->Sum + rs->Query(K - ls->cnt);
	}
}Root[maxn * 90];

inline int init(){
	int i, M, N, L, R, P;
	Event *it;
	getd(M), getd(N);
	Pool = Root + N + 1;
	while(M--){
		getd(L), getd(R), getd(P);
		*(Pend++) = P;
		*(Eend++) = (Event){true, L, P};
		*(Eend++) = (Event){false, R + 1, P};
	}
	Eend->Time = maxn;
	sort(E, Eend);
	sort(Plist, Pend);
	Root->init(0, Pend - Plist);
	SegT *u = Root, *v = Root + 1;
	for(i = 1, it = E;i <= N;++i){
		*(v++) = *(u++);
		while(it->Time == i){
			u->Add(id(it->P), 2 * it->Add - 1);
			++it;
		}
	}
	return N;
}

int main(){
	#ifdef DEBUG
	freopen("test.txt", "r", stdin);
	#else
	SetFile(cqoi15_query);
	#endif
	#ifdef USEFREAD
	fread(ptr,1,InputLen,stdin);
	#endif
	
	int X, A, B, C, N;
	LL Pre = 1;
	N = init();
	while(N--){
		getd(X), getd(A), getd(B), getd(C);
		Pre = Root[X].Query((Pre * A + B) % C + 1);
		printf("%lld\n", Pre);
	}
	
#ifdef DEBUG
    printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}