fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. typedef long long ll;
  5. #define s second
  6. #define f first
  7.  
  8. const int N = 2e5 + 10;
  9. int ask[N], ok[N], sz[N], a[N], par[N];
  10. map <int, int> mp[N];
  11. ll cnt[N], tt[N];
  12.  
  13. int get(int x) {
  14.     return par[x] ? get(par[x]) : x;
  15. }
  16.  
  17. ll ans = 0;
  18.  
  19. // mp[y][x] là số lần xuất hiện của giá trị x trong tplt y.
  20.  
  21.  
  22. void unite(int x, int y) {
  23.     x = get(x), y = get(y);
  24.     if (x == y)
  25.         return;
  26.  
  27.     ll tot = cnt[x] + cnt[y] + (ll)sz[x] * (ll)sz[y];
  28.     if (sz[x] > sz[y])
  29.         swap(x, y);
  30.  
  31.     for (auto t : mp[x]) {
  32.         tot -= (ll)t.s * mp[y][t.f];
  33.     }
  34.  
  35.     for (auto t : mp[x]) {
  36.         mp[y][t.f] += t.s;
  37.     }
  38.  
  39.     par[x] = y;
  40.     sz[y] += sz[x];
  41.     cnt[y] = tot;
  42.     ans = max(ans, tot);
  43. }
  44.  
  45. int main() {
  46.     ios_base::sync_with_stdio(0);
  47.     cin.tie(0);
  48.     cout.tie(0);
  49.  
  50.     freopen("tet.inp", "r", stdin);
  51.     freopen("tet.out", "w", stdout);
  52.     int n, q;
  53.     cin >> n >> q;
  54.  
  55.     for (int i = 1; i <= n; i++) {
  56.         cin >> a[i];
  57.         ok[i] = 1;
  58.     }
  59.  
  60.     for (int i = 1; i <= q; i++) {
  61.         cin >> ask[i];
  62.         ok[ask[i]] = 0;
  63.     }
  64.  
  65.     for (int i = 1; i <= n; i++) {
  66.         if (ok[i]) {
  67.             mp[i][a[i]]++;
  68.             sz[i] = 1;
  69.         }
  70.     }
  71.  
  72.     for (int i = 1; i <= n; i++) {
  73.         if (ok[i] && ok[i + 1]) {
  74.             unite(i, i + 1);
  75.         }
  76.     }
  77.  
  78.     tt[q] = ans + 1;
  79.     for (int i = q; i >= 2; i--) {
  80.         int p = ask[i];
  81.         sz[p] = 1;
  82.         mp[p][a[p]]++;
  83.         if (ok[p + 1]) {
  84.             unite(p, p + 1);
  85.         }
  86.  
  87.         if (ok[p - 1]) {
  88.             unite(p - 1, p);
  89.         }
  90.  
  91.         ok[p] = 1;
  92.         tt[i - 1] = ans + 1;
  93.     }
  94.  
  95.     for (int i = 1; i <= q; i++)
  96.         cout << tt[i] << '\n';
  97.  
  98.     return 0;
  99. }
  100.  
Success #stdin #stdout 0.01s 18100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7nJfHd
language:
C++14 (gcc 8.3)
created:
2 days 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!