BZOJ 4012 [HNOI2015]开店

好写好调的点分治,就算可持久化了仍然好写好调。

题目大意

给出一个 nnn 个点的树,每条边有长度,每个点有点权。有 qqq 个询问,每个询问查询点 uuu 到所有权值在 [l,r][l,r][l,r] 中的点的距离之和。

强制在线。

题目链接

BZOJ 4012

题解

首先我们先考虑不强制在线时的做法。

考虑一个经典问题:对于一棵树,支持两种操作:

  • 标记一个点
  • 给出一个点,查询该点到所有已标记点的距离之和

这是一个动态点分治经典题,只需要维护点分治树就可以了。

那么对于不强制在线的版本,我们可以把每个询问拆成两个前缀询问,每个询问查询点 uuu 到所有权值不超过 xxx 的点的距离之和。将点按权值从小到大的顺序依次标记,并且在恰当的时刻计算询问的答案,就可以在 O((n+q)logn)O((n+q)\log n)O((n+q)logn) 时间内解决这个问题。(可以戳这个题 BZOJ 3626

如果要求强制在线呢?注意到在进行标记点的操作时,我们只修改了点分治树中从根出发的一条链。由于点分治树的高度是不超过 logn\log nlogn 的,因此修改的点的数量也不会超过这个量。既然如此,我们可以类比可持久化线段树,对点分治树进行可持久化,在操作时把修改节点改为新建节点。这样时间复杂度没有改变,总体的空间复杂度变为 O(nlogn)O(n\log n)O(nlogn)。而在询问的时候我们仍将询问拆成前缀询问,而对于一个前缀询问只需拿出对应版本的点分治树查询即可。这样每次查询的时间复杂度仍是 O(logn)O(\log n)O(logn) 的,总时间复杂度仍然为 O((n+q)logn)O((n+q)\log n)O((n+q)logn)

吐槽一下,网上树链剖分做法或者点分治加二分的做法都是 O((n+q)log2n)O((n+q)\log^2n)O((n+q)log2n) 的...然而我的做法还不如某些树链剖分跑得快...很多时候复杂度优越并没有什么卵用啊...

代码

这题我只写了3k代码,应该还是比很多其他做法短不少的。

#include <bits/stdc++.h>
#define debug(x) std::cerr << #x << " = " << x << std::endl

typedef long long LL;

const int MAXN = 150031, MAXL = 19;

std::vector<std::pair<int, int>> g[MAXN];

int sz[MAXN], l[MAXN], idx[MAXN][MAXL];
LL d[MAXN][MAXL];
bool vis[MAXN];

void gs(int u, int p) {
    sz[u] = 1;
    for (auto &e : g[u]) if (!vis[e.first] && e.first != p) gs(e.first, u), sz[u] += sz[e.first];
}

int ctrd(int u, int p, int hs) {
    for (auto &e : g[u]) if (!vis[e.first] && e.first != p && sz[e.first] > hs) return ctrd(e.first, u, hs);
    return u;
}

void gdis(int u, int p, int ly) {
    for (auto &e : g[u]) if (!vis[e.first] && e.first != p) idx[e.first][ly] = idx[u][ly], d[e.first][ly] = d[u][ly] + e.second, gdis(e.first, u, ly);
}

int dc(int u, int ly) {
    int ctr = (gs(u, 0), ctrd(u, 0, sz[u] / 2)), c = 0;
    vis[ctr] = 1, l[ctr] = ly;
    for (auto &e : g[ctr])
        if (!vis[e.first]) {
            d[e.first][ly] = e.second, idx[e.first][ly] = c++;
            gdis(e.first, ctr, ly), dc(e.first, ly + 1);
        }
    return ctr;
}

struct N {
    N *ch[3];
    LL s, sf, c;

    N() {}
    N(N *ch0, N *ch1, N *ch2) : ch{ch0, ch1, ch2}, s(0), sf(0), c(0) {};
} *_nil = new N(), *nil = &(*_nil = N(_nil, _nil, _nil)), pool[MAXN * MAXL], *top = pool, *rt[MAXN] = {nil};

void insert(N *&x, N *p, int u, int ly) {
    *(x = top++) = *p;
    x->s += d[u][ly], x->sf += d[u][ly - 1], x->c++;
    if (ly != l[u]) insert(x->ch[idx[u][ly]], p->ch[idx[u][ly]], u, ly + 1);
}

LL query(N *x, int u, int ly) {
    return (ly == l[u] ? 0LL : query(x->ch[idx[u][ly]], u, ly + 1)) + x->s - x->sf + x->c * (d[u][ly] - d[u][ly - 1]);
}

int n = 0, q = 0, p = 0;

std::pair<int, int> x[MAXN];

int id(int a) {
    int l = 1, r = n + 1;
    for (int mid = 0; l < r; x[mid = (l + r) >> 1].first >= a ? r = mid : l = mid + 1);
    return l - 1;
}

int main() {
    scanf("%d%d%d", &n, &q, &p);
    for (int i = 1, t = 0; i <= n; i++) scanf("%d", &t), x[i] = {t, i};
    std::sort(x + 1, x + n + 1);
    for (int i = 1, u = 0, v = 0, w = 0; i < n; i++) scanf("%d%d%d", &u, &v, &w), g[u].push_back({v, w}), g[v].push_back({u, w});
    int ctr = dc(1, 1);
    for (int i = 1; i <= n; i++) insert(rt[i], rt[i - 1], x[i].second, 1);
    LL lans = 0;
    for (int u = 0, a = 0, b = 0; q--; ) {
        scanf("%d%d%d", &u, &a, &b);
        a = (a + lans) % p, b = (b + lans) % p;
        if (a > b) std::swap(a, b);
        printf("%lld\n", lans = query(rt[id(b + 1)], u, 1) - query(rt[id(a)], u, 1));
    }
    return 0;
}

5 thoughts on “BZOJ 4012 [HNOI2015]开店

  1. 扑通扑通跪下来,千古神犇zyz

  2. 这代码要开C++11,BZOJ上怎么过编译的?是有什么方法能让BZOJ支持C++11吗?

  3. 然而如果没有度数<=3的限制的话没法可持久化……

    • BZOJ上的代码我是把那些 range for 手动展开了... 没有度数小于等于3的话 就加虚点让度数小于等于3就好了呀XD

  4. 我也写了3K……但是跑的绝对很慢

发表评论

电子邮件地址不会被公开。 必填项已用*标注