priority_queue和multiset异同以及线段树空树插入维护初见

priority_queue和multiset异同

优先级队列只能按照排序顺序访问一个元素 - 即,可以获得最高优先级的项目,想要访问其他的元素,就必须删除顶端元素。 优先级队列还允许重复元素,因此它很像是一个multiset。

但是multiset比priority_queue的好处就在于multiset不用删除掉优先级最高的元素就可以访问其他优先级的元素,就相当于一个动态的有序数组

同为log(n)插入,但是multiset却能访问更多,真香

虽然priority_queue可以通过删除再恢复的方式达到访问其他优先级的元素,但是实现很不优雅,而且让一个log(n)的操作蹩脚地魔改成了接近O(n^2)的操作,并且容易卡时间

比如HDU-6609这一题

暴力priority_queue

虽然我很不愿意把我很喜欢的一种STL加上暴力的前缀,但是确实是很朴素自然,大道至简但是这里有点过分使用了…所以下面是TLE的代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int inf = 0x3f3f3f3f;
const int M = 2e5 + 7 ;
int Q, n, m, w[M];
ll sum;
int k;
priority_queue<int,vector<int>,greater<int>> pre;
priority_queue<int,vector<int>,less<int>> q;

int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>Q;
while(Q--){
/* init */
sum = 0;k=0;
while(!q.empty()) q.pop();
while(!pre.empty()) pre.pop();
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n;i++){
/* 根据题意不能弹出本次加入的 */
/* 根据题意应该不会在空的时候满足条件 */
// int pre=inf;
/*每弹出一个k++,所以每回收pre一个k--*/
// while(!pre.empty()) pre.pop();
while(!q.empty()&&sum+w[i]>m){
k++;
pre.push(q.top());
sum-=q.top();
q.pop();
}
/*输出*/
cout<<k<<" ";
if(i==n){ cout<<endl; break; }
/*回溯*/
ll tmp = 0;
/* = 再想想*/
bool f=0;
while(!pre.empty()&&tmp+pre.top()<=w[i]){
f=1;
tmp += pre.top();
q.push(pre.top());
k--;
pre.pop();
}
/*能加入一个就无需加本身了,要加回之前的sum值
本身未加入的话就相当于弹出了一个k++*/
/*不对,加回本身,让其在后面的循环中进入pre*/
// if(f) sum += tmp,k++;
if(f) sum += tmp;
q.push(w[i]);
sum += w[i];
}
}

return 0;
}

multiset

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
#include<iostream>
#include<set>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
multiset<int> ss;

