bzoj 3932 任务查询系统

Posted on | Views:

主席树.

将每个任务视作在时刻 $S_i$ 插入,时刻 $T_i+1$ 删除.

用主席树维护每个时刻存在的所有任务,查询时在主席树上二分.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,m,val[MAXN],tot=0;
struct opt
{
	int pos,c,tp;
	opt(int pos=0,int c=0,int tp=0):pos(pos),c(c),tp(tp) {}
	bool operator < (const opt &rhs) const
	{
		return pos<rhs.pos;
	}
}p[MAXN<<1];
int rt[MAXN],idx=0;
struct node
{
	int ls,rs,cnt;
	ll sum;
}Tree[MAXN*40];
#define root Tree[o]
#define lson Tree[root.ls]
#define rson Tree[root.rs]
void upd(int &o,int lst,int l,int r,int pos,int tp)
{
	o=++idx;
	root=Tree[lst];
	root.cnt+=tp,root.sum+=1LL*tp*val[pos];
	if(l==r)
		return;
	int mid=(l+r)>>1;
	if(pos<=mid)
		upd(root.ls,Tree[lst].ls,l,mid,pos,tp);
	else
		upd(root.rs,Tree[lst].rs,mid+1,r,pos,tp);
}
ll query(int o,int l,int r,int k)
{
	if(root.cnt<=k)
		return root.sum;
	if(l==r)
		return 1LL*val[l]*k;
	int mid=(l+r)>>1;
	if(lson.cnt>=k)
		return query(root.ls,l,mid,k);
	else
		return query(root.rs,mid+1,r,k-lson.cnt)+lson.sum;
}
int main()
{
	m=read(),n=read();
	for(int i=1;i<=m;++i)
	{
		int L=read(),R=read(),c=read();
		val[++tot]=c;
		p[2*i-1]=opt(L,c,1);
		p[2*i]=opt(R+1,c,-1);
	}
	sort(val+1,val+1+tot);
	tot=unique(val+1,val+1+tot)-val-1;
	sort(p+1,p+1+2*m);
	for(int i=1,j=0;i<=n;++i)
	{
		int tmp=rt[i-1],nxt;		
		while(j<2*m && p[j+1].pos==i)
		{
			++j;
			p[j].c=lower_bound(val+1,val+1+tot,p[j].c)-val;
			upd(nxt,tmp,1,tot,p[j].c,p[j].tp);
			tmp=nxt;
		}
		rt[i]=tmp;
	}
	ll lastans=1;
	for(int i=1;i<=n;++i)
	{
		int x=read();
		int k=1+(lastans*read()+read())%read();
		lastans=query(rt[x],1,n,k);
		printf("%lld\n",lastans);
	}
	return 0;
}