曾子愚 's Blog

U498412 JJ的项链

U498412 JJ的项链

题目描述

JJ 有一串由各种漂亮的贝壳组成的项链。JJ 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。JJ 不断地收集新的贝壳，因此，他的项链变得越来越长（长成树形结构，以 1 为根）。

有一天，他突然提出了一个问题：树上某一条链中（对于链 (u,v)，保证 u 在 1\sim v 的路径上），包含了多少种不同的贝壳？

输入格式

第一行2个整数 n,q，代表点数和询问数

第二行 n 个整数 c[1\sim n] 代表每个贝壳的种类

接下来 n-1 行，每行2个整数 (u,v) 代表树上一条边

接下来 q 行，每行2个整数 (u,v) 代表一次询问，保证 u 在 1\sim v 的路径上，u=v 是有可能的

输出格式

输出 q 行，每行1个整数代表答案

样例 #1

样例输入 #1

10 10
2 1 2 3 1 1 3 1 3 1
1 2
3 1
4 1
5 4
6 4
7 3
1 8
9 1
5 10
1 2
1 3
3 7
4 5
1 5
1 10
1 6
1 8
4 10
6 6

样例输出 #1

2
1
2
2
3
3
3
2
2
1

样例链接跳转 #2

样例输入 #2

https://git.zziyu.cn/Zengtudor/algorithm_2024/src/branch/main/src/20241116/necklace

样例输出 #2

https://git.zziyu.cn/Zengtudor/algorithm_2024/src/branch/main/src/20241116/necklace

提示

对于 100% 的数据，1\le n,q\le 10^5, 1\le u,v\le n, 1\le c[i]\le n，保证询问中的 u 在 1\sim v 的路径上，u=v 是有可能的

子任务1（20pts）：n,q\le 100

子任务2（25pts）：n,q\le 5000

子任务3（10pts）：成链，(i,i+1) 之间有边

子任务4（20pts）：c[i]\le 10

子任务5（25pts）：无特殊限制

45pts解

#include <cstdint>
#include <iostream>
#include <istream>
#include <set>
#include <vector>

using ll = int64_t;
using std::cin, std::cout;

const ll max_n = 1e5+5, rt{1};

ll n, q, c[max_n], fts[max_n];
std::vector<ll> edges[max_n];

void fd_ft(const ll &ft, const ll &now){
    fts[now] = ft;
    for(const ll &nxt: edges[now]){
        if(nxt==ft)continue;
        fd_ft(now, nxt);
    }
}

int main(){
    std::iostream::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin>>n>>q;
    for(ll i{1};i<=n;i++){
        cin>>c[i];
    }
    for(ll i{1};i<n;i++){
        ll u, v;
        cin>>u>>v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    fd_ft(0, rt);
    for(ll i{1};i<=q;i++){
        ll u, v;
        cin>>u>>v;
        std::set<ll> pts;
        pts.emplace(c[u]);
        while(v!=u){
            pts.emplace(c[v]);
            v=fts[v];
        }
        cout<<pts.size()<<'\n';
    }
}

官方题解

和原题（P1972）类似，定义每个点的前驱：路径上和颜色相同、且深度最大的点（若不存在定义为 0）。

DFS 过程中维护子树中的答案，从当前点 u 开始，离开时更新：

  • 子树的答案
  • 对于所有 u 的子节点的答案
  • 回答这个点的所有询问

可以使用任何支持区间修改、单点求值的数据结构实现。

时间复杂度：O(N \log N)。

stack<int> stc[MAXN];
int pre[MAXN];
int st[MAXN], ed[MAXN], tt = 0;

void dfs1(int u, int fa) { // 求 pre
    st[u] = ++tt;
    if (stc[c[u]].size()) {
        pre[u] = stc[c[u]].top();
        adjp[pre[u]].push_back(u);
    }
    stc[c[u]].push(u);

    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs1(v, u);
    }
    stc[c[u]].pop();
    ed[u] = tt;
}

void dfs2(int u, int fa) {
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs2(v, u);
    }
    change(rt, st[u], ed[u], +1); // u 子树 +1
    for (int v : adjp[u]) change(rt, st[v], ed[v], -1); // pre[v]=u 的 v 子树 -1

    for (req _ : adjq[u]) { // 查询 ans
        int v = _.v, id = _.id;
        ans[id] = query(rt, st[v], 0);
    }
}

原型题自己的代码 P1972

我寻思这道题还是不会写就先写上文提到的原型题

这段代码使用的是离线处理+树状数组的算法来高效解决范围查询的问题。对于每个查询，它计算某个区间 [l, r] 内有多少种不同的贝壳。下面是详细的讲解和逐步分析，以及相应的注释添加。

核心思想

  • 树状数组（Fenwick Tree）：用于高效维护和查询数组的前缀和，时间复杂度为 O(log n)。
  • 离线算法：将查询提前记录下来，然后按 r（右端点）排序，通过遍历项链处理每个查询。
  • 去重处理：当遇到重复的贝壳时，需要将上一次出现的位置的贡献移除，并在当前的位置添加新的贡献。

代码逐步解析和注释

#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <iostream>
#include <istream>

using ll = int64_t;
using std::cin, std::cout;

const ll maxn = 1e6 + 5;
ll n, kds[maxn], m, anss[maxn], viss[maxn], bits[maxn];  // 全局变量声明

struct Sch {
    ll l, r, pos;  // 表示查询的区间 [l, r] 和其在输入中的位置
} schs[maxn];

// 返回 `v` 的最低位 1，树状数组使用
ll lb(const ll &v) {
    return v & (-v);
}

// 在树状数组中增加值操作
void tadd(ll idx, const ll &v) {
    while (idx <= n) {
        bits[idx] += v;  // 更新 idx 位置上的值
        idx += lb(idx);  // 移动到下一个需要更新的位置
    }
}

// 查询树状数组的前缀和
ll tpsch(ll idx) {
    ll res = 0;
    while (idx != 0) {
        res += bits[idx];  // 累加从 idx 开始的值
        idx -= lb(idx);    // 移动到上一个有效位置
    }
    return res;  // 返回前缀和
}

int main() {
    std::iostream::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    // 输入项链长度 n 和项链内容
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> kds[i];  // 第 i 个贝壳种类
    }
    // 输入查询数 m
    cin >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> schs[i].l >> schs[i].r;  // 输入每个查询的区间
        schs[i].pos = i;  // 保存查询的原始位置
    }

    // 按照查询区间的右端点 r 升序排序
    std::sort(schs + 1, schs + 1 + m, [](const Sch &a, const Sch &b) -> bool {
        return a.r < b.r;
    });

    ll nm = 1;  // 记录当前处理的查询索引
    for (ll i = 1; i <= n; i++) {
        // 检查当前贝壳是否已被访问过
        if (viss[kds[i]]) {
            // 如果该贝壳之前出现过，则在树状数组中移除其在上次位置的贡献
            tadd(viss[kds[i]], -1);
        }
        // 更新该贝壳在树状数组中的新位置
        viss[kds[i]] = i;
        tadd(i, 1);

        // 处理当前右端点为 i 的所有查询
        if (i == schs[nm].r) {
            do {
                // 获取当前查询的答案，利用树状数组查询[l, r]内的前缀和差
                anss[schs[nm].pos] = tpsch(schs[nm].r) - tpsch(schs[nm].l - 1);
                nm++;  // 处理下一个查询
            } while (nm <= m && schs[nm].r == schs[nm - 1].r);  // 若下一个查询的 r 相同，继续处理
        }
    }

    // 输出每个查询的答案
    for (ll i = 1; i <= m; i++) {
        cout << anss[i] << '\n';
    }
}

详细解释

  1. 输入和初始化：

    • n 表示项链长度，kds 存储项链中的贝壳类型。
    • m 表示查询的个数，schs 数组存储每个查询的区间 [l, r] 和其原始位置 pos。

  2. 树状数组函数：

    • lb 计算最低位 1，用于定位树状数组的更新步长。
    • tadd 用于更新树状数组中某个索引位置的值。
    • tpsch 查询树状数组从 1 到 idx 的前缀和。

  3. 离线处理查询：

    • 查询根据 r 进行升序排序，以便逐一扩展右边界进行处理。
    • 遍历项链，当 kds[i] 已出现过时，移除其在上次位置的贡献，然后更新其在当前的位置。
    • 每当处理到一个查询的右端点 r 时，使用树状数组计算结果。

  4. 复杂度：

    • 排序 O(m log m)。
    • 每次更新或查询树状数组 O(log n)，整体时间复杂度约为 O(n log n + m log m)，适合大规模数据。

优化思路

  • 该实现已接近最优解，通过使用树状数组和离线处理达到了较好的性能。
  • 在读入大数据时，使用 scanf/printf 可提高 IO 性能。

继续思考原题是怎么拿满

未完待续

Zengtudor

© 2024 曾子愚 's Blog