Tram travel#11775

Tram travel (Editorial)

Problem Author:	Pavlo Tsikalyshyn
Prepared by:	Pavlo Tsikalyshyn, Denysov Kostiantyn
Editorial by:	Denysov Kostiantyn

Lets at first solve the problem offline (that is $g = 0$ g=0, in that case all queries are known in advance). For that, we can use heavy light decomposition (HLD). We can build the whole tree in advance to know its structure and build HLD over it. Then any path can be seen as $O (lo g n)$ O(\log{n}) bamboo-paths. So it is essential to solve our problem on bamboo to use HLD. For bamboo, it is easy to calculate the minimum amount of minutes using prefix sums as in this case for every edge (depending on the direction) we know what will be the next our edge on the path. To do dynamic prefix sums, we can maintain a segment tree to update values. Then we can do updates in $O (lo g n)$ O(\log{n}) and answer queries in $O (lo g^{2} n)$ O(\log^2{n}). Then we have offline solution in $O (q \cdot lo g^{2} n)$ O(q \cdot \log^2{n}).

Let's learn to solve when $g = 1$ g=1. Then we can't know tree structure in advance. In cases when we have a static data structure (we can't do additions, in this case adding a vertex) and we still want to do additions then we can try to use "static to dynamic" technique. To use this trick on a tree, we will maintain components we are currently in the same structure. In "static to dynamic" technique, we split our structure to no more than $lo g n$ different structures. Here we will have more than that. We will split our tree on components, and in each we will build HLD separately.

So we start with a single vertex and then will learn how to add one more. Every component size will be a power of two. Adding of vertex to the graph will work this way: let's look at component sizes from new vertex to root, then we will do things as in the usual "static to dynamic" approach. We find the first missing power of two in the components sizes, and then merge all the components with fewer sizes than this power of two to make a new component of such size.

Then let's see one important property: if we take some vertex $v$ and look at the sizes of components on the path to the root, then those sizes will be strictly increasing while going to the root.

If sizes are strictly increasing then if we take the path between two vertices then it will go through $O (lo g n)$ O(\log{n}) different components. So then we can answer the queries in $O (lo g^{3} n)$ O(\log^3{n}) as in every component we find minimum time in $O (lo g^{2} n)$ O(\log^2{n}). But we can do better!

Let's see time complexities of our queries:

Minimum path query: $O (lo g^{3} n)$ O(\log^3{n}) per query;
Update: $O (lo g n)$ O(\log{n}) per query;
Adding a vertex: $O (n \cdot lo g n)$ O(n \cdot \log{n}) in total (as every vertex changes its components no more than $lo g n$ times).

We can see that updates and adding are very fast comparing to query path. We can try to make them slower, but get faster path query to make faster solution.

We can mention that during path query, we do $O (lo g^{2} n)$ O(\log^2{n}) queries of finding sum on segment tree. What if somehow we do them in $O (1)$ like we previously did in prefix sums? But how to do updates then? We can use sqrt decomposition! Usually using sqrt decomposition we can do updates in $O (1)$ and queries in $O (n)$ O(\sqrt{n}). But in a similar way, we can do updates in $O (n)$ O(\sqrt{n}) and queries in $O (1)$ .

This way we can answer path queries in $O (lo g^{2} n)$ O(\log^2{n}) and do updates in $O (n)$ O(\sqrt{n}) which is fast enough.

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 4e5 + 11, inf = 1000111222;


int period;

struct ed {
    int to, t1, t3;
};

vector <int> edge[max_n];


vector <ed> e;

inline void add_edge (int u, int v, int t1, int t3) {
    assert(t3 + t1 < period);
    edge[u].pb(len(e));
    e.pb(ed{v, t3, t1});
    edge[v].pb(len(e));
    e.pb(ed{u, t3 + t1, period - t1});
}


int p[max_n], back_edge_id[max_n], sz[max_n], num_cmp[max_n], tin[max_n], tout[max_n], depth[max_n];

int active[max_n], active_id = 0, leader[max_n];

inline void dfs (int v, int pr, int color, int root) {
    sz[v] = 1;
    leader[v] = root;
    num_cmp[v] = color;
    for (int id : edge[v]) {
        int to = e[id].to;
        if (to == pr || active[num_cmp[to]] != active_id) {
            continue;
        }
        p[to] = v;
        back_edge_id[to] = id ^ 1;
        depth[to] = depth[v] + 1;
        dfs(to, v, color, root);
        sz[v] += sz[to];
    }
}

int timer = 0, nxt[max_n];

vector <int> who;

inline void dfs_hld (int v) {
    who.pb(v);
    tin[v] = timer++;
    int cur = -1;
    for (int id : edge[v]) {
        int to = e[id].to;
        if (to == p[v] || active[num_cmp[to]] != active_id) {
            continue;
        }
        if (cur == -1 || sz[to] > sz[cur]) {
            cur = to;
        }
    }
    if (cur != -1) {
        nxt[cur] = nxt[v];
        dfs_hld(cur);
        for (int id : edge[v]) {
            int to = e[id].to;
            if (to == p[v] || active[num_cmp[to]] != active_id || to == cur) {
                continue;
            }
            nxt[to] = to;
            dfs_hld(to);
        }
    }
    tout[v] = timer;
}

const int C = 400;

int id_block[max_n];


struct magic {

    vector <ll> pref, block;

    inline void init (int n) {
        pref.resize(n);
        block.resize(n / C + 1);
    }

    inline void compute () {
        int n = len(pref);
        for (int i = 1; i < n; i++) {
            pref[i] += pref[i - 1];
        }
    }

    inline ll get_pref (int r) {
        if (r < 0) {
            return 0;
        }
        return pref[r] + block[id_block[r]];
    }

    inline ll get_sum (int l, int r) {
        return get_pref(r) - get_pref(l - 1);
    }

    inline void upd (int pos, ll new_val) {
        ll add = new_val - get_sum(pos, pos);
        if (add == 0) {
            return;
        }
        int r = min(len(pref), (id_block[pos] + 1) * C);
        for (; pos < r; pos++) {
            pref[pos] += add;
        }
        if (r < len(pref)) {
            r = id_block[r];
            for (; r < len(block); r++) {
                block[r] += add;
            }
        }
    }
};


inline void norm_t (int &t) {
    if (t >= period) {
        t -= period;
    }
}

struct cmp_structure {

    int sz_cmp;
    vector <int> save;
    magic up, down;

    inline void init (int root, int sz, int new_num) {
        who.clear();
        active[new_num] = active_id;
        if (root) {
            depth[root] = depth[p[root]] + 1;
        }
        dfs(root, -1, new_num, root);
        timer = 0;
        nxt[root] = root;
        dfs_hld(root);
        int n = len(who);
        save = who;
        up.init(n);
        down.init(n);
        for (int i = 0; i < n; i++) {
            int ver = who[i];
            if (nxt[ver] != ver) {
                if (nxt[ver] != p[ver]) {
                    int id = back_edge_id[ver];
                    int arrive = e[id].t1 + e[id].t3;
                    norm_t(arrive);
                    int need = e[back_edge_id[p[ver]]].t1;
                    ll res = need - arrive;
                    if (res < 0) {
                        res += period;
                    }
                    down.pref[i] = e[id].t3 + res;
                }
                if (i + 1 < n) {
                    int id = back_edge_id[ver] ^ 1;
                    int arrive = e[id].t1 + e[id].t3;
                    norm_t(arrive);
                    int need = e[back_edge_id[who[i + 1]] ^ 1].t1;
                    ll res = need - arrive;
                    if (res < 0) {
                        res += period;
                    }
                    up.pref[i] = e[id].t3 + res;
                }
            }
        }
        down.compute();
        up.compute();
        sz_cmp = sz;
    }

    inline ll get_sum_down (int l, int r) {
        return down.get_sum(l, r);
    }

    inline ll get_sum_up (int l, int r) {
        return up.get_sum(l, r);
    }

    inline int get_arrive_down_time (int id) {
        int ver = save[id - 1];
        id = back_edge_id[ver];
        int res = e[id].t1;
        return res;
    }

    inline int get_arrive_up_time (int id) {
        assert(id + 1 < len(save));
        int ver = save[id + 1];
        id = back_edge_id[ver] ^ 1;
        int res = e[id].t1;
//        norm_t(res);
        return res;
    }

    inline void set_val (int ver) {
        int n = len(save), i = tin[ver];
        if (nxt[ver] != ver) {
            if (nxt[ver] != p[ver]) {
                int id = back_edge_id[ver];
                int arrive = e[id].t1 + e[id].t3;
                norm_t(arrive);
                int need = e[back_edge_id[p[ver]]].t1;
                ll res = need - arrive;
                if (res < 0) {
                    res += period;
                }
                down.upd(i, e[id].t3 + res);
            }
            if (i + 1 < n) {
                int id = back_edge_id[ver] ^ 1;
                int arrive = e[id].t1 + e[id].t3;
                norm_t(arrive);
                int need = e[back_edge_id[save[i + 1]] ^ 1].t1;
                ll res = need - arrive;
                if (res < 0) {
                    res += period;
                }
                up.upd(i, e[id].t3 + res);
            }
        }
    }

    inline void upd (int x) {
        int l = max(0, tin[x] - 1);
        int r = min(len(save), tin[x] + 2);
        for (; l < r; l++) {
            set_val(save[l]);
        }
    }
};


cmp_structure T[max_n];


inline void go_wait (int &t, ll &ans, int st) {
    if (t <= st) {
        ans += st - t;
    }
    else {
        ans += period + (st - t);
    }
    t = st;
}


inline void go_one_down (int v, int &t, ll &ans) {
    go_wait(t, ans, e[back_edge_id[v]].t1);
    t += e[back_edge_id[v]].t3;
    norm_t(t);
    ans += e[back_edge_id[v]].t3;
}


inline void go_one_up (int v, int &t, ll &ans) {
    go_wait(t, ans, e[back_edge_id[v] ^ 1].t1);
    t += e[back_edge_id[v] ^ 1].t3;
    norm_t(t);
    ans += e[back_edge_id[v] ^ 1].t3;
}



inline int get_ver (int cmp, int id) {
    return T[cmp].save[id];
}

inline void get_sum_down (int cmp, int l, int r, int &t, ll &ans) {
    if (l > r) {
        return;
    }
    ans += T[cmp].get_sum_down(l, r);
    t = T[cmp].get_arrive_down_time(l);
}

inline void get_sum_up (int cmp, int l, int r, int &t, ll &ans) {
    if (l > r) {
        return;
    }
    ans += T[cmp].get_sum_up(l, r);
    t = T[cmp].get_arrive_up_time(r);
}


inline void go_line_down (int x, int y, int &t, ll &ans) {
    if (x == y) {
        return;
    }
    go_wait(t, ans, e[back_edge_id[x]].t1);
    get_sum_down(num_cmp[x], tin[y] + 2, tin[x], t, ans);
    int prelast = get_ver(num_cmp[x], tin[y] + 1);
    go_one_down(prelast, t, ans);
}


inline void go_line_up (int x, int y, int &t, ll &ans) {
    if (x == y) {
        return;
    }
    int prefirst = get_ver(num_cmp[x], tin[x] + 1);
    go_wait(t, ans, e[back_edge_id[prefirst] ^ 1].t1);
    get_sum_up(num_cmp[x], tin[x] + 1, tin[y] - 1, t, ans);
    go_one_up(y, t, ans);
}



inline void go (int x, int y, int &t, ll &ans) {
    if (x == y) {
        return;
    }
    vector <pii> save;
    while (nxt[x] != nxt[y]) {
        if (depth[nxt[x]] > depth[nxt[y]]) {
            go_line_down(x, nxt[x], t, ans);
            go_one_down(nxt[x], t, ans);
            x = p[nxt[x]];
        }
        else {
            save.pb({y, nxt[y]});
            y = p[nxt[y]];
        }
        LOG(x, y, t, ans);
    }
    if (tin[x] < tin[y]) {
        go_line_up(x, y, t, ans);
    }
    else {
        go_line_down(x, y, t, ans);
    }
    reverse(all(save));
    for (auto &i : save) {
        go_one_up(i.second, t, ans);
        go_line_up(i.second, i.first, t, ans);
    }
}


inline ll solve (int x, int y, int t) {
    if (x == y) {
        return 0;
    }
    ll ans = 0;
    vector <pii> save;
    while (num_cmp[x] != num_cmp[y]) {
        if (depth[leader[x]] > depth[leader[y]]) {
            go(x, leader[x], t, ans);
            go_one_down(leader[x], t, ans);
            x = p[leader[x]];
        }
        else {
            save.pb({y, leader[y]});
            y = p[leader[y]];
        }
    }
    go(x, y, t, ans);
    reverse(all(save));
    for (auto &i : save) {
        go_one_up(i.second, t, ans);
        go(i.second, i.first, t, ans);
    }
    return ans;
}

inline void upd (int x) {
    T[num_cmp[x]].upd(x);
}


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < max_n; i++) {
        id_block[i] = i / C;
    }

    int n, q, g;
    cin >> period >> n >> q >> g;
    for (int i = 1, a, b, t1, t3; i < n; i++) {
        cin >> a >> b >> t1 >> t3;
//        LOG(a, b, t1, t3);
        --a, --b;
        add_edge(a, b, t1, t3);
    }
