fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define pp push_back
  5. #define endl '\n'
  6. #define all(x) x.begin(),x.end()
  7. #define ld long double
  8. #define PI acos(-1)
  9. #define ones(x) __builtin_popcountll(x)
  10. //#define int ll
  11.  
  12. using namespace std;
  13.  
  14. void Drakon() {
  15.     ios_base::sync_with_stdio(false);
  16.     cin.tie(nullptr);
  17.     cout.tie(nullptr);
  18. #ifdef Clion
  19.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  20. #endif
  21. }
  22.  
  23. unsigned long long inf = 1e10;
  24. const double EPS = 1e-6;
  25. const int MOD = 1000000007, N = 200005, LOG = 25;
  26.  
  27. ll mul(const ll &a, const ll &b) {
  28.     return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
  29. }
  30.  
  31. ll add(const ll &a, const ll &b) {
  32.     return (a + b + 2 * MOD) % MOD;
  33. }
  34.  
  35. ll pw(ll x, ll y) {
  36.     ll ret = 1;
  37.     while (y > 0) {
  38.         if (y % 2 == 0) {
  39.             x = mul(x, x);
  40.             y = y / 2;
  41.         } else {
  42.             ret = mul(ret, x);
  43.             y = y - 1;
  44.         }
  45.     }
  46.     return ret;
  47. }
  48.  
  49. struct seg {
  50.     int mx = -1, sum = 0;
  51.  
  52.     seg() {
  53.  
  54.     }
  55.  
  56.     seg(int mx, int sum) {
  57.         this->mx = mx;
  58.         this->sum = sum;
  59.     }
  60. };
  61.  
  62. struct segtree {
  63.  
  64.     vector<seg> values;
  65.     int size = 1, n;
  66.  
  67.     void init(int nn) {
  68.         n = nn;
  69.         while (size < nn)size *= 2;
  70.         values.resize(2 * size, seg());
  71.     }
  72.  
  73.     seg mrg(seg &a, seg &b) {
  74.         seg c;
  75.         c.mx = max(a.mx, b.mx);
  76.         c.sum = a.sum + b.sum;
  77.         return c;
  78.     }
  79.  
  80.     void update(int i, int mx, int sum, int x, int lx, int rx) {
  81.  
  82.         if (lx == rx) {
  83.             values[x].mx = mx;
  84.             values[x].sum = sum;
  85.             return;
  86.         }
  87.         int mid = (lx + rx) / 2;
  88.         if (i <= mid)
  89.             update(i, mx, sum, 2 * x + 1, lx, mid);
  90.         else
  91.             update(i, mx, sum, 2 * x + 2, mid + 1, rx);
  92.         values[x] = mrg(values[2 * x + 1], values[2 * x + 2]);
  93.     }
  94.  
  95.     void update(int i, int mx, int sum) {
  96.         update(i, mx, sum, 0, 0, n - 1);
  97.     }
  98.  
  99.     seg query(int l, int r, int x, int lx, int rx) {
  100.  
  101.         if (l > rx || lx > r) {
  102.             return seg();
  103.         }
  104.         else if (lx >= l && rx <= r) {
  105.             return values[x];
  106.         }
  107.  
  108.         int mid = (lx + rx) / 2;
  109.         seg s1 = query(l, r, 2 * x + 1, lx, mid);
  110.         seg s2 = query(l, r, 2 * x + 2, mid + 1, rx);
  111.         return mrg(s1, s2);
  112.     }
  113.  
  114.     seg query(int l, int r) {
  115.         return query(l, r, 0, 0, n - 1);
  116.     }
  117.  
  118. };
  119.  
  120. void solve() {
  121.     int n, q;
  122.     cin >> n >> q;
  123.     vector<int> vec(n);
  124.     set<int> ind[n];
  125.     for (int i = 0; i < n; ++i) {
  126.         cin >> vec[i];
  127.         vec[i] --;
  128.         ind[vec[i]].insert(i);
  129.     }
  130.  
  131.     segtree stF, stL;
  132.     stF.init(n + 5);
  133.     stL.init(n + 5);
  134.     multiset<int> mnFS;
  135.     multiset<int, greater<>> mxLS;
  136.     for (int i = 0; i < n; ++i) {
  137.         if(!ind[i].empty()) {
  138.             int first = *ind[i].begin();
  139.             int last = *ind[i].rbegin();
  140.             stF.update(first, last, ind[i].size() - 1);
  141.             stL.update(last, first, ind[i].size() - 1);
  142.         }
  143.         if(ind[i].size() > 1) {
  144.             mnFS.insert(*++ind[i].begin());
  145.             mxLS.insert(*--ind[i].rbegin());
  146.         }
  147.     }
  148.  
  149.     while (q --) {
  150.         int op;
  151.         cin >> op;
  152.         if(op == 1) {
  153.             int t, i;
  154.             cin >> t >> i;
  155.             t--, i--;
  156.  
  157.             int cur = vec[i];
  158.  
  159.             if(!ind[cur].empty()) {
  160.                 auto fi = ind[cur].begin();
  161.                 auto la = ind[cur].rbegin();
  162.  
  163.                 stF.update(*fi, -1, 0);
  164.                 stL.update(*la, -1, 0);
  165.                 if(ind[cur].size() > 1) {
  166.                     mnFS.erase(mnFS.find(*next(fi)));
  167.                     mxLS.erase(mxLS.find(*prev(la)));
  168.                 }
  169.             }
  170.             ind[cur].erase(i);
  171.             if(!ind[cur].empty()) {
  172.                 auto fi = ind[cur].begin();
  173.                 auto la = ind[cur].rbegin();
  174.  
  175.                 stF.update(*fi, *la, ind[cur].size() - 1);
  176.                 stL.update(*la, *fi, ind[cur].size() - 1);
  177.                 if(ind[cur].size() > 1) {
  178.                     mnFS.insert(*next(fi));
  179.                     mxLS.insert(*prev(la));
  180.                 }
  181.             }
  182.  
  183.             vec[i] = t;
  184.             cur = vec[i];
  185.  
  186.             if(!ind[cur].empty()) {
  187.                 auto fi = ind[cur].begin();
  188.                 auto la = ind[cur].rbegin();
  189.  
  190.                 stF.update(*fi, -1, 0);
  191.                 stL.update(*la, -1, 0);
  192.                 if(ind[cur].size() > 1) {
  193.                     mnFS.erase(mnFS.find(*next(fi)));
  194.                     mxLS.erase(mxLS.find(*prev(la)));
  195.                 }
  196.             }
  197.             ind[cur].insert(i);
  198.             if(!ind[cur].empty()) {
  199.                 auto fi = ind[cur].begin();
  200.                 auto la = ind[cur].rbegin();
  201.  
  202.                 stF.update(*fi, *la, ind[cur].size() - 1);
  203.                 stL.update(*la, *fi, ind[cur].size() - 1);
  204.                 if(ind[cur].size() > 1) {
  205.                     mnFS.insert(*next(fi));
  206.                     mxLS.insert(*prev(la));
  207.                 }
  208.             }
  209.         }
  210.         else {
  211.             int t;
  212.             cin >> t;
  213.             t --;
  214.             if(ind[t].size() < 2) {
  215.                 cout << "-1\n";
  216.                 continue;
  217.             }
  218.             int l = *ind[t].begin();
  219.             int r = *ind[t].rbegin();
  220.             if((!mnFS.empty() && *mnFS.begin() < l)
  221.             || (!mxLS.empty() && *mxLS.begin() > r)
  222.             || (l && stF.query(0, l - 1).mx > r)) {
  223.                 cout << "-1\n";
  224.                 continue;
  225.             }
  226.             int ans = 0;
  227.             if(l) ans += stF.query(0, l - 1).sum;
  228.             if(r + 1 < n) ans += stL.query(r + 1, n - 1).sum;
  229.             cout << ans << endl;
  230.         }
  231.     }
  232.  
  233. }
  234.  
  235. signed main() {
  236.     Drakon();
  237.     int t = 1;
  238.     //cin >> t;
  239.     while (t--) {
  240.         solve();
  241.     }
  242. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zceIH2
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!