[数据结构与算法] E Eyjafjalla(莫队主席树)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> E Eyjafjalla(莫队主席树) -> 正文阅读

[数据结构与算法]E Eyjafjalla(莫队主席树)

在这里插入图片描述
输入

输出

1
0
3

数据结构题，题意就不写了

思路
首先考虑能达到的最上边，再看从最上边开始的子树有多少符合下界的，可以将用树链剖分知识（dfs序）变为一条链，再对区间操作。
考虑对温度建一棵主席树，用dfs序更新，或者对温度分块，用莫队修改。
具体不简单，详见代码
注意向上找要用倍增，温度要离散化（包括询问时的温度）

主席树

#include <bits/stdc++.h>
// #define x first
// #define y second
typedef long long ll;
const int N = 100100;
#define PII pair<int, int>
const ll mod = (ll)1e9 + 7;
using namespace std;
int n, q;
int t[N], tmp[N];                           //时间戳编号对应的权值
int h[N], e[N << 1], ne[N << 1], idx_path;  //建图
int dfn[N], low[N], timestamp;
int fa[N][31];
vector<int> ve;
struct Query {
    int num;
    int l, r;  //温度
    int x, y;
} qu[N];
struct node {
    int l, r;
    int cnt;
} tr[N * 25];
int root[N], idx;
set<int> se;
int cnt_q;
unordered_map<int, int> id;
int ans[N << 2], belong[N << 2], num;

void add_path(int u, int v) {
    idx_path++;
    e[idx_path] = v, ne[idx_path] = h[u], h[u] = idx_path;
}
void dfs1(int u, int father) {
    dfn[u] = low[u] = ++timestamp;
    ve.push_back(t[u]);
    tmp[dfn[u]] = t[u];
    fa[u][0] = father;
    for (int i = 1; i < 30; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];

    int j;
    for (int i = h[u]; i; i = ne[i]) {
        j = e[i];
        if (j == father) continue;
        dfs1(j, u);
        low[u] = max(low[u], low[j]);
    }
}
int find_root(int x, int l, int r) {
    int zu;
    for (int i = 30; i >= 0; i--) {
        zu = fa[x][i];
        if (t[zu] >= l && t[zu] <= r)  //
            x = zu;
    }
    return x;
}

int build(int l, int r) {
    int p = ++idx;
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    return p;
}

