bzoj3932【CQOI2015】任務查詢系統

Description

最近實驗室正在為其管理的超級計算機編制一套任務管理系統，而你被安排完成其中的查詢部分。 超級計算機中的任務用三元組(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任務從第Si秒開始，在第Ei秒後結束（第Si秒和Ei秒任務也在運行），其優先級為Pi。同一時間可能有多個任務同時執行，它們的優先級可能相同，也可能不同。調度系統會經常向查詢系統詢問，第Xi秒正在運行的任務中，優先級最小的Ki個任務（即將任務按照優先級從小到大排序後取前Ki個）的優先級之和是多少。特別的，如果Ki大於第Xi秒正在運行的任務總數，則直接回答第Xi秒正在運行的任務優先級之和。上述所有參數均為整數，時間的范圍在1到n之間（包含1和n）。

Input

輸入文件第一行包含兩個空格分開的正整數m和n，分別表示任務總數和時間范圍。 接下來m行，每行包含三個空格分開的正整數Si、Ei和Pi(Si≤Ei)，描述一個任務。 接下來n行，每行包含四個空格分開的整數Xi、Ai、Bi和Ci，描述一次查詢。查詢的參數Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci 計算得到。其中Pre表示上一次查詢的結果，對於第一次查詢，Pre=1。

Output

輸出共n行，每行一個整數，表示查詢結果。

Sample Input

4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3

Sample Output

2
8
11

HINT

樣例解釋
K1 = (1*1+3)%2+1 = 1
K2 = (1*2+3)%4+1 = 2
K3 = (2*8+4)%3+1 = 3
對於100%的數據，1≤m,n,Si,Ei,Ci≤100000，0≤Ai,Bi≤100000，1≤Pi≤10000000，Xi為1到n的一個排列

Source

可持久化線段樹裸題

然而我改了好久，好久，好久......其實最後也不明白為什麼之前是錯的......QAQ

80分程序不同的是49行最後為return (ll)l*(ll)num，求好心同學解答。。。T_T

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 200005
#define maxm 8000005
using namespace std;
int m,n,tot;
int rt[maxn],ls[maxm],rs[maxm];
int f[maxn],fp[maxn];
ll cnt[maxm],sum[maxm];
struct data{int s,e,p,num;}a[maxn];
struct poi{int tim,val,flg;}b[maxn*2];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline bool cmpa(data x,data y){return x.p>1;
	build(ls[k],l,mid);
	build(rs[k],mid+1,r);
}
inline void update(int x,int &y,int l,int r,int v,int d)
{
	y=++tot;
	cnt[y]=cnt[x]+d;sum[y]=sum[x]+(ll)f[v]*(ll)d;
	if (l==r) return;
	ls[y]=ls[x];rs[y]=rs[x];
	int mid=(l+r)>>1;
	if (v<=mid) update(ls[x],ls[y],l,mid,v,d);
	else update(rs[x],rs[y],mid+1,r,v,d);
}
inline ll query(int k,int num,int l,int r)
{
	if (num==cnt[k]) return sum[k];
	if (l==r) return sum[k]/cnt[k]*num;
	int mid=(l+r)>>1;
	if (num<=cnt[ls[k]]) return query(ls[k],num,l,mid);
	else return sum[ls[k]]+query(rs[k],num-cnt[ls[k]],mid+1,r);
}
int main()
{
	m=read();n=read();
	F(i,1,m){a[i].s=read();a[i].e=read();a[i].p=read();a[i].num=i;}
	sort(a+1,a+m+1,cmpa);
	int sz=0;
	F(i,1,m)
	{
		if (i==1||a[i].p!=a[i-1].p) f[++sz]=a[i].p;
		fp[i]=sz;
	}
	F(i,1,m)
	{
		b[i*2-1]=(poi){a[i].s,fp[i],1};
		b[i*2]=(poi){a[i].e+1,fp[i],-1};
	}
	sort(b+1,b+m*2+1,cmpb);
	build(rt[0],1,n);
	int t=1;
	F(i,1,n)
	{
		int pre=rt[i-1],tmp=rt[i-1];
		for(;t<=2*m&&b[t].tim==i;t++)
		{
			update(pre,tmp,1,n,b[t].val,b[t].flg);
			pre=tmp;
		}
		rt[i]=tmp;
	}
	ll pr=1;
	F(i,1,n)
	{
		ll xi=read(),ai=read(),bi=read(),ci=read();
		ll ki=(ai*pr+bi)%ci+1;
		if (ki>cnt[rt[xi]]) pr=sum[rt[xi]];
		else if (ki==0) pr=0;
		else pr=query(rt[xi],ki,1,n);
		printf("%lld\n",pr);
	}
	return 0;
}