BZOJ 3435: [Wc2014]紫荆花之恋

二次联通门 : BZOJ 3435: [Wc2014]紫荆花之恋

二次联通门 : luogu P3920 [WC2014]紫荆花之恋

/*

    luogu P3920 [WC2014]紫荆花之恋

    怀疑人生

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <ctime>

#include <algorithm>

#define rg register

#define INF 1e9

#define EPS 0.78

#define Max 100050

typedef long long LL;

int c[Max * ][], h[Max], d[Max], r[Max], li[Max], N, M, EC = ;

LL Answer; int dis[Max][], fi[Max], Dis[Max], Zero; bool Flag;

const int BUF = ; char Buf[BUF], *buf = Buf;

inline void read (int &n)

{

     rg char c = getchar ();

     for (n = ; !isdigit (*buf); ++ buf);

     for (; isdigit (*buf); n = n *  + *buf - '', ++ buf);

}

inline void Line (int x, int y, int z)

{

    c[++ EC][] = y, c[EC][] = fi[x], fi[x] = EC, c[EC][] = z;

    c[++ EC][] = x, c[EC][] = fi[y], fi[y] = EC, c[EC][] = z;

}

struct Node { Node *c[]; int v, s, val; };

Node pool[Max * ], *unp[Max * ], *Ta = pool, **top = unp, *_r[Max][], Null, *null = &Null;

struct Balance_Tree

{

    inline Node* Get(int x)

    {

        Node *k = (top != unp) ? *--top : Ta ++;

        k->c[] = k->c[] = null, k->s = , k->v = x, k->val = rand (); return k;

    }

    inline void Update (Node *x) { x->s = x->c[]->s + x->c[]->s + ; }

    Node *Rebuild (int x, int y)

    {

        Node* R = Get (dis[li[]][y] - r[li[]]);

        for (rg int i = ; i <= x; ++ i)

            Inse_r (R, Get (dis[li[i]][y] - r[li[i]]));

        return R;

    }

    void Rotate (Node *&x, Node *y)

    {

        bool k = y == x->c[];

        x->c[!k] = y->c[k], y->c[k] = x, y->s=x->s;

        Update(x), x = y; return;

    }

    int Query (Node *x, int y)

    {

        if (x == null) return ;

        if (y >= x->v) return x->c[]->s +  + Query (x->c[], y);

        return Query (x->c[], y);

    }

    void Clear(Node* &x)

    {

        if (x == null) return;

        *top ++ = x, Clear (x->c[]), Clear (x->c[]), x = null;

    }

    void Inse_r (Node *&x, Node *y)

    {

        bool flag = y->v > x->v;

        if (x == null) { x = y; return; } else ++ x->s;

        Inse_r (x->c[flag], y);

        if (x->c[flag]->val > x->val) Rotate (x, x->c[flag]);

    }

} B;

#undef Max

struct Divide_Tree

{

#define Max 100050

    int suf[Max], ct[Max], sg[Max], s[Max], R, Sg;

    int Get_R (int C)

    {

        int _C = li[]; rg int i, j;

        for (i = C; i >= ; -- i)

            for (s[li[i]] = , j = fi[li[i]]; j; j = c[j][])

                if (!sg[c[j][]] && s[c[j][]] > ) s[li[i]] += s[c[j][]];

        for (; true; )

        {

            bool flag = false;

            for (i = fi[_C]; i; i = c[i][])

                if (s[c[i][]] < s[_C] && !sg[c[i][]] && s[c[i][]] *  >= C)

                { _C = c[i][], flag = true; break; }

            if (!flag) break;

        }

        for (i = ; i <= C; ++ i) s[li[i]] = ;

        return _C;

    }

    int Get_s (int x)

    {

        int le = , ri = ; li[] = x, s[x] = -;

        for (rg int i; le <= ri; ++ le)

            for (i = fi[li[le]]; i; i = c[i][])

                if (!s[c[i][]] && !sg[c[i][]]) s[li[++ ri] = c[i][]] = -;

        return ri;

    }

    void Clear (int x)

    {

        if (!sg[x] || sg[x] < Sg) return;

        sg[x] = , B.Clear (_r[x][]), B.Clear (_r[x][]);

        for (rg int i = fi[x]; i; i = c[i][]) Clear (c[i][]);

    }

    void Get (int x, int y)

    {

        ct[x] = , sg[x] = sg[suf[x]] + ; rg int i, j;

        int _f = ; _r[x][] = B.Get (-y), _r[x][] = B.Get (c[EC][] - y);

        memcpy (dis[x], dis[suf[x]], sizeof dis[suf[x]]);

        for (i = ; i < sg[x]; ++ i) dis[x][i] += c[EC][];

        for (dis[x][sg[x]] = , i = suf[x], j = sg[x] - ; i; i = suf[i], -- j)

        {

            ++ ct[i];

            if (j -  && ct[i] / (ct[suf[i]] + 1.0) > EPS) _f = suf[i];

            Answer += B.Query (_r[i][], y - dis[x][j]), B.Inse_r (_r[i][], B.Get (dis[x][j] - y));

            if (j - ) Answer -= B.Query (_r[i][], y - dis[x][j - ]), B.Inse_r (_r[i][], B.Get (dis[x][j - ] - y));

        }

        if (_f) Sg = sg[_f], Clear (_f), Rebuild (_f, Sg, suf[_f]);

    }

    void Rebuild (int x, int y, int z)

    {

        int C = Get_s (x), _C = Get_R (C);

        dis[_C][y] = , Dfs (_C, , y), sg[_C] = y;

        if (z) suf[_C] = z; else suf[R = _C] = , _r[_C][] = null;

        _r[_C][] = B.Rebuild (C, y), ct[_C] = C;

        if (y > ) _r[_C][] = B.Rebuild (C, y - );

        for (rg int i = fi[_C]; i; i = c[i][])

            if (!sg[c[i][]]) Rebuild (c[i][], y + , _C);

    }

    void Dfs (int x,int y,int z)

    {

        for (rg int i = fi[x]; i; i = c[i][])

            if (!sg[c[i][]] && c[i][] != y)

                dis[c[i][]][z] = dis[x][z] + c[i][], Dfs (c[i][], x, z);

    }

#undef Max

} A;

int main (int argc, char *argv[])

{

    fread (buf, , BUF, stdin);

       read (Zero), read (N), read (Zero), read (Zero), A.R = ;

    Null.c[] = Null.c[] = &Null; int q, w;

    srand (time ()), read (r[]),  A.Get (, r[]); puts ("");

    for (rg int i = ; i <= N; ++ i)

    {

        read (q), q = q ^ (Answer % (int) INF), read (w);

        read (r[i]), h[i] = h[q] + , d[i] = d[q] + w;

        Line (i, q, w), A.suf[i] = q, A.Get (i, r[i]);

        printf ("%lld\n", Answer);

    }

    return ;

}