//    return 0;
    int N = n;
    while ((N & (N - 1)) != 0) {
        ++N;
    }
    T[0].init(0, N, 0);
    int cur_ver = n, num = 1;
    ll last = 0;
    for (int i = 0, type, x, y, t, t1, t3; i < q; i++) {
        cin >> type;
        if (type == 1) {
            cin >> x >> y >> t;
            x = (x - 1 + last * g) % (n + q) + 1;
            y = (y - 1 + last * g) % (n + q) + 1;
            --x, --y;
            ll res = solve(x, y, t);
            cout << res << '\n';
            last = res;
        }
        else if (type == 2) {
            cin >> x >> y >> t1 >> t3;

            x = (x - 1 + last * g) % (n + q) + 1;
            y = (y - 1 + last * g) % (n + q) + 1;
            assert(t3 + t1 < period);
            --x, --y;
            // update edge
            if (p[x] == y) {
                int id = back_edge_id[x];
                e[id].t1 = t3;
                e[id].t3 = t1;
                e[id ^ 1].t1 = t3 + t1;
                e[id ^ 1].t3 = period - t1;

                if (num_cmp[x] == num_cmp[y]) {
                    upd(x);
                }
            }
            else {
                assert(p[y] == x);

                int id = back_edge_id[y];
                e[id ^ 1].t1 = t3;
                e[id ^ 1].t3 = t1;


                e[id].t3 = period - t1;
                e[id].t1 = t3 + t1;

                if (num_cmp[x] == num_cmp[y]) {
                    upd(y);
                }
            }
            // done
        }
        else if (type == 3) {
            cin >> x;
            --x;
            // delete vertex

            // done
        }
        else {
            cin >> x >> y >> t1 >> t3;

            x = (x - 1 + last * g) % (n + q) + 1;
            y = (y - 1 + last * g) % (n + q) + 1;

            --x, --y;
            assert(y == cur_ver);
            ++cur_ver;
            add_edge(x, y, t1, t3);
            p[y] = x;

            back_edge_id[y] = len(e) - 1;
            int cur_sz = 1;
            ++active_id;
            int new_num = num++;

            leader[y] = y;
            num_cmp[y] = new_num;
            active[num_cmp[y]] = active_id;
            depth[y] = depth[x] + 1;


            while (true) {
                y = leader[y];
                if (!y) {
                    break;
                }
                int pr = p[y];
                assert(num_cmp[pr] != num_cmp[y]);
                int sz_pr = T[num_cmp[pr]].sz_cmp;
                if (sz_pr == cur_sz) {
                    cur_sz += sz_pr;

                    y = pr;
                    active[num_cmp[y]] = active_id;
                }
                else {
                    break;
                }
            }
            y = leader[y];

            T[new_num].init(y, cur_sz, new_num);
            // done

        }
    }
}

C++