## 题目描述

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.

## 算法分析

“重心树”上每一层节点的树状数组空间复杂度为$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;
}


## 题目描述

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$.

## 题意概述

$$\sum_{1 \le i \le j \le n} (max_{i, j}-min_{i, j})$$

## 代码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

#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;
}


## 题目描述

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.