Steven_MengのBlog

传送门

先考虑一下暴力怎么打,对于每个时间,我们开一个$vector$,对于每一个任务,我们在$[S_i,E_i]$的$vector$里面都$pushback$一遍$P_i$即可。

但是这样的暴力是愚蠢的暴力,考虑优化,我们在$S_i$和$E_i+1$的位置分别打上加入和删除标记,到某一个时间,我们先复制上一个时间的$vector$,然后按照标记加入和删除$P_i$,事实上,这起了差分的作用。

这样会有什么不好的地方,首先,每次复制上一次的$vector$,绝对会爆空间,其次,查询不好搞。

如何减少空间,我们使用jzm主席树,每次加入或者删除$P_i$最多只需要$\log n$的空间,在主席树上面查询也比较好搞,只要在每个节点维护任务的总数,任务的优先级之和即可。

如果你想偷懒(像我一样),预处理的时候不用一个一个合并过去,而是每个节点先插入$P_i$,然后一个一个线段树合并过去,代码量能减少不少。

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
#include <bits/stdc++.h>
#define MAXN 100005
#define LOG 105
using namespace std;
int S[MAXN],E[MAXN],P[MAXN];
int org[MAXN];
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<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int rt[MAXN];
namespace SegmentTree{
struct node{
int l,r;
int cnt;//任务的总数
int val;//任务的优先级之和
}tree[MAXN*LOG];
int tot;
#define lc tree[i].l
#define rc tree[i].r
inline void pushup(int i,int x,int y){
tree[i].cnt=tree[x].cnt+tree[y].cnt;
tree[i].val=tree[x].val+tree[y].val;
}
void Update(int &i,int l,int r,int pos,int val){
if (!i) i=++tot;
if (l==r){
tree[i].cnt+=val;
tree[i].val+=val*P[l];
return ;
}
int mid=(l+r)>>1;
if (pos<=mid) Update(lc,l,mid,pos,val);
else Update(rc,mid+1,r,pos,val);
pushup(i,lc,rc);
}
int Query(int i,int l,int r,int k){
if (l==r){
return P[l]*min(k,tree[i].cnt);//特别注意,因为查询的可能大于任务总数
}
int mid=(l+r)>>1;
if (tree[lc].cnt>=k) return Query(lc,l,mid,k);
else return tree[lc].val+Query(rc,mid+1,r,k-tree[lc].cnt);
}
void Merge(int &x,int y){//y->x
if (!x||!y){
x=x+y;
return ;
}
pushup(x,x,y);
Merge(tree[x].l,tree[y].l);
Merge(tree[x].r,tree[y].r);
}
}
using namespace SegmentTree;
int main(){
int m=read(),n=read();
for (register int i=1;i<=m;++i){
S[i]=read(),E[i]=read(),org[i]=P[i]=read();
}
sort(P+1,P+1+m);
int M=unique(P+1,P+1+m)-P-1;
for (register int i=1;i<=m;++i){
int rk=lower_bound(P+1,P+1+M,org[i])-P;
Update(rt[S[i]],1,M,rk,1);
Update(rt[E[i]+1],1,M,rk,-1);
}
for (register int i=1;i<=n;++i){
Merge(rt[i],rt[i-1]);
}
int pre=1;
for (register int i=1;i<=n;++i){
int x=read(),a=read(),b=read(),c=read();
int k=(1+((long long)a*pre+b)%c);
printf("%d\n",pre=Query(rt[x],1,M,k));
}
}

 评论