记录编号	295525	评测结果	AAAAAAAAAA
题目名称	[CQOI2015]任务查询系统	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	3.934 s
提交时间	2016-08-13 20:15:47	内存使用	167.49 MiB

#include <cstdio>
#include <queue>
typedef long long ll;
typedef ll TYPE;
const int MAXN=100000+10;
const int MAXM=MAXN*80;
 
static inline int min
(const int&a,const int&b)
	{return a<b?a:b;}
 
static inline int max
(const int&a,const int&b)
	{return a<b?b:a;}
 
struct Node{
	int lc,rc,cnt;
	TYPE sum;
//	Node(){lc=rc=0;cnt=0;sum=0;}
}T[MAXM];
 
int N,M,SIZEN=0;
int root[MAXN],mark[MAXM],fate;
std::vector<int>L[MAXN],R[MAXN];
int V,C;
 
void newNode(int &y,int x)
{	
	T[y=++SIZEN]=T[x];
	mark[y]=fate;
}
void update(int l,int r,int x,int &y)
{
	if(mark[x]!=fate)newNode(y,x);
	T[y].cnt+=C;	T[y].sum+=V*C;
	if(l==r)return ; int mid=(l+r)>>1;
	if(V<=mid)update(l,mid,T[x].lc,T[y].lc);
	else update(mid+1,r,T[x].rc,T[y].rc);
}
TYPE query(int l,int r,int x,int rank)
{
	if(l==r)return (TYPE)l*rank;
	int mid=(l+r)>>1;
	if(T[T[x].lc].cnt>=rank)return query(l,mid,T[x].lc,rank);
	else return query(mid+1,r,T[x].rc,rank-T[T[x].lc].cnt)+T[T[x].lc].sum;
}
int main()
{
	freopen("cqoi15_query.in","r",stdin);
	freopen("cqoi15_query.out","w",stdout);
	int s,e,p,mn=(int)1e9,mx=(int)-1e9;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;++i){
		scanf("%d%d%d",&s,&e,&p);
		mn=min(mn,s);	mx=max(mx,e);
		L[s].push_back(p);
		R[e].push_back(p);
	}
	for(int i=mn;i<=mx;++i){
		newNode(root[i],root[i-1]);++fate;
		int sizen=L[i].size();
		for(int j=0;j<sizen;++j)
			V=L[i][j],C=1,
			update(1,(int)1e7,root[i],root[i]);
		sizen=R[i-1].size();
		for(int j=0;j<sizen;++j)
			V=R[i-1][j],C=-1,
			update(1,(int)1e7,root[i],root[i]);
	}
	int x;
	TYPE a,b,c,pre=1;
	for(int i=1;i<=M;++i){
		scanf("%d%lld%lld%lld",&x,&a,&b,&c);
		int k=(int)(1LL+(a*pre+b)%c);
		if(T[root[x]].cnt<=k)printf("%lld\n",pre=T[root[x]].sum);
		else printf("%lld\n",pre=query(1,(int)1e7,root[x],k));
	}return 0;
}