记录编号	411028	评测结果	AAAAAAAAAA
题目名称	[CQOI2015]任务查询系统	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.837 s
提交时间	2017-06-03 13:34:31	内存使用	194.84 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+10,M=1e7+10;
struct pt{
	int x;ll y;
	pt(int X=0,ll Y=0){x=X;y=Y;}
	pt operator + (const pt &a)const{return pt(x+a.x,y+a.y);}
}s[M];
int n,m,lc[M],rc[M],root[N],id,a[N];
int rank(int x){
	int l=1,r=m;
	while (l<r){
		int mid=(l+r)>>1;
		if (a[mid]>=x) r=mid;else l=mid+1;
	}
	return l;
}
int add(int x,int l,int r,int p,pt d){
	int now=++id;
	s[now]=s[x]+d;
	lc[now]=lc[x];
	rc[now]=rc[x];
	if (l==r) return now;
	int mid=(l+r)>>1;
	if (p>mid) rc[now]=add(rc[x],mid+1,r,p,d);
		else lc[now]=add(lc[x],l,mid,p,d);
	return now;
}
ll query(int x,int k){
	int l=1,r=m;ll ans=0;
	while (l<r){
		int mid=(l+r)>>1;
		pt sum=s[lc[x]];
		if (sum.x>=k) x=lc[x],r=mid;
		else{
			k-=sum.x;
			ans+=sum.y;
			x=rc[x];
			l=mid+1;
		}
	}
	return ans+min(k,s[x].x)*(ll)a[l];
}
struct opt{int t,p,d;}Q[N];int cnt;
bool cmp(const opt &a,const opt &b){return a.t<b.t;}
int main()
{
	freopen("cqoi15_query.in","r",stdin);
	freopen("cqoi15_query.out","w",stdout);
	scanf("%d%d",&m,&n);
	for (int i=1;i<=m;i++){
		int l,r,p;
		scanf("%d%d%d",&l,&r,&p);
		Q[++cnt]=(opt){l,p,1};
		Q[++cnt]=(opt){r+1,p,-1};
		a[i]=p;
	}
	sort(a+1,a+m+1);
	sort(Q+1,Q+cnt+1,cmp);
	for (int i=1,p=1;i<=n;i++){
		root[i]=root[i-1];
		for (;p<=cnt&&Q[p].t==i;p++)
			root[i]=add(root[i],1,m,rank(Q[p].p),pt(Q[p].d,Q[p].d*Q[p].p));
	}
	ll ans=1;
	for (int i=1;i<=n;i++){
		int x,a,b,c,k;
		scanf("%d%d%d%d",&x,&a,&b,&c);
		k=1+(ans%c*a+b)%c;
		printf("%lld\n",ans=query(root[x],k));
	}
	return 0;
}