记录编号	159257	评测结果	AAAAAAAAAA
题目名称	[CQOI2015]任务查询系统	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.499 s
提交时间	2015-04-20 16:06:07	内存使用	2.22 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
#define Nil NULL
const int SIZEN=100010;
int value[SIZEN];
class Node{
public:
	int l,r;
	LL cnt,sum;
	Node *lc,*rc;
	Node(){
		l=r=0;
		cnt=sum=0;
		lc=rc=Nil;
	}
	void push_up(void){
		if(lc!=Nil){
			cnt=lc->cnt+rc->cnt;
			sum=lc->sum+rc->sum;
		}
	}
	LL query(int K){//前K个
		if(cnt<=K) return sum;
		if(l==r) return sum/cnt*K;
		if(lc->cnt>=K) return lc->query(K);
		else return lc->sum+rc->query(K-lc->cnt);
	}
};
Node* change(Node *p,int x,int w){//优先级为x的任务数+=w
	Node *now=new Node;*now=*p;
	now->cnt+=w;now->sum+=value[x]*w;
	if(now->l==x&&now->r==x) return now;
	int mid=(now->l+now->r)/2;
	if(x<=mid) now->lc=change(now->lc,x,w);
	else now->rc=change(now->rc,x,w);
	return now;
}
Node* build(int a,int b){
	Node *p=new Node;
	p->l=a,p->r=b;
	if(a<b){
		int mid=(a+b)/2;
		p->lc=build(a,mid);
		p->rc=build(mid+1,b);
	}
	return p;
}
Node *root;
int M,N;//M个任务
vector<int> events[SIZEN];
Node *timecut[SIZEN];
void work(void){
	LL pre=1;
	int x,a,b,c;
	for(int i=1;i<=N;i++){
		scanf("%d%d%d%d",&x,&a,&b,&c);
		LL k=(pre*a+b)%c+1;
		pre=timecut[x]->query(k);
		printf("%lld\n",pre);
	}
}
int realid(int p){
	return lower_bound(value+1,value+1+M,p)-value;
}
void maketree(void){
	timecut[0]=root;
	for(int i=1;i<=N;i++){
		Node *now=timecut[i-1];
		for(int j=0;j<events[i].size();j++){
			int p=events[i][j];
			if(p>0) now=change(now,realid(p),1);
			else now=change(now,realid(-p),-1);
		}
		timecut[i]=now;
	}
}
void init(void){
	scanf("%d%d",&M,&N);
	root=build(1,M);
	int s,e,p;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&s,&e,&p);
		value[i]=p;
		events[s].push_back(p);
		events[e+1].push_back(-p);
	}
	sort(value+1,value+1+M);
}
int main(){
	freopen("cqoi15_query.in","r",stdin);
	freopen("cqoi15_query.out","w",stdout);
	init();
	maketree();
	work();
	return 0;
}