题意:给n个人 每个人有一个值a[i] 属于b[i]组 有q次询问
每次询问让第c个人变成d组 问每次改变后 每个组中的最大值中的最小值为多少
题目链接:https://atcoder.jp/contests/abc170/tasks/abc170_e
思路:纯模拟题 但是要熟悉multiset 的用法 还有一些rbegin和begin的使用 用multiset 来存每个集合
再用一个多集来存最大值 每次改变后只需要看 原集合中的被改变的数是不是最大值
还有 改变的集合的最大值是不是大于 这个插进去的数 要注意都要判断一下s[i].size()为0的情况
由于map和set都是红黑树来实现 所以查询和删除复杂度都为logn
时间复杂度 Nlognlogn q次询问+删除+查询
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define pb push_back 5 const int maxn =2e5+10; 6 const int mod=1e9+7; 7 multiset<int>s[maxn]; 8 multiset<int>max1; 9 int a[maxn]; 10 int b[maxn]; 11 int f[maxn]; 12 13 14 int main() 15 { 16 ios::sync_with_stdio(false); 17 cin.tie(0); 18 int n,q; 19 cin>>n>>q; 20 for(int i=1;i<=n;i++) 21 { 22 cin>>a[i]>>b[i]; 23 s[b[i]].insert(a[i]); 24 f[i]=b[i]; 25 } 26 for(int i=1;i<maxn;i++) 27 { 28 if(s[i].size()) 29 max1.insert(*s[i].rbegin()); 30 } 31 while(q--) 32 { 33 int c,d; 34 cin>>c>>d; 35 int p=f[c]; 36 f[c]=d; 37 s[p].erase(s[p].find(a[c])); 38 if((s[p].size()==0)||(a[c]>*s[p].rbegin())) 39 { 40 max1.erase(max1.find(a[c])); 41 if(s[p].size()) 42 { 43 max1.insert(*s[p].rbegin()); 44 } 45 } 46 if((s[d].size()==0)||(a[c]>*s[d].rbegin())) 47 { 48 if(s[d].size()) 49 max1.erase(max1.find(*s[d].rbegin())); 50 max1.insert(a[c]); 51 } 52 s[d].insert(a[c]); 53 cout<<*max1.begin()<<'\n'; 54 } 55 56 57 58 59 60 61 62 63 }View Code