Участник:ZhenyaStrelkova/ADAFTBLL

Материал из DISCOPAL
< Участник:ZhenyaStrelkova
Версия от 22:15, 10 декабря 2020; ZhenyaStrelkova (обсуждение | вклад) (Новая страница: «https://www.spoj.com/problems/ADAFTBLL/ <code-cpp> #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int max_n = 100007; c…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADAFTBLL/

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int max_n = 100007;
const int max_m = 100007;
const int k = 16;
 
typedef struct query_t {
    int l;
    int r;
    int t;
    int z;
} query_t;
 
query_t ask[100010];
 
typedef struct list {
    int data;
    struct list *next;
} list;
 
typedef struct vector_int {
    list *start;
    list *end;
} vector_int;
 
typedef struct mo {
    long ret;
    int cnt[max_m];
    int mark[max_n];
 
} mo;
 
void ml_emplace_back(vector_int *v, int value) {
 
    list *newList = (list *) malloc(sizeof(list));
    newList->next = nullptr;
    newList->data = value;
    if (v->end) {
        v->end->next = newList;
        v->end = newList;
    }
    else {
        v->end = newList;
        v->start = newList;
    }
}
 
vector_int edges[max_n], query[60][60];
int a[max_n], value[max_n], st[max_n], ed[max_n];
int dfn[max_n * 2];
int sz, n, q;
int fa[max_n][k + 1], dep[max_n];
 
void dfs(int u, int p) {
    int v;
    dfn[st[u] = ++sz] = u;
    fa[u][0] = p;
    for (int i = 1; i < k; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    list *start = edges[u].start;
    while (start != nullptr) {
        v = start->data;
        if (v != p) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
        start = start->next;
    }
    dfn[ed[u] = ++sz] = u;
}
 
void add(mo *m, int x) {
    int v;
    v = value[x];
    if (m->mark[x]) {
        m->cnt[v]--;
        m->ret = m->ret - m->cnt[v];
    }
    else {
        m->ret = m->ret + m->cnt[v];
        m->cnt[v]++;
    }
    m->mark[x] ^= 1;
}
 
int lca(int x, int y) {
    if (y == x)
        return x;
    if (dep[x] < dep[y]) {
        swap(x, y);
    }
    for (int i = k; i >= 0; --i) {
        if (dep[fa[x][i]] >= dep[y])
            x = fa[x][i];
    }
    if (x == y)
        return x;
    for (int i = k; i >= 0; --i) {
        if (fa[x][i] == fa[y][i])
            continue;
        y = fa[y][i];
        x = fa[x][i];
 
    }
    return fa[x][0];
}
 
inline void nulling(vector_int &vert) {
    vert.start = nullptr;
    vert.end = nullptr;
}
 
int main() {
    for (auto &edge: edges) {
        nulling(edge);
    }
    for (auto &query_row: query) {
        for (auto &query_elem: query_row) {
            nulling(query_elem);
        }
    }
 
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        ml_emplace_back(&edges[u], v);
        ml_emplace_back(&edges[v], u);
    }
    sz = 0;
    dep[0] = 0;
    dfs(0, 0);
    int B = 0;
    while (B * B * B < sz) {
        B++;
    }
    B = B * B;
    pair<int, int> modify[max_n];
    int modify_size = 0;
    for (int i = 0; i < q; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            ask[i].t = -2;
            modify[modify_size].first = x;
            modify[modify_size].second = y;
            modify_size++;
        } else {
            if (st[x] > st[y]) {
                swap(x, y);
            }
            int l, z, r;
            z = lca(x, y);
            r = st[y];
            l = (z == x) ? st[x] : ed[x];
 
            ask[i].t = modify_size - 1;
            ask[i].z = (z == x) ? -1 : z;
            ask[i].l = l;
            ask[i].r = r;
            ml_emplace_back(&query[l / B][r / B], i);
        }
    }
    long ret[q];
    int m = (sz - 1) / B + 1;
    for (int i = 0; i < m; ++i) {
        for (int j = i; j < m; ++j) {
            if (query[i][j].start == nullptr)
                continue;
            memcpy(value, a, sizeof(*a) * n);
            mo mo_instance;
            fill(mo_instance.cnt, mo_instance.cnt + max_m, 0);
            fill(mo_instance.mark, mo_instance.mark + max_n, 0);
            mo_instance.ret = 0;
            int t = 0, l = 0, r = -1;
            list *start = query[i][j].start;
            while (start != nullptr) {
                int v = start->data;
                struct query_t qr = ask[v];
                if (qr.r > r) {
                    r++;
                    while (r <= qr.r) {
                        add(&mo_instance, dfn[r]);
                        r++;
                    }
                    --r;
                }
                while (r > qr.r)
                    add(&mo_instance, dfn[r--]);
                while (l < qr.l)
                    add(&mo_instance, dfn[l++]);
                if (l > qr.l) {
                    l--;
                    while (l >= qr.l) {
                        add(&mo_instance, dfn[l]);
                        l--;
                    }
                    ++l;
                }
                int x, y;
                while (t <= qr.t) {
                    x = modify[t].first;
                    y = modify[t].second;
                    int flag = (qr.l <= st[x] && st[x] <= qr.r) ^ (qr.l <= ed[x] && ed[x] <= qr.r);
                    if (flag != 0) {
                        add(&mo_instance, x);
                    }
                    value[x] = y;
                    if (flag != 0) {
                        add(&mo_instance, x);
                    }
                    t++;
                }
                if (qr.z != -1) {
                    add(&mo_instance, qr.z);
                }
                ret[v] = mo_instance.ret;
                if (qr.z != -1) {
                    add(&mo_instance, qr.z);
                }
                start = start->next;
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        if (ask[i].t == -2)
            continue;
        cout << ret[i] << "\n";
    }
    return 0;
}