Advertisement
BaoJIaoPisu

Untitled

Aug 30th, 2021
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.53 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pb push_back
  5. #define pf push_front
  6. #define popb pop_back
  7. #define popf pop_front
  8. #define ins insert
  9. #define pq priority_queue
  10. #define minele min_element
  11. #define maxele max_element
  12. #define lb lower_bound //first pos >= val
  13. #define ub upper_bound // first pos > val
  14. #define cnt_bit __builtin_popcount
  15. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  16. //#pragma GCC optimize("Ofast")
  17. //#pragma GCC target("avx,avx2,fma")
  18. using namespace std;
  19.  
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21.  
  22. typedef long long ll;
  23. typedef pair<ll, ll> pll;
  24. typedef pair<int, int> pii;
  25.  
  26.  
  27. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  28. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  29. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  30.  
  31. const ll oo = 1e18;
  32. const ll maxN = 1e5 + 10;
  33.  
  34. /* Author : Le Ngoc Bao Anh, 10A5, LQD High School for Gifted Student */
  35.  
  36. void maximize(int &a, int b) {
  37.     a = max(a, b);
  38. }
  39.  
  40. void minimize(int &a, int b) {
  41.     a = min(a, b);
  42. }
  43.  
  44. set<int> pos[maxN];
  45. int a[maxN];
  46.  
  47. void solve() {
  48.     int n; cin >> n;
  49.     for(int i = 1; i <= n; i++) {
  50.         cin >> a[i];
  51.         pos[a[i]].ins(i);
  52.     }
  53.  
  54.     for(int i = 1; i <= 1e5; i++) {
  55.         pos[i].ins(0); pos[i].ins(n + 1);
  56.     }
  57.  
  58.     auto cost = [&](int len) -> ll {
  59.         return 1ll * len * (len - 1) / 2 + len;
  60.     };
  61.  
  62.     ll ans = 0;
  63.     auto f = [&]() -> void {
  64.         const int mxN = 1e5;
  65.         for(int i = 1; i <= mxN; i++) {
  66.             if(pos[i].size() < 2) continue;
  67.             ans += cost(n);
  68.             int p = 0;
  69.             for(auto id : pos[i]) {
  70.                 if(id == 0) continue;
  71.                 int x = id - p - 1;
  72.                 ans -= cost(x);
  73.                 p = id;
  74.             }
  75.         }
  76.     };
  77.  
  78.     f();
  79.  
  80.     int q; cin >> q;
  81.     while(q--) {
  82.         int d, val; cin >> d >> val;
  83.        
  84.         int k = a[d];
  85.         auto it = pos[k].find(d);
  86.         int x = *(--it);
  87.         it++; it++;
  88.         int y = *(it);
  89.         pos[k].erase(--it);
  90.        
  91.         ans += cost(d - x - 1);
  92.         ans += cost(y - d - 1);
  93.         ans -= cost(y - x - 1);
  94.  
  95.        
  96.         pos[val].ins(d);
  97.         a[d] = val;
  98.         it = pos[val].find(d);
  99.         x = *(--it);
  100.         it++; it++;
  101.         y = *(it);
  102.        
  103.         ans += cost(y - x - 1);
  104.         ans -= cost(d - x - 1);
  105.         ans -= cost(y - d - 1);
  106.  
  107.         cout << ans << "\n";
  108.     }
  109. }
  110.  
  111. int main()
  112. {
  113.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  114.     #ifndef ONLINE_JUDGE
  115.     freopen("input.txt", "r", stdin);
  116.     freopen("output.txt", "w", stdout);
  117.     #else
  118.     //online
  119.     #endif
  120.  
  121.     int tc = 1, ddd = 0;
  122.     // cin >> tc;
  123.     while(tc--) {
  124.         //ddd++;
  125.         //cout << "Case #" << ddd << ": ";
  126.         solve();
  127.     }
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement