AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 吐槽
  • App
  • 登录/注册

HDU-6291 对称数 (树上莫队 + 分块)

作者: 作者的头像   冰冷酒 ,  2022-11-23 22:02:14 ,  所有人可见 ,  阅读 159


4


#include <bits/stdc++.h>

// #define int long long

using namespace std;

// #pragma GCC optimize(2, "Ofast", "inline")
// #pragma GCC optimize(3, "Ofast", "inline")

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 200010, M = 2 * N;

int T;

int n, m, a[N];
vector<int> G[N];

int depth[M], fa[N][21];
int q[N];

int block[N], first[N];
int nums[M], cnt;

int len;

struct node {
    int l, r, id, p;
}Query[N];

bool cmp(const node &a, const node &b) {
    if (block[a.l] != block[b.l]) return block[a.l] < block[b.l];
    return first[a.r] < first[b.r];
}

void dfs(int u, int father) {
    first[u] = ++ cnt;

    for (auto j : G[u]) {
        if (j == father) continue;
        depth[j] = depth[u] + 1;
        fa[j][0] = u;
        for (int k = 1; k <= 20; k ++)
            fa[j][k] = fa[fa[j][k - 1]][k - 1];
        dfs(j, u);
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 20; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 20; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
            a = fa[a][k], b = fa[b][k];
    return fa[a][0];
}

int num_a[N], hs[N];
int len_a;

int ans[N];

int st[N];

void add_modui(int x) {
    st[a[x]] ^= 1;
    if (st[a[x]] % 2) {
        num_a[hs[a[x]]] ++;
    } else {
        num_a[hs[a[x]]] --;
    }
}

void move(int x, int y) {
    while (x != y) {
        if (depth[x] > depth[y]) swap(x, y);
        add_modui(y);
        y = fa[y][0];
    }
}

int query() {
    for (int i = 1; i <= len_a + 1; i ++) {
        if (num_a[i] != len_a) {
            for (int j = (i - 1) * len_a + 1; j < N; j ++) {
                if (st[j] % 2 == 0) {
                    return j;
                }
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    len_a = sqrt(N);
    for (int i = 1; i < N; i ++) hs[i] = (i - 1) / len_a + 1;

    cin >> T;
    while (T --) {
        cnt = 0;

        cin >> n >> m;

        for (int i = 1; i <= n; i ++) {
            cin >> a[i];
            G[i].clear();
            st[i] = num_a[i] = 0;
        }

        for (int i = 1; i < n; i ++) {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }

        depth[0] = 0, depth[1] = 1;
        dfs(1, -1);

        len = sqrt(n);
        for (int i = 1; i <= n; i ++) {
            block[i] = (first[i] - 1) / len + 1;
        }

        for (int i = 1; i <= m; i ++) {
            int l, r;
            cin >> l >> r;
            if (block[l] > block[r]) swap(l, r);
            int p = lca(l, r);
            Query[i] = {l, r, i, p};
        }

        sort(Query + 1, Query + m + 1, cmp);

        int LCA = Query[1].p;
        move(Query[1].l, Query[1].r);
        add_modui(LCA);
        ans[Query[1].id] = query();
        add_modui(LCA);

        for (int i = 2; i <= m; i ++) {
            int id = Query[i].id, p = Query[i].p;
            move(Query[i - 1].l, Query[i].l);
            move(Query[i - 1].r, Query[i].r);
            add_modui(p);
            ans[id] = query();
            add_modui(p);
        }

        for (int i = 1; i <= m; i ++) {
            cout << ans[i] << '\n';
        }
    }

    return 0;
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息