SHARE
TWEET

LUK FQ U

lizazhemchuzhina Nov 9th, 2019 (edited) 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <unordered_map>
  2. #include <set>
  3. #include <queue>
  4. #include <iostream>
  5. #include <functional>
  6. using namespace std;
  7.  
  8. const int N = 300005;
  9. int arr[N];
  10. unordered_map <int, set<int>>h(N);
  11. priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> add, del;
  12.  
  13. int main()
  14. {
  15.     int n, q;
  16.     cin >> n;
  17.     for (int i = 0; i < n; i++)
  18.     {
  19.         cin >> arr[i];
  20.         h[arr[i]].insert(i);
  21.     }
  22.     for (auto i : h)
  23.         add.push({ i.second.size(), *(i.second.begin()) });
  24.    
  25.     cin >> q;
  26.     char c;
  27.     int index, y;
  28.     for (int i = 0; i < q; i++)
  29.     {
  30.         cin >> c;
  31.         if (c == '?')
  32.             cout << add.top().second <<'\n';
  33.         else
  34.         {
  35.             cin >> index >> y;
  36.             del.push({h[arr[index]].size(),*(h[arr[index]].begin()) });
  37.             h[arr[index]].erase(index);
  38.             if (!h[arr[index]].empty())
  39.                 add.push({ h[arr[index]].size(), *(h[arr[index]].begin()) });
  40.            
  41.             arr[index] = y;
  42.             if (!h[arr[index]].empty())
  43.                 del.push({ h[arr[index]].size(), *(h[arr[index]].begin()) });
  44.  
  45.             h[arr[index]].insert(index);
  46.             add.push({ h[arr[index]].size(), *(h[arr[index]].begin()) });
  47.  
  48.                 while ((!add.empty()) && (!del.empty()) && add.top() == del.top())
  49.                 {
  50.                     add.pop();
  51.                     del.pop();
  52.                 }
  53.         }
  54.     }
  55.     return 0;
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top