Advertisement
aayyk

Untitled

Oct 12th, 2020
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.14 KB | None | 0 0
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2.  
  3. #ifdef LOCAL
  4. #include "debug.h"
  5. #else
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. #define debug(x...)
  10. #endif
  11.  
  12. using namespace std;
  13.  
  14. //#define int ll
  15.  
  16. typedef long long ll;
  17. typedef long double ld;
  18. typedef pair <int, int> pii;
  19. #define sz(x) int((x).size())
  20.  
  21. template <typename T>
  22. using ordered_set = __gnu_pbds::tree <T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  23.  
  24. #ifdef ONLINE_JUDGE
  25. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  26. #else
  27. mt19937 rng(1000 - 7);
  28. #endif
  29.  
  30. const int N = 2e5 + 10;
  31. //const int MOD = 998244353;
  32. const ll MOD = 1e9 + 7;
  33. const ld eps = 1e-9;
  34. const pii dir[] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
  35.  
  36. struct segtree {
  37.     struct Node {
  38.         Node *l = nullptr, *r = nullptr;
  39.         int tl, tr, sum;
  40.  
  41.         Node(int tl, int tr) : tl(tl), tr(tr) {}
  42.  
  43.         ~Node() {
  44.             delete l;
  45.             delete r;
  46.         }
  47.     };
  48.  
  49.     ~segtree() {
  50.         delete root;
  51.     }
  52.  
  53.     Node *root = new Node(0, N - 1);
  54.     int _size = 0;
  55.  
  56.     inline int get(Node *u) {
  57.         return (u ? u->sum : 0);
  58.     }
  59.  
  60.     void update(Node *u, int pos) {
  61.         if (u->tl == u->tr) {
  62.             u->sum = 1;
  63.         }
  64.         else {
  65.             int tm = (u->tl + u->tr) / 2;
  66.  
  67.             if (pos <= tm) {
  68.                 if (!u->l) {
  69.                     u->l = new Node(u->tl, tm);
  70.                 }
  71.                 update(u->l, pos);
  72.             }
  73.             else {
  74.                 if (!u->r) {
  75.                     u->r = new Node(tm + 1, u->tr);
  76.                 }
  77.                 update(u->r, pos);
  78.             }
  79.             u->sum = get(u->l) + get(u->r);
  80.         }
  81.     }
  82.  
  83.     int sum(Node *u, int l, int r) {
  84.         if (l > r || !u) {
  85.             return 0;
  86.         }
  87.         else if (u->tl == l && u->tr == r) {
  88.             return u->sum;
  89.         }
  90.         else {
  91.             int tm = (u->tl + u->tr) / 2;
  92.             return sum(u->l, l, min(tm, r)) + sum(u->r, max(tm + 1, l), r);
  93.         }
  94.     }
  95.  
  96.     inline void insert(int x) {
  97.         _size++;
  98.         update(root, x);
  99.     }
  100.  
  101.     inline int less_than(int x) {
  102.         return sum(root, 0, x - 1);
  103.     }
  104.  
  105.     inline int greater_than(int x) {
  106.         return sum(root, x + 1, N - 1);
  107.     }
  108.  
  109.     inline int size() {
  110.         return _size;
  111.     }
  112.  
  113.     void dfs(Node *u, vector <int>& res) {
  114.         if (u->l) {
  115.             dfs(u->l, res);
  116.         }
  117.         if (u->r) {
  118.             dfs(u->r, res);
  119.         }
  120.         if (u->tl == u->tr) {
  121.             res.push_back(u->tl);
  122.         }
  123.     }
  124.  
  125.     vector <int> get_list() {
  126.         vector <int> res;
  127.         res.reserve(_size);
  128.  
  129.         dfs(root, res);
  130.  
  131.         return res;
  132.     }
  133. };
  134.  
  135. int n;
  136. ll ans[N];
  137. vector <int> g[N];
  138.  
  139. ll merge(segtree& a, segtree& b) {
  140.     ll add = 0;
  141.  
  142.     if (b.size() < a.size()) {
  143.         auto v = b.get_list();
  144.         for (int x : v) {
  145.             add += a.greater_than(x);
  146.         }
  147.         for (int x : v) {
  148.             a.insert(x);
  149.         }
  150.     }
  151.     else {
  152.         auto v = a.get_list();
  153.         for (int x : v) {
  154.             add += b.less_than(x);
  155.         }
  156.         for (int x : v) {
  157.             b.insert(x);
  158.         }
  159.  
  160.  
  161.         swap(a, b);
  162.  
  163.     }
  164.  
  165.     return add;
  166. }
  167.  
  168. segtree dfs(int u) {
  169.     ll cur = 0;
  170.  
  171.     segtree s;
  172.     s.insert(u);
  173.  
  174.     for (int v : g[u]) {
  175.         auto t = dfs(v);
  176.         cur += ans[v];
  177.  
  178.         cur += merge(s, t);
  179.     }
  180.  
  181.     ans[u] = cur;
  182.     return s;
  183. }
  184.  
  185. signed main() {
  186. #ifdef LOCAL
  187.     freopen("input.txt", "r", stdin);
  188.     freopen("output.txt", "w", stdout);
  189. #endif
  190.     cout << fixed << setprecision(9);
  191.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  192.  
  193.     cin >> n;
  194.  
  195.     for (int i = 1; i <= n; i++) {
  196.         int k;
  197.         cin >> k;
  198.  
  199.         while (k--) {
  200.             int v;
  201.             cin >> v;
  202.  
  203.             g[i].push_back(v);
  204.         }
  205.     }
  206.  
  207.     dfs(1);
  208.  
  209.     for (int i = 1; i <= n; i++) {
  210.         cout << ans[i] << " ";
  211.     }
  212.  
  213.     return 0;
  214. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement