Query on the Subtree

题目描述

Bobo has a tree, whose vertices are conveniently labeled by $1, 2, \ldots, n$. At the very begining, the $i$-th vertex is assigned with weight $w_i$.
There are $q$ operations. Each operations are of the following $2$ types:

  • change the weight of vertex $v$ into $x$ (denoted as “! $v$ $x$”),
  • ask the total weight of vertices whose distance are no more than $d$ away from vertex $v$ (denoted as “? $v$ $d$”).

Note that the distance between vertex $u$ and $v$ is the number of edges on the shortest path between them.

题意概述

给定一棵有$n$个节点的树,第$i$个节点的权值为$w_i$。有两种操作:①将节点$v$的权值变成$x$;②询问与节点$v$的距离不超过$d$的所有节点的权值和。共有$q$次操作。
数据范围:$1 \le n, q \le 10^5, \; 0 \le w_i \le 10^4, \; 0 \le x \le 10^4, \; 0 \le d \le n$。

算法分析

对于我们枚举的某一个重心$x$,从它子树的重心向它连一条“虚”边,这样就形成了一棵由重心相连构成的“重心树”。由重心的性质可得,这棵树最多只有$O(\log n)$层。
A Weight Tree
如图,黑色表示原树上的边,红色表示重心树上的“虚”边。
对于每个节点,我们用树状数组存下它在“重心树”上的子树节点到它的距离为$p$(在原树上的距离)的权值和。当我们询问到节点$v$的距离不超过$d$的节点的权值和时,答案就等于$v$的树状数组中$d$的前缀和,再加上“重心树”上$v$的祖先节点$u$的树状数组中$d-dist_{u, v}$的前缀和。可以发现,$u$在“重心树”上包含$v$的子树中的节点被重复计算了。
如图,在计算到节点$3$的距离不超过$3$的节点的权值和时,计算了节点$3$子树中的节点$1, 3, 6, 8$;在计算到节点$3$的祖先节点$2$的距离不超过$3-2=1$的节点的权值和时,节点$1$又被计算了一次。
根据容斥原理,只需对每个节点再用一个树状数组记录下它在“重心树”上的子树节点到它在“重心树”上的父节点的距离为$p$(在原树上的距离)的权值和,每次计算时减去这个树状数组中$d-dist_{u, v}$的前缀和,就得到了正确答案。
修改节点$v$的权值时,只需更新“重心树”上$v$所有祖先节点的树状数组即可。
树上两点间的距离可以通过倍增求LCA得到,不过有更简便的方法。由于每个节点只会被$O(\log n)$个重心搜到,因此可以存下每个节点到其所有祖先重心节点的距离。
在“重心树”上操作的时间复杂度为$O(\log n)$,树状数组的时间复杂度为$O(\log n)$,总时间复杂度为$O(q\log^2n)$。
“重心树”上每一层节点的树状数组空间复杂度为$O(n)$,有$O(\log n)$层,每个节点上要存$O(\log n)$个距离,总空间复杂度为$O(n\log n)$。

代码

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct edge {
    int v, nxt;
} e[200001];
struct binary_indexed_tree {
    int n;
    vector<int> a;
    void init(int size) { n = size + 10, a.clear(), a.resize(n); }
    void add(int p, int t) {
        if (p) for (int i = p; i < n; i += i & -i) a[i] += t;
    }
    int sum(int p) {
        if (p <= 0) return 0;
        int ret = 0;
        for (int i = min(p, n - 1); i; i -= i & -i) ret += a[i];
        return ret;
    }
} tree[200001];
int n, q, nume, tot, top, root, h[100001], w[100001];
int size[100001], f[100001], up[100001], id[100001][2];
bool vis[100001];
vector<int> dist[100001];
void add_edge(int u, int v) {
    e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
    size[t] = 1, f[t] = 0;
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            get_root(e[i].v, t);
            size[t] += size[e[i].v], f[t] = max(f[t], size[e[i].v]);
        }
    }
    f[t] = max(f[t], tot - size[t]);
    if (f[t] < f[root]) root = t;
}
void get_dist(int t, int fa, int depth, int flag) {
    if (flag) dist[t].push_back(depth);
    else {
        tree[id[root][0]].add(depth, w[t]);
        if (dist[t].size() > 1) tree[id[root][1]].add(dist[t][dist[t].size() - 2], w[t]);
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) get_dist(e[i].v, t, depth + 1, flag);
    }
}
void solve(int t) {
    vis[t] = true;
    for (int i = h[t]; i; i = e[i].nxt) if (!vis[e[i].v]) get_dist(e[i].v, t, 1, 0);
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            root = 0, tot = size[e[i].v], get_root(e[i].v, t), up[root] = t;
            tree[id[root][0] = ++top].init(size[e[i].v]);
            tree[id[root][1] = ++top].init(size[e[i].v]);
            tree[id[root][1]].add(dist[root][dist[root].size() - 1], w[root]);
            get_dist(root, 0, 0, 1);
            solve(root);
        }
    }
}
void modify(int t, int d) {
    int p = t, top = dist[t].size() - 1;
    while (p) {
        if (top >= 0) tree[id[p][0]].add(dist[t][top], d);
        if (top > 0) tree[id[p][1]].add(dist[t][top - 1], d);
        p = up[p], --top;
    }
}
int ask(int t, int d) {
    int p = t, ret = 0, top = dist[t].size() - 1;
    while (p) {
        int len;
        if (top >= 0) len = d - dist[t][top];
        if (top >= 0 && len >= 0) ret += tree[id[p][0]].sum(len) + w[p];
        if (top > 0) len = d - dist[t][top - 1];
        if (top > 0 && len >= 0 && up[p]) ret -= tree[id[p][1]].sum(len);
        p = up[p], --top;
    }
    return ret;
}
int main()
{
    while (scanf("%d%d", &n, &q) != EOF) {
        nume = top = 0;
        memset(up, 0, sizeof(up));
        memset(h, 0, sizeof(h));
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &w[i]);
            dist[i].clear();
        }
        for (int i = 1; i < n; ++i) {
            int u, v;
            scanf("%d%d", &u, &v), add_edge(u, v);
        }
        root = 0, tot = f[0] = n, get_root(1, 0);
        tree[id[root][0] = ++top].init(size[1]);
        tree[id[root][1] = ++top].init(size[1]);
        get_dist(root, 0, 0, 1);
        solve(root);
        while (q--) {
            char oper = ' ';
            while (oper != '!' && oper != '?') scanf("%c", &oper);
            int v, d;
            scanf("%d%d", &v, &d);
            if (oper == '!') modify(v, d - w[v]), w[v] = d;
            else printf("%d\n", ask(v, d));
        }
    }
    return 0;
}

Imbalanced Array

题目描述

You are given an array $a$ consisting of $n$ elements. The imbalance value of some subsegment of this array is the difference between the maximum and minimum element from this segment. The imbalance value of the array is the sum of imbalance values of all subsegments of this array.
For example, the imbalance value of array $[1, 4, 1]$ is $9$, because there are $6$ different subsegments of this array:

  • $[1]$ (from index $1$ to index $1$), imbalance value is $0$;
  • $[1, 4]$ (from index $1$ to index $2$), imbalance value is $3$;
  • $[1, 4, 1]$ (from index $1$ to index $3$), imbalance value is $3$;
  • $[4]$ (from index $2$ to index $2$), imbalance value is $0$;
  • $[4, 1]$ (from index $2$ to index $3$), imbalance value is $3$;
  • $[1]$ (from index $3$ to index $3$), imbalance value is $0$.

You have to determine the imbalance value of the array $a$.

题意概述

给定一个长度为$n$的$a$数组,求
$$\sum_{1 \le i \le j \le n} (max_{i, j}-min_{i, j})$$
其中$max_{i, j}$表示$a_i, a_{i+1}, a_{i+2}, \ldots, a_j$中的最大值,$min_{i, j}$表示$a_i, a_{i+1}, a_{i+2}, \ldots, a_j$中的最小值。
数据范围:$1 \le n \le 10^6, \; 1 \le a_i \le 10^6$。

算法分析1

考虑对于第$i$个数$a_i$,设它作为最大值出现的次数为$mx_i$,作为最小值出现的次数为$mn_i$。那么$ans=\sum_{i=1}^n(mx_i-mn_i)a_i$。接下来的问题就变成了求$mx_i, mn_i$。
对于区间$[l, r]$,我们找出其中的最大(小)值,设为$a_j$,那么$a_j$在$[l, r]$上的$mx_i$($mn_i$)就等于$(j-l+1)(r-j+1)$。可以发现,求解区间$[l, j-1]$和$[j+1, r]$是这个问题的子问题,而且规模更小,可以递归求解。只需在开始时先将数组从大到小(从小到大)排序,令$l=1, r=n$,即可解决原问题。
在求解时可以倒过来思考,即从小到大(从大到小)枚举,并将连续的区间合并,用并查集维护。理论时间复杂度为$O(n\log n)$。

代码1

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct number {
    long long num, id, rec;
} a[1000001];
bool cmp(number a, number b) {return a.num < b.num;}
long long n, fa[1000002], s[1000002], ans;
int get_fa(long long t) {
    return t == fa[t] || fa[t] == 0 ? fa[t] : fa[t] = get_fa(fa[t]);
}
void process(int t) {
    int i, j;
    if (t == 1) i = 1, j = n + 1;
    else i = n, j = 0;
    for (; i != j; i += t) {
        fa[a[i].id] = a[i].id;
        s[a[i].id] = 1;
        long long p = get_fa(a[i].id - 1), q = get_fa(a[i].id + 1);
        a[i].rec = (s[p] + 1) * (s[q] + 1);
        if (s[p]) {
            s[p] += s[get_fa(a[i].id)];
            fa[get_fa(a[i].id)] = p;
        }
        if (s[q]) {
            s[q] += s[get_fa(a[i].id)];
            fa[get_fa(a[i].id)] = q;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].num;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    process(1);
    for (int i = 1; i <= n; ++i) {
        ans += a[i].num * a[i].rec;
    }
    memset(fa, 0, sizeof(fa));
    memset(s, 0, sizeof(s));
    process(-1);
    for (int i = 1; i <= n; ++i) {
        ans -= a[i].num * a[i].rec;
    }
    cout << ans << endl;
    return 0;
}

算法分析2

设$l_i, r_i$分别表示$a_i$作为区间$[l, r]$中的最大(小)值时,$l$的最小值和$r$的最大值。那么对于$a_i$来讲,$mx_i(mn_i)=(i-l_i+1)(r_i-i+1)$。$l_i, r_i$均可以$O(n)$维护(DP或单调栈),从而避免了排序。
注意到有多个数相等时会有重复计算的区间。根据容斥原理,在判断时应一边取等号一边不取等号。

代码2

#include <iostream>
using namespace std;
long long n, a[1000001], l[1000001], r[1000001], ans;
void process(int t) {
    for (int i = 1; i <= n; ++i) {
        l[i] = r[i] = i;
    }
    for (int i = 2; i <= n; ++i) {
        int now = i;
        while (now > 1 && a[i] * t >= a[now - 1] * t) now = l[now - 1];
        l[i] = now;
    }
    for (int i = n - 1; i; --i) {
        int now = i;
        while (now < n && a[i] * t > a[now + 1] * t) now = r[now + 1];
        r[i] = now;
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    process(1);
    for (int i = 1; i <= n; ++i) {
        ans += a[i] * (i - l[i] + 1) * (r[i] - i + 1);
    }
    process(-1);
    for (int i = 1; i <= n; ++i) {
        ans -= a[i] * (i - l[i] + 1) * (r[i] - i + 1);
    }
    cout << ans << endl;
    return 0;
}

The Almost Lucky Numbers

题目描述

A lucky number is a number whose decimal representation contains only the digits $4$ and $7$. An almost lucky number is a number that is divisible by a lucky number.
For example, $14, 36$ and $747$ are almost lucky, but $2$ and $17$ are not. Note that a number can be both lucky and almost lucky at the same time (for example, $747$).
You are given long longs $a$ and $b$. Return the number of almost lucky numbers between $a$ and $b$, inclusive.

题意概述

只由$4$和$7$组成的数叫做lucky number,能被lucky number整除的数叫做almost lucky nunber,问区间$[a, b]$中有多少个almost lucky number。
数据范围:$1 \le a \le b \le 10^{10}$。

算法分析

可以发现,lucky number的个数不会很多,而且若某个lucky number是另一个lucky number的倍数,则这个lucky number可以忽略。
易知只需分别求出$[1, a-1]$和$[1, b]$中almost lucky number的个数,两者相减即可得到答案。
下面来研究怎样求出$[1, n]$中almost lucky number的个数。对于在$[1, n]$中的某一个lucky number(设为$p$),区间$[1, n]$中能被它整除的数的个数为$\left\lfloor {n \over p} \right\rfloor$。将这些数删去后,对于在$[1, n]$中的某两个lucky number(设为$p, q$),区间$[1, n]$中能被它们整除的数的个数为$\left\lfloor {n \over LCM(p, q)} \right\rfloor$。因为这些数在之前被删去了两次,所以要将这些数加上。以此类推,利用暴力容斥即可解决此题。
有两个小优化:当某个$LCM$大于$n$时,这个$LCM$可以忽略;从大到小枚举lucky number,使得$LCM$可以很快超过$n$。

Jackpot

题意概述

给定$n$个数$P_i$,求$\lim_{k \to \infty} {S_k \over 2k+1}$,其中$S_k$表示区间$[-k, k]$中能被至少一个$P_i$整除的数的个数。
数据范围:$1 \le n \le 16, \; 1 \le P_i \le 10^9$。

算法分析

观察这个公式,可以发现这就是在所有整数中等概率选取一个数$X$,$X$能被至少一个$P_i$整除的概率。考虑一个非零整数$P$,$X$能被$P$整除的概率为${1 \over P}$。考虑多个整数$P_1, P_2, …, P_m$,$X$能被所有$P_i$整除的概率为${1 \over LCM(P_1, P_2, …, P_m)}$。
根据容斥原理,答案就是将某一个$P_i$整除$X$的概率加起来,再减去某两个$P_i$同时整除$X$的概率,再加上某三个$P_i$同时整除$X$的概率…由于$n \le 16$,直接枚举$P$的所有组合然后按上述方法进行计算即可。
理论上程序的时间复杂度是$O(2^n)$。