fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define TIME (1.0* clock()/CLOCKS_PER_SEC)
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define id1 (id<<1)
  6. #define id2 (id<<1)|1
  7. #define ll long long
  8. #define ii pair<int,int>
  9. #define vi vector<int>
  10. #define vii vector<pair<int,int>> 
  11. #define vl vector<long long>
  12. #define vll vector <pair<ll,ll>>
  13. #define li pair<long long,int>
  14. #define vil vector <pair<int,ll>>
  15. #define db double
  16. #define ff first
  17. #define ss second
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define FOR(i, a, b) for (int i = (a); i <=(b); i++)
  21. #define F0R(i, a) FOR(i, 0, a-1)
  22. #define ROF(i, a, b) for (int i = (b); i >= (a); i--)
  23. #define R0F(i, a) ROF(i, 0, a-1)
  24. #define rep(a) F0R(_, a)
  25. #define each(a, x) for (auto &a : x)
  26. #define ALL(x) (x).begin(),(x).end()
  27. #define pq priority_queue <li, vector <li>, greater <li>> 
  28. using namespace std;
  29. const int maxn=6e5+5;
  30. const int MAXQ=3e5+5;
  31. //const int MOD=1e9+7;
  32. //const int MOD=998244353;
  33. //const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
  34. #define int long long
  35.  
  36. int n = 300000; 
  37. int q;
  38. ll ans=0;
  39.  
  40. struct DSU {
  41.     vi parent;
  42.     vl cntX, cntY;
  43.     vii history;
  44.  
  45.     DSU(int size) {
  46.         parent.resize(size + 1);
  47.         cntX.resize(size + 1, 0);
  48.         cntY.resize(size + 1, 0);
  49.  
  50.         FOR(i,1,n) {
  51.             parent[i] = i;
  52.             cntX[i] = 1;
  53.             cntY[i] = 0;
  54.         }
  55.         FOR(i,n+1,2*n) {
  56.             parent[i] = i;
  57.             cntX[i] = 0;
  58.             cntY[i] = 1;
  59.         }
  60.     }
  61.  
  62.     int find(int x) {
  63.         while (parent[x] != x) x = parent[x];
  64.         return x;
  65.     }
  66.  
  67.     bool unite(int x, int y) {
  68.         x = find(x);
  69.         y = find(y);
  70.         if (x == y) return false;
  71.  
  72.         if (cntX[x] + cntY[x] < cntX[y] + cntY[y]) {
  73.             swap(x, y);
  74.         }
  75.  
  76.         history.pb({x, y});
  77.  
  78.         ans -= cntX[x] * cntY[x] + cntX[y] * cntY[y];
  79.  
  80.         cntX[x] += cntX[y];
  81.         cntY[x] += cntY[y];
  82.         parent[y] = x;
  83.  
  84.         ans += cntX[x] * cntY[x];
  85.  
  86.         return true;
  87.     }
  88.  
  89.     void rollback(int checkpoint) {
  90.         while ((int)history.size() > checkpoint) {
  91.             auto [x, y] = history.back();
  92.             history.pop_back();
  93.  
  94.             ans -= cntX[x] * cntY[x];
  95.  
  96.             cntX[x] -= cntX[y];
  97.             cntY[x] -= cntY[y];
  98.             parent[y] = y;
  99.  
  100.             ans += cntX[x] * cntY[x] + cntX[y] * cntY[y];
  101.         }
  102.     }
  103.  
  104.     int getCheckpoint() {
  105.         return history.size();
  106.     }
  107. };
  108.  
  109. vector<ii> st[4 * MAXQ];
  110.  
  111. void addEdge(int id, int l, int r, int u, int v, ii edge) {
  112.     if (u > r || v < l) return;
  113.     if (u <= l && r <= v) {
  114.         st[id].pb(edge);
  115.         return;
  116.     }
  117.     int mid = (l + r) >> 1;
  118.     addEdge(id1, l, mid, u, v, edge);
  119.     addEdge(id2, mid+1, r, u, v, edge);
  120. }
  121.  
  122. void solve(int id, int l, int r, DSU &dsu) {
  123.     int checkpoint = dsu.getCheckpoint();
  124.     for (auto &edge : st[id]) {
  125.         dsu.unite(edge.ff, edge.ss);
  126.     }
  127.  
  128.     if (l == r) {
  129.  
  130.         cout << ans << " ";
  131.     } else {
  132.         int mid = (l + r) >> 1;
  133.         solve(id1, l, mid, dsu);
  134.         solve(id2, mid+1, r, dsu);
  135.     }
  136.  
  137.  
  138.     dsu.rollback(checkpoint);
  139. }
  140.  
  141. void solve(){
  142.     cin >> q;
  143.  
  144.  
  145.     FOR(i,0,4*(q+1)) st[i].clear();
  146.  
  147.     map<ii, int> startTime;
  148.     DSU dsu(maxn);
  149.  
  150.  
  151.     FOR(i,1,q) {
  152.         int x, y;
  153.         cin >> x >> y;
  154.         ii point = {x, y + n}; 
  155.  
  156.         if (startTime.count(point)) {
  157.             addEdge(1, 1, q, startTime[point], i - 1, point);
  158.             startTime.erase(point);
  159.         } else {
  160.             startTime[point] = i;
  161.         }
  162.     }
  163.     for (auto &[point, start] : startTime) {
  164.         addEdge(1, 1, q, start, q, point);
  165.     }
  166.     solve(1, 1, q, dsu);
  167.     cout << endl;
  168. }
  169.  
  170. signed main(){
  171.     ios_base::sync_with_stdio(false);
  172.     cin.tie(NULL);cout.tie(NULL);
  173.     if (fopen("TASK.INP", "r")){
  174.         freopen("TASK.INP", "r", stdin);
  175.         freopen("TASK.OUT", "w", stdout);
  176.     }
  177.     int ntest;
  178.     ntest=1;
  179.     //cin>>ntest;
  180.  
  181.     FOR(i,1,ntest) solve();
  182.     cerr<<"\n"<<"Time elapsed "<<TIME<<"s.\n";
  183.     return 0;
  184. }
Success #stdin #stdout #stderr 0.02s 45364KB
comments (?)
stdin
copy 
7
1 1
1 2
2 1
2 2
1 2
1 3
2 1
stdout
copy 
1 2 4 4 4 6 3
stderr
copy 
Time elapsed 0.01937s.
https://ideone.com/qIsJQ8
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!