【小DS】ABC253 C - Max - Min Query

谁践踏了优雅 2024-03-23 14:26 57阅读 0赞

**我到今天才知道set原来是这么用的**

[C - Max - Min Query (atcoder.jp)][C - Max - Min Query _atcoder.jp]

题意：

![fe6de202db4941ce95e36bb9421d3ed8.png][]

思路：

因为是修改和询问，考虑DS

首先看需要维护的是什么，是集合里最大值和最小值

然后考虑修改操作，把min(c,x的次数)的x从集合里删除

因为是多次删除，怕超时（事实上不会），又要维护它存不存在，因此加个维护的东西：每个数出现的次数

所以考虑在set里放pair

操作1就是把原来的erase掉，次数加上去后再insert

操作2就是删除旧的，修改出现次数后换成新的

操作3就直接输出就行，值得注意的是set最大值和最小值的写法，最大值应该是\*prev(S.end())，而不是(\*S.end())，end是到不了的

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e3+10;
    const int mxe=2e5+10;
    const int Inf=1e18;
    const int mod=998244353;
    
    map<int,int> mp;
    set<pair<int,int> > S;
    int Q;
    int op,x,c;
    void solve(){
    	cin>>Q;
    	while(Q--){
    		cin>>op;
    		if(op==1){
    			cin>>x;
    			if(mp.count(x)){
    				S.erase({x,mp[x]});
    				mp[x]++;
    				S.insert({x,mp[x]});
    			}else{
    				mp[x]++;
    				S.insert({x,mp[x]});
    			}
    		}else if(op==2){
    			cin>>x>>c;
    			if(mp[x]<=c){
    				S.erase({x,mp[x]});
    				mp[x]=0;
    			}else{
    				S.erase({x,mp[x]});
    				mp[x]-=c;
    				S.insert({x,mp[x]});
    			}
    		}else if(op==3){
    			cout<<(*prev(S.end())).first-(*S.begin()).first<<'\n';
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[C - Max - Min Query _atcoder.jp]: https://atcoder.jp/contests/abc253/tasks/abc253_c
[fe6de202db4941ce95e36bb9421d3ed8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/69230b41092c4d09ad8b44c0557afa17.png