「CQOI2015」任务查询系统 - 主席树/可持久化treap | Bill Yang's Blog

「CQOI2015」任务查询系统 - 主席树/可持久化treap

题目大意

    最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。
    超级计算机中的任务用三元组$(S_i,E_i,P_i)$描述,$(S_i,E_i,P_i)$表示任务从第$S_i$秒开始,在第$E_i$秒后结束(第$S_i$秒和$E_i$秒任务也在运行),其优先级为$P_i$。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。
    调度系统会经常向查询系统询问,第$X_i$秒正在运行的任务中,优先级最小的$K_i$个任务(即将任务按照优先级从小到大排序后取前$K_i$个)的优先级之和是多少。特别的,如果$K_i$大于第$X_i$秒正在运行的任务总数,则直接回答第$X_i$秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范围在$1$到$n$之间(包含$1$和$n$)。


题目分析

点到区间的映射不好搞,转化为点到点的映射。
将区间$(l,r)$的$l$处打上添加标记,$r+1$处打上删除标记。
那么每个时刻的所有任务就是对时间作前缀和后的结果。

那么我们就可以用主席树来维护了。
才学了可持久化treap,因此想用可持久化treap来搞一搞。
可持久化treap的空间需求似乎要大一点点,因此必须使用概率交换,不能记录随机值。

注意在插入和删除的时候维护优先级的有序性。


代码

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
#define pii pair<int,int>
#define mp make_pair
typedef long long LL;
mt19937 g(rand());
const int maxn=100005;
struct Tree {
int l,r,size;
int val;
LL sum;
Tree() {}
Tree(int _l,int _r,int s,int v,LL _s):l(_l),r(_r),size(s),val(v),sum(_s) {}
};
struct Treap { //以根作为接口
Tree tree[maxn*110];
int size;
#define val(x) tree[x].val
#define size(x) tree[x].size
int newnode(int v) {
tree[++size]=Tree(0,0,1,v,v);
return size;
}
void push_up(int index) {
int l=tree[index].l,r=tree[index].r;
size(index)=size(l)+size(r)+1;
tree[index].sum=tree[l].sum+val(index)+tree[r].sum;
}
pii split(int index,int num) {
if(!index)return mp(0,0);
int l=tree[index].l,r=tree[index].r;
int now=++size;
tree[now]=tree[index];
if(num<=size(l)) {
pii lt=split(l,num);
tree[now].l=lt.second;
push_up(now);
return mp(lt.first,now);
} else {
pii rt=split(r,num-size(l)-1);
tree[now].r=rt.first;
push_up(now);
return mp(now,rt.second);
}
}
int merge(int a,int b) {
if(!a||!b)return a+b;
int now=++size;
if(g()%(size(a)+size(b))<size(a)) {
tree[now]=tree[a];
tree[now].r=merge(tree[a].r,b);
} else {
tree[now]=tree[b];
tree[now].l=merge(a,tree[b].l);
}
push_up(now);
return now;
}
int get_rank(int index,int v) {
if(!index)return 0;
if(v<val(index))return get_rank(tree[index].l,v);
else return size(tree[index].l)+1+get_rank(tree[index].r,v);
}
int insert(int index,int v) {
int k=get_rank(index,v);
pii tmp=split(index,k); //保证v的有序性
return merge(merge(tmp.first,newnode(v)),tmp.second);
}
int remove(int index,int v) {
int k=get_rank(index,v);
return merge(split(index,k-1).first,split(index,k).second);
}
LL query(int index,int k) {
if(!index||!k)return 0;
if(k<=size(tree[index].l))return query(tree[index].l,k);
else return tree[tree[index].l].sum+tree[index].val+query(tree[index].r,k-size(tree[index].l)-1);
}
} bbt;
int n,q,root[maxn];
LL lastans=1;
vector<pii>a[maxn];
int main() {
srand(time(NULL));
n=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++) {
int l=Get_Int(),r=Get_Int(),v=Get_Int();
a[l].push_back(mp(1,v));
a[r+1].push_back(mp(-1,v));
}
for(int i=1; i<=q; i++) {
root[i]=root[i-1];
for(pii tmp:a[i]) {
int opt=tmp.first,v=tmp.second;
if(opt==1)root[i]=bbt.insert(root[i],v);
else root[i]=bbt.remove(root[i],v);
}
}
while(q--) {
int x=Get_Int(),a=Get_Int(),b=Get_Int(),c=Get_Int();
int k=1+(lastans*a+b)%c;
if(k>=bbt.tree[root[x]].size)lastans=bbt.tree[root[x]].sum;
else lastans=bbt.query(root[x],k);
printf("%lld\n",lastans);
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%