【小DS】代码源每日一题div2 上帝的集合

╰+攻爆jí腚メ 2024-03-16 18:37 25阅读 0赞

根本不会

[上帝的集合 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![110f019cb5fa4bd7bb46788f8d1dac7a.png][]

![3a30009d3ec34471bdae844f4097b5b2.png][]

思路：

DS题

首先看我们需要维护的是什么，是集合中最小的数，这个用优先队列就可以轻松维护

然后去看修改操作对需要维护的东西的影响，全体加上x，那么最小值就+x

那么可以加一个维护的东西：加一个变量add，维护我们对这个集合一共加的值，输出的时候加上add即可

还有一个操作：插入一个数，这个对最小值的影响是什么呢？这个优先队列就解决了，但是麻烦的是询问的时候，我们并没有对其加上add，因此在插入的时候要减去在这个数加入之前的add

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    
    priority_queue<int,vector<int>,greater<int> > Q;
    
    int N,x,op,add=0;
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++){
    		cin>>op;
    		if(op==1){
    			cin>>x;
    			Q.push(x-add);
    		}else if(op==2){
    			cin>>x;
    			add+=x;
    		}else{
    			cout<<Q.top()+add<<'\n';
    			Q.pop();
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/736
[110f019cb5fa4bd7bb46788f8d1dac7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d634c21b20c9442aa0abac110dcd1a73.png
[3a30009d3ec34471bdae844f4097b5b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6b314f5e47b54a00bd21cd1b0ee798f8.png