宇宙大一统 by roosephu

gistfile1.cpp

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <ctype.h>
#include <math.h>
#include <stdbool.h>

#define DEBUG
typedef int (*cmp_t) (const void *, const void *);
typedef unsigned uint;
typedef long long int64;
typedef unsigned long long uint64;
#define max(i, j) ({int _ = (i), __ = (j); _ > __ ? _ : __;})
#define min(i, j) ({int _ = (i), __ = (j); _ < __ ? _ : __;})
#define swap(T, i, j) ({T _ = (i); (i) = (j); (j) = _;})
#ifdef DEBUG
#define cerr(...) fprintf (stderr, __VA_ARGS__)
void disp (int *x, int n) {int i; cerr ("["); for (i = 0; i < n - 1; ++i) cerr ("%d ", x[i]); if (n) cerr ("%d", x[i]); cerr ("]");}
#else
#define cerr(...) ({})
void disp (int *x, int n) {};
#endif
#define CR cerr ("\n")
#ifdef WIN32
#define fmt64 "%I64d"
#else
#define fmt64 "%lld"
#endif

#define maxn 44000

typedef struct node {struct node *c[2], *f; bool rev; int key, sum, wpl, wpr, dep, vcs;} node;
typedef int arr32[maxn];

node lct[maxn], *null = lct;
arr32 ufs, size, cost;
int ans;

bool isr (node *t) {return t->f == null || (t->f->c[0] != t && t->f->c[1] != t);}
#define setc(F,d,C) (((F)->c[d] = (C))->f = (F))

node *update (node *t) {
     node *l = t->c[0], *r = t->c[1];
     t->sum = l->sum + t->key + r->sum;
     t->wpl = l->wpl + r->wpl + (t->key + r->sum) * l->dep + r->sum + t->vcs;
     t->wpr = l->wpr + r->wpr + (t->key + l->sum) * r->dep + l->sum + t->vcs;
     return t->dep = l->dep + 1 + r->dep, t;
}

void put_rev (node *t) {
     if (t == null) return ;
     swap (node *, t->c[0], t->c[1]), swap (int, t->wpl, t->wpr);
     t->rev ^= 1;
}

void show () {
     void dfs (node *t, int d) {
          cerr ("["); 
          if (t->c[d] != null) dfs (t->c[d], d ^ t->rev), cerr ("<-");
          cerr ("%d(%d, %d)", t - lct, t->key, t->vcs);
          if (t->c[!d] != null) cerr ("->"), dfs (t->c[!d], d ^ t->rev);
          cerr ("]");
     }
     int i;
     cerr ("====================\n");
     for (i = 1; i <= 5; ++i)
          if (isr (lct + i))
               dfs (lct + i, 0), cerr ("[wpl: %d]\n", lct[i].wpl);
     cerr ("====================\n");
}

void push_down (node *t) {
     if (t->rev) put_rev (t->c[0]), put_rev (t->c[1]), t->rev = false;
}

void rotate (node *x) {
     node *y = x->f, *z = y->f; int d = x == y->c[1];
     push_down (y), push_down (x);
     x->f = z; if (!isr (y)) z->c[y == z->c[1]] = x;
     setc (y, d, x->c[!d]);
     setc (x, !d, update (y));
}

node *splay (node *x) {
     for (push_down (x); !isr (x); rotate (x))
          if (!isr (x->f))
               rotate ((x->f->f->c[1] == x->f) == (x->f->c[1] == x) ? x->f : x);
     return update (x);
}

void relink (node *p, node *q) {
     node *t = p->c[1];
     p->vcs += (t->sum - q->sum) + (t->wpl - q->wpl);
     p->key +=  t->sum - q->sum;
     p->c[1] = q;
}

node *expose (node *p) {
     node *q = null;
     for (; p != null; p = p->f)
          splay (p), relink (p, q), update (q = p);
     return q;
}

void evert (node *t) {put_rev (expose (t));}
int find (int t){return ufs[t] != t ? ufs[t] = find (ufs[t]) : t;}
int get_size (node *t){ return expose (t), t->key;}

node *find_root (node *t) {
     for (expose (t); push_down (t), t->c[0] != null; t = t->c[0]);
     return t;
}

void unite (int S, int T) {
     int x = find (S), y = find (T); node *s = lct + S, *t = lct + T;
     if (size[x] > size[y]) swap (node *, s, t), swap (int, x, y);
     evert (s), splay (s), s->f = t;
     int lmt = (size[y] - size[x] + 1) / 2;
     node *m = expose (t);
     /* cerr ("[lmt, w: %d %d]\n", lmt, m - lct); */
     for (; push_down (m), m != null; )
          if (m->c[1] != null && m->c[1]->sum >= lmt) m = m->c[1];
          else if (m->key + m->c[1]->sum >= lmt) break;
          else lmt -= m->key + m->c[1]->sum, m = m->c[0];
     assert (m != null);
     splay (t), t->key += s->sum, t->vcs += s->wpl + s->sum, update (t);
     evert (m), splay (m);
     ans -= cost[x] + cost[y], ufs[x] = y, size[y] += size[x];
     ans += cost[y] = m->wpl;
     /* cerr ("[centroid: %d]\n", m - lct); */
     /* show (); */
}

int main () {
     freopen ("village.in" , "r", stdin);
     freopen ("village.out", "w", stdout);

     int n, m, i, s, t; char cmd;
  
     *null = (node){{null, null}, null};
     scanf ("%d%d", &n, &m);
     for (i = 1; i <= n; ++i)
          lct[i] = (node){{null, null}, null, 0, 1, 1, 0, 0, 1, 0}, ufs[i] = i, size[i] = 1;
     for (; m--; ) {
          scanf (" %c", &cmd);
          if (cmd == 'Q')
               printf ("%d\n", ans);
          else
               scanf ("%d%d", &s, &t), unite (s, t);
     }
     return 0;
}