int insert(int p, int l, int r, int x) {
    int q = ++idx;
    tr[q] = tr[p];
    if (l == r) {
        tr[q].cnt++;
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        tr[q].l = insert(tr[p].l, l, mid, x);
    else
        tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

int query(int q, int p, int l, int r, int k) {  //隐含一个上界正无穷(下界k)
    if (l >= k) return tr[q].cnt - tr[p].cnt;
    int ans = 0, mid = l + r >> 1;
    if (k <= mid) ans += query(tr[q].l, tr[p].l, l, mid, k);
    ans += query(tr[q].r, tr[p].r, mid + 1, r, k);
    return ans;
}
void solve() {
    int tot = 0;
    int u, v;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        add_path(u, v), add_path(v, u);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &t[i]);
        se.insert(t[i]);
    }
    dfs1(1, 0);
    // for (int i = 0; i < ve.size(); i++) {
    //     cout << ve[i] << "*";
    // }
    // cout << "\n";
    scanf("%d", &q);
    int x, l, r;
    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d", &x, &l, &r);
        if (!(t[x] >= l && t[x] <= r)) {
            ans[i] = 0;
            continue;
        }
        se.insert(l);
        se.insert(r);
        int root = find_root(x, l, r);
        qu[cnt_q++] = {i, l, r, dfn[root], low[root]};
    }
    for (auto it : se) id[it] = ++tot;
    int ql, qr;
    root[0] = build(1, tot);
    for (int i = 1; i - 1 < ve.size(); i++) {
        root[i] = insert(root[i - 1], 0, tot, id[ve[i - 1]]);
    }
    for (int i = 0; i < cnt_q; i++) {
        int l, r, k;
        l = qu[i].x, r = qu[i].y;
        k = id[qu[i].l];
        ans[qu[i].num] = query(root[r], root[l - 1], 0, tot, k);
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
}
int main() {
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

莫队

在这里插入代码片#include <bits/stdc++.h>
// #define x first
// #define y second
typedef long long ll;
const int N = 100100;
#define PII pair<int, int>
const ll mod = (ll)1e9 + 7;
using namespace std;
int n, q;
int t[N], tmp[N];                      //时间戳编号对应的权值
int h[N], e[N << 1], ne[N << 1], idx;  //建图
int dfn[N], low[N], timestamp;
int fa[N][31];

struct Query {
    int num;
    int l, r;  //温度
    int x, y;
} qu[N];
int cnt_q;
set<int> se;
unordered_map<int, int> id;
int cnt[N << 2];
int sum[N << 2], val[N << 2], num;
int ans[N << 2], belong[N << 2];
int len, block, curl = 1, curr;

void add_path(int u, int v) {
    idx++;
    e[idx] = v, ne[idx] = h[u], h[u] = idx;
}
void dfs(int u, int father) {
    dfn[u] = low[u] = ++timestamp;
    tmp[dfn[u]] = t[u];
    fa[u][0] = father;
    for (int i = 1; i < 30; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];

    int j;
    for (int i = h[u]; i; i = ne[i]) {
        j = e[i];
        if (j == father) continue;
        dfs(j, u);
        low[u] = max(low[u], low[j]);
    }
}
int find_root(int x, int l, int r) {
    int zu;
    for (int i = 30; i >= 0; i--) {
        zu = fa[x][i];
        if (t[zu] >= l && t[zu] <= r)  //
            x = zu;
    }
    return x;
}
bool cmp(Query u, Query v) {
    if (u.x / len == v.x / len) return u.y < v.y;
    return u.x < v.x;
}
void build() {
    int maxx = se.size();
    block = sqrt(maxx);  //注意
    num = maxx / block;
    if (maxx % block) num++;
    for (int i = 1; i <= maxx; i++) {  //注意
        belong[i] = (i - 1) / block + 1;
        sum[belong[i]] += val[i];
    }
}
void add(int x) {
    int fx = id[tmp[x]];
    val[fx]++;
    sum[belong[fx]]++;
}
void del(int x) {
    int fx = id[tmp[x]];
    val[fx]--;
    sum[belong[fx]]--;
}
int ask(int ql, int qr) {
    int ret = 0;
    int st = belong[ql], ed = belong[qr];
    if (st == ed) {
        for (int i = ql; i <= qr; i++)  //
            ret += val[i];

        return ret;
    }
    for (int i = ql; belong[i] == belong[ql]; i++) ret += val[i];

    for (int i = qr; belong[i] == belong[qr]; i--) ret += val[i];

    for (int i = st + 1; i < ed; i++) ret += sum[i];

    return ret;
}
void solve() {
    int tot = 0;
    int u, v;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        add_path(u, v), add_path(v, u);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &t[i]);
        se.insert(t[i]);
    }
    dfs(1, 0);
    len = sqrt(n);
    scanf("%d", &q);
    int x, l, r;
    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d", &x, &l, &r);
        if (!(t[x] >= l && t[x] <= r)) {//答案等于0的不用保存
            ans[i] = 0;
            continue;
        }
        se.insert(l);
        se.insert(r);
        int root = find_root(x, l, r);
        qu[cnt_q++] = {i, l, r, dfn[root], low[root]};
    }
    for (auto it : se) id[it] = ++tot;
    build();
    sort(qu, qu + cnt_q, cmp);
    int ql, qr;
    curl = 1, curr = 0;
    for (int i = 0; i <= cnt_q; i++) {
        int ql = qu[i].x, qr = qu[i].y;
        while (curl > ql) add(--curl);

        while (curl < ql) del(curl++);

        while (curr < qr) add(++curr);

        while (curr > qr) del(curr--);

        ql = id[qu[i].l];
        qr = id[qu[i].r];
        ans[qu[i].num] = ask(ql, qr);
        // cout << "*" << ans[qu[i].num] << "\n";
    }

    for (int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
}
int main() {
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}