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

发表于 更新于 分类于 阅读次数：
priority_queue和multiset异同以及线段树树空树插入维护初见 [HDU-6609] 2019航电多校3-1007

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