fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define pii pair<int,int>
  5. #define fi first
  6. #define se second
  7. #define el '\n'
  8. const ll maxN = 1e6;
  9. int n, query;
  10. int a[maxN+5];
  11.  
  12.  
  13.  
  14. namespace subtask1
  15. {
  16.     ll C2(int N)
  17.     {
  18.         return (ll) N*(N-1)/2;
  19.     }
  20.  
  21.     ll cal(int L, int R)
  22.     {
  23.         map<int,int> dd;
  24.         int len = R-L+1;
  25.         for(int i=L; i<=R; i++) dd[a[i]]++;
  26.         ll res = 0;
  27.         for(pii c : dd)
  28.         {
  29.             res+= C2(c.se);
  30.         }
  31.         return (ll)(1 + C2(len) - res);
  32.     }
  33.  
  34.     set<pii> seg;
  35.     multiset<ll> val;
  36.     void solve()
  37.     {
  38.         seg.insert({1,n});
  39.         val.insert(cal(1,n));
  40.         while(query--)
  41.         {
  42.             int pos; cin >> pos;
  43.             auto it = seg.upper_bound({pos,(int)1e9});
  44.             it--;
  45.             int L = it -> fi;
  46.             int R = it -> se;
  47.             val.erase(val.find(cal(L,R)));
  48.             seg.erase(it);
  49.             if(L<=pos-1) 
  50.             {
  51.                 val.insert(cal(L,pos-1));
  52.                 seg.insert({L, pos - 1});
  53.             }
  54.             if(pos+1<=R)
  55.             {
  56.                 val.insert(cal(pos+1,R));
  57.                 seg.insert({pos+1,R});
  58.             }
  59.             if(val.empty()) cout<<0<<el;
  60.             else cout<<*val.rbegin()<<el;
  61.         }
  62.     }    
  63. }
  64. namespace subtask2
  65. {
  66.     int sz[maxN+5], par[maxN+5], alive[maxN+5];
  67.     int Query[maxN+5];
  68.     ll bad[maxN+5];
  69.     multiset<ll> val;
  70.     unordered_map<int,int> cnt[maxN+5];
  71.     ll ans[maxN+5];
  72.  
  73.     ll C2(ll N)
  74.     {
  75.         return N*(N-1)/2;
  76.     }
  77.  
  78.     int findroot(int u)
  79.     {
  80.         if(u == par[u]) return u;
  81.         return par[u] = findroot(par[u]);
  82.     }
  83.  
  84.     ll cal(int u)
  85.     {
  86.         u = findroot(u);
  87.         return 1LL + C2(sz[u]) - bad[u];
  88.     }
  89.  
  90.     void add_val(int u)
  91.     {
  92.         u = findroot(u);
  93.         val.insert(cal(u));
  94.     }
  95.  
  96.     void del_val(int u)
  97.     {
  98.         u = findroot(u);
  99.         val.erase(val.find(cal(u)));
  100.     }
  101.  
  102.     void dsu(int u, int v)
  103.     {
  104.         u = findroot(u);
  105.         v = findroot(v);
  106.  
  107.         if(u == v) return;
  108.  
  109.         if(cnt[u].size() < cnt[v].size())
  110.             swap(u,v);
  111.  
  112.         del_val(u);
  113.         del_val(v);
  114.  
  115.         par[v] = u;
  116.  
  117.         sz[u] += sz[v];
  118.  
  119.         for(auto f : cnt[v])
  120.         {
  121.             int num = f.fi;
  122.             int sl = f.se;
  123.             bad[u] -= C2(cnt[u][num]);
  124.             cnt[u][num] += sl;
  125.             bad[u] += C2(cnt[u][num]);
  126.         }
  127.  
  128.         add_val(u);
  129.     }
  130.  
  131.     void solve()
  132.     {
  133.  
  134.         for(int i=1; i<=n; i++)
  135.         {
  136.             par[i] = i;
  137.             sz[i] = 1;
  138.             alive[i] = 1;
  139.         }
  140.  
  141.  
  142.         for(int i=1; i<=query; i++)
  143.         {
  144.             cin >> Query[i];
  145.             alive[Query[i]] = 0;
  146.         }
  147.  
  148.  
  149.         for(int i=1; i<=n; i++)
  150.         {
  151.             if(alive[i])
  152.             {
  153.                 cnt[i][a[i]] = 1;
  154.                 bad[i] = 0;
  155.  
  156.                 add_val(i);
  157.             }
  158.         }
  159.         for(int i=1; i<n; i++)
  160.         {
  161.             if(alive[i] && alive[i+1])
  162.                 dsu(i,i+1);
  163.         }
  164.         for(int i=query; i>=1; i--)
  165.         {
  166.             if(val.empty()) ans[i] = 0;
  167.             else ans[i] = *val.rbegin();
  168.             int u = Query[i];
  169.             alive[u] = 1;
  170.             par[u] = u;
  171.             sz[u] = 1;
  172.             bad[u] = 0;
  173.             cnt[u].clear();
  174.             cnt[u][a[u]] = 1;
  175.             add_val(u);
  176.             if(u > 1 && alive[u-1])
  177.                 dsu(u,u-1);
  178.             if(u < n && alive[u+1])
  179.                 dsu(u,u+1);
  180.         }
  181.         for(int i=1; i<=query; i++)
  182.             cout << ans[i] << el;
  183.     }
  184. };
  185.  
  186. int main()
  187. {
  188.     ios_base::sync_with_stdio(0); cin.tie(0);
  189.     freopen("TET.INP","r",stdin);
  190.     freopen("TET.OUT","w",stdout);
  191.     cin >> n >> query;
  192.     for(int i=1; i<=n; i++) cin >> a[i];
  193.     if(n<=5000)subtask1::solve();
  194.     else subtask2::solve();
  195.     return 0;
  196. }
  197.  
Success #stdin #stdout 0.02s 61228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2U3Nse
language:
C++ (gcc 8.3)
created:
4 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!