【BZOJ3932】【CQOI2015】任务查询系统

  主席树直接上。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=100010,maxv=4000010;

struct President_Tree
{
	LL sum[maxv];
	int num[maxv];
	int root[maxn];
	int ls[maxv],rs[maxv];
	int IDs;
	int n;
	
	#define mid ((l+r)>>1)

	void Change(int l,int r,int lnd,int &rnd,int p,int c,int o)
	{
		if (rnd==lnd)
		{
			rnd=++IDs;
			ls[rnd]=ls[lnd],rs[rnd]=rs[lnd];
			num[rnd]=num[lnd];
			sum[rnd]=sum[lnd];
		}
		num[rnd]+=o;
		sum[rnd]+=c;
		if (l==r) return;
		if (p<=mid) Change(l,mid,ls[lnd],ls[rnd],p,c,o);
		else Change(mid+1,r,rs[lnd],rs[rnd],p,c,o);
	}

	LL Query(int l,int r,int nd,int k)
	{
		LL res=0;
		while (l<r)
		{
			if (num[nd]<=k) return res+sum[nd];
			int nls=ls[nd],lnum=num[nls];
			if (lnum>=k) nd=nls,r=mid;
			else res+=sum[nls],nd=rs[nd],k-=lnum,l=mid+1;
		}
		if (num[nd]<=k) return res+sum[nd];
		else return res+sum[nd]/num[nd]*k;
	}

	#undef mid

	void Build_Root(int x) {root[x]=root[x-1];}
	void Change(int x,int p,int c,int o) {Change(1,n,root[x-1],root[x],p,c,o);}
	LL Query(int x,int k) {return Query(1,n,root[x],k);}
}T;

struct Info {int t,p;}IS[maxn],IE[maxn];
bool cmp(const Info &a,const Info &b) {return a.t<b.t;}
void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

int temp[maxn];
int n,m,mp;

int main()
{
	read(m),read(n);
	for (int i=1;i<=m;i++) read(IS[i].t),read(IE[i].t),read(IS[i].p),IE[i].t++,IE[i].p=IS[i].p,temp[i]=IE[i].p;
	sort(temp+1,temp+1+m);
	mp=unique(temp+1,temp+1+m)-(temp+1);
	T.n=mp;
	sort(IS+1,IS+1+m,cmp);sort(IE+1,IE+1+m,cmp);
	for (int i=1,ps=0,pe=0;i<=n;i++)
	{
		T.Build_Root(i);
		while (ps<m && IS[ps+1].t==i) ++ps,T.Change(i,lower_bound(temp+1,temp+1+mp,IS[ps].p)-(temp),IS[ps].p,1);
		while (pe<m && IE[pe+1].t==i) ++pe,T.Change(i,lower_bound(temp+1,temp+1+mp,IE[pe].p)-(temp),-IE[pe].p,-1);
	}
	LL pre=1;
	for (int i=1;i<=n;i++)
	{
		int x,a,b,c,k;
		scanf("%d%d%d%d",&x,&a,&b,&c);
		k=((LL)a*pre+b)%c+1;
		pre=T.Query(x,k);
		printf("%lld\n",pre);
	}
	return 0;
}