Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast,unroll-loops")
- #ifdef LOCAL
- #include "debug.h"
- #else
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define debug(x...)
- #endif
- using namespace std;
- //#define int ll
- typedef long long ll;
- typedef long double ld;
- typedef pair <int, int> pii;
- #define sz(x) int((x).size())
- template <typename T>
- 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>;
- #ifdef ONLINE_JUDGE
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(1000 - 7);
- #endif
- const int N = 2e5 + 10;
- //const int MOD = 998244353;
- const ll MOD = 1e9 + 7;
- const ld eps = 1e-9;
- const pii dir[] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
- struct segtree {
- struct Node {
- Node *l = nullptr, *r = nullptr;
- int tl, tr, sum;
- Node(int tl, int tr) : tl(tl), tr(tr) {}
- ~Node() {
- delete l;
- delete r;
- }
- };
- ~segtree() {
- delete root;
- }
- Node *root = new Node(0, N - 1);
- int _size = 0;
- inline int get(Node *u) {
- return (u ? u->sum : 0);
- }
- void update(Node *u, int pos) {
- if (u->tl == u->tr) {
- u->sum = 1;
- }
- else {
- int tm = (u->tl + u->tr) / 2;
- if (pos <= tm) {
- if (!u->l) {
- u->l = new Node(u->tl, tm);
- }
- update(u->l, pos);
- }
- else {
- if (!u->r) {
- u->r = new Node(tm + 1, u->tr);
- }
- update(u->r, pos);
- }
- u->sum = get(u->l) + get(u->r);
- }
- }
- int sum(Node *u, int l, int r) {
- if (l > r || !u) {
- return 0;
- }
- else if (u->tl == l && u->tr == r) {
- return u->sum;
- }
- else {
- int tm = (u->tl + u->tr) / 2;
- return sum(u->l, l, min(tm, r)) + sum(u->r, max(tm + 1, l), r);
- }
- }
- inline void insert(int x) {
- _size++;
- update(root, x);
- }
- inline int less_than(int x) {
- return sum(root, 0, x - 1);
- }
- inline int greater_than(int x) {
- return sum(root, x + 1, N - 1);
- }
- inline int size() {
- return _size;
- }
- void dfs(Node *u, vector <int>& res) {
- if (u->l) {
- dfs(u->l, res);
- }
- if (u->r) {
- dfs(u->r, res);
- }
- if (u->tl == u->tr) {
- res.push_back(u->tl);
- }
- }
- vector <int> get_list() {
- vector <int> res;
- res.reserve(_size);
- dfs(root, res);
- return res;
- }
- };
- int n;
- ll ans[N];
- vector <int> g[N];
- ll merge(segtree& a, segtree& b) {
- ll add = 0;
- if (b.size() < a.size()) {
- auto v = b.get_list();
- for (int x : v) {
- add += a.greater_than(x);
- }
- for (int x : v) {
- a.insert(x);
- }
- }
- else {
- auto v = a.get_list();
- for (int x : v) {
- add += b.less_than(x);
- }
- for (int x : v) {
- b.insert(x);
- }
- swap(a, b);
- }
- return add;
- }
- segtree dfs(int u) {
- ll cur = 0;
- segtree s;
- s.insert(u);
- for (int v : g[u]) {
- auto t = dfs(v);
- cur += ans[v];
- cur += merge(s, t);
- }
- ans[u] = cur;
- return s;
- }
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(9);
- ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
- cin >> n;
- for (int i = 1; i <= n; i++) {
- int k;
- cin >> k;
- while (k--) {
- int v;
- cin >> v;
- g[i].push_back(v);
- }
- }
- dfs(1);
- for (int i = 1; i <= n; i++) {
- cout << ans[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement