文件详细信息

下载本文件

本文件的大小为 1883 字节。

#include<algorithm>
#include<cstdio>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
const int maxm=100000,maxn=100000,maxval=10000000;
int m,n;
struct Task{
	int s,e,p;
}task[maxm+1];
bool operator<(const Task a,const Task b){
	return a.p<b.p;
}
struct Seg{
	int cnt,l,r;
	ll sum;
}T[maxm*26*2];
int rt[maxm+1],tot,ql,qr,val,pos;
void modify(const int pre,int&u,const int l,const int r){
	u=++tot;
	T[u]=T[pre];
	if(ql<=l&&r<=qr){
		T[u].cnt++;
		T[u].sum+=val;
		return;
	}
	const int mid=(l+r)>>1;
	if(ql<=mid)modify(T[pre].l,T[u].l,l,mid);
	if(qr>mid)modify(T[pre].r,T[u].r,mid+1,r);
}
int query_cnt(int u,int l,int r){
	int ans=0,mid;
	while(u){
		ans+=T[u].cnt;
		if(l==r)return ans;
		mid=(l+r)>>1;
		if(pos<=mid)u=T[u].l,r=mid;
		else u=T[u].r,l=mid+1;
	}
	return ans;
}
int query_sum(int u,int l,int r){
	ll ans=0,mid;
	while(u){
		ans+=T[u].sum;
		if(l==r)return ans;
		mid=(l+r)>>1;
		if(pos<=mid)u=T[u].l,r=mid;
		else u=T[u].r,l=mid+1;
	}
	return ans;
}
int main(){
	read(m),read(n);
	for(int i=1;i<=m;i++)read(task[i].s),read(task[i].e),read(task[i].p);
	std::sort(task+1,task+m+1);
	for(int i=1;i<=m;i++){
		ql=task[i].s,qr=task[i].e,val=task[i].p;
		modify(rt[i-1],rt[i],1,maxval);
	}
	ll pre=1;
	for(int i=1,x,a,b,c,k,l,r,mid;i<=n;i++){
		read(x),read(a),read(b),read(c);
		k=1+(a*(pre%c)+b)%c;
		pos=x;
		if(query_cnt(rt[m],1,maxval)<=k)pre=query_sum(rt[m],1,maxval);
		else{
			l=1,r=m;
			while(l<r){
				mid=(l+r)>>1;
				if(query_cnt(rt[mid],1,maxval)<k)l=mid+1;
				else r=mid;
			}
			pre=query_sum(rt[l],1,maxval);
		}
		write(pre),putchar('\n');
	}
	return 0;
}