int main(){
int t;
scanf("%d", &t);
while (t--) {
ss.clear();
long long int n, m;
scanf("%lld%lld", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
long long int sum = 0;
int tem = 0;
for (int i = 0; i < n; i++) {
long long int suma = sum;
int jishu = 0;
if (suma + a[i] > m) {
auto j = ss.end();
/* 这里用计数jishu记下软删除的数量,由于priority_queue
只能访问第一个值,所以不支持软硬删除操作...所以会用真实删除再
恢复的操作会TLE...因为这样会从O(nlog(n))魔化到O(n^2) */
/* 由题意a[i]<=m,满足下面条件时一定不会出现ss为空 */
while (suma + a[i] > m) {
j--;
suma -= *j;
jishu++;
}
}
/* 第一个铁定是0的 */
printf("%d ", jishu + tem);
ss.insert(a[i]);
auto j = ss.end();
sum += a[i];
/* 用tem记录下硬删除的数量 */
while (sum > m) {
j--;
sum -= *j;
/* 这里由于find返回的是指针,所以就会只删除一个值
而不是删除数值那样把所有数值都删除掉 */
ss.erase(ss.find(*j));
tem++;
}
}
printf("\n");
}
}

线段树树空树插入维护初见

这个线段树标程真是魔鬼一般地折磨了我整整7个小时…菜鸡刚学线段树,还没有过插入空树的经历,然后这个std是插入空树…我好菜啊

所以放一发带思考注释的手抄代码

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
#include<bits/stdc++.h>
using namespace std;
#define mod 1e9+7
#define ll long long
const int M = 2e5+7;
ll int a[M],number[M<<2],bz[M<<2];
int number2[M<<2],bz2[M<<2],to[M];
struct node{
int id;
ll b;
} no[M];

bool cmp(node a,node b){
return a.b==b.b ? a.id<b.id : a.b<b.b;
}

/* 自己重写std感觉上推数值好像还是不对,如果不理解的话,下次就算有板子也不能秒掉!
所以还是要先理解一下 ,多多重现算法*/
/* 先写着,等下写完全部看看有没有新的认识 */
/* 2019年7月30日16:59:35 还是不懂,维护区间之和难道不是要左右相加吗?

2019年7月30日20:34:57 突然灵光一闪!
因为你一开始是一棵空树,然后你一个个插入,如果使用的是max,就相当于(to[i],n+1)这个区间以及每个子区间
都是你的插入值的和. 因为都是直接到了叶子节点去加和

如果使用加法,那么就出错了,就有很多重复计算,所以说[1->n]区间就是最大的前缀和

所以询问的时候就可以直接加和*/
void PushUp(int rt){
number[rt] = max(number[rt<<1],number[rt<<1|1]);
}

/* 其实这里是多组测试的初始化0值 */
/* 但是number2不PushUp清零吗?这里好像有问题,但为什么std能AC
惊呆的发现竟然放在了pushdown下推标记的时候清零了...感觉线段树的写法真多*/
void build(int l,int r,int rt){
bz[rt]=bz2[rt]=number[rt]=0;
if(l==r){number2[rt]=0;return;}
int mid = (l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
PushUp(rt);
}

void pushdown(int l,int r,int rt){
if(bz[rt]){
bz[rt<<1] += bz[rt];
bz[rt<<1|1] += bz[rt];
number[rt<<1] += bz[rt];
number[rt<<1|1] += bz[rt];
bz[rt] = 0;
}
if(bz2[rt]){
bz2[rt<<1] += bz2[rt];
bz2[rt<<1|1] += bz2[rt];
number2[rt<<1] += bz2[rt];
number2[rt<<1|1] += bz2[rt];
bz2[rt] = 0;
}
}

void change(ll o,int L,int R,int l,int r,int rt){
if(L>R) return;
if(l==r){
number[rt]+=o;
/* 之前初始化成了0,所以这里可以这样...这个标程写得真随意... */
number2[rt]+=1;
return ;
}
/* 此节点(区段l,r)全被包含在内 */
if(L<=l && r<=R){
/* 先自己赋值,下推标记就直接给儿子赋值 */
number[rt]+=o;
bz[rt]+=o;
bz2[rt] += 1;
return ;
}
int mid = (l+r)>>1;
/* pushdown和PushUp都只管修改相邻层 */
pushdown(l,r,rt);
/* 区段l,r包含L,R,或者有交叠,则访问子节点(子区段) */
if(L<=mid) change(o,L,R,l,mid,rt<<1);
if(R>mid) change(o,L,R,mid+1,r,rt<<1|1);
PushUp(rt);
}

ll query(ll k,int l,int r,int rt){
if(l==r) return number2[rt];
int mid = (l+r)>>1;
pushdown(l,r,rt);
int ans;
if(k < number[rt<<1]) ans = query(k,l,mid,rt<<1);
else ans = query(k,mid+1,r,rt<<1|1);
PushUp(rt);
return ans;
}

int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d%d",&n,&m);
build(1,n+1,1);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
no[i].b = a[i];
no[i].id = i;
}
sort(no+1,no+n+1,cmp);
/* 把与n+1有关的节点都打上number=1e9,number2=1的标记...
只给n+1对应的叶子节点处打上了标记!其他地方没有进去过!
就相当于在那里插入了一点*/
change(1e9,n+1,n+1,1,n+1,1);
for(int i=1;i<=n;i++) to[no[i].id] = i;
for(int i=1;i<=n;i++){
/*一个个插入,第一个时还没插入,是空树,所以肯定返回0*/
ll k = query(m-a[i],1,n+1,1);
printf("%lld ",i-k);
/*按照队友的说法,那这里就是插入第一个*/
/* 给排名在to[i]到n+1的地方都所有区段打上区间数值和number
和此区间个数和number2 */
change(a[i],to[i],n+1,1,n+1,1);
}
puts("");
}
return 0;
}

借鉴:

C++&STL&multiset&杭电多校第三场 1007 find the answer