T2
CF1303G Sum of Prefix Sums
考虑这个东西的本质其实是 \(\sum (n - i + 1)a_i\)。又对于路径计数问题，我们考虑能否快速合并两个区间的答案，发现这是非常可以的，需要记录的信息也很少。于是考虑点分治，然后对每个重心建李超树查询即可。由于路径有方向，需要正反查两遍。
代码
#include <iostream>
using namespace std;
const int inf = 2147483647;
int n;
long long a[150005];
int head[150005], nxt[300005], to[300005], ecnt;
void add(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
bool ban[150005];
int deg[150005];
struct node {
int fr;
long long down, up, sum;
int len;
} lf[150005];
int lcnt;
struct Line {
long long k, b;
long long operator()(int x) { return k * x + b; }
} T[600005];
struct Segment_Tree {
void Clear(int o, int l, int r) {
T[o] = (Line) { 0, 0 };
if (l == r)
return;
int mid = (l + r) >> 1;
Clear(o << 1, l, mid);
Clear(o << 1 | 1, mid + 1, r);
}
void Insert(int o, int l, int r, Line v) {
if (!T[o].k) {
T[o] = v;
return;
}
int mid = (l + r) >> 1;
if (T[o](mid) < v(mid))
swap(T[o], v);
if (l == r)
return;
long long l1 = T[o](l), l2 = v(l), r1 = T[o](r), r2 = v(r);
if (l1 < l2)
Insert(o << 1, l, mid, v);
if (r1 < r2)
Insert(o << 1 | 1, mid + 1, r, v);
}
long long Query(int o, int l, int r, int x) {
if (l == r)
return T[o](x);
int mid = (l + r) >> 1;
if (x <= mid)
return max(Query(o << 1, l, mid, x), T[o](x));
else
return max(Query(o << 1 | 1, mid + 1, r, x), T[o](x));
}
} seg;
int sz[150005], msz[150005];
int Root, Rsz = inf;
void getroot(int x, int fa, int S) {
sz[x] = 1;
msz[x] = 0;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa && !ban[v]) {
getroot(v, x, S);
sz[x] += sz[v];
msz[x] = max(msz[x], sz[v]);
}
}
msz[x] = max(msz[x], S - sz[x]);
if (msz[x] < Rsz)
Rsz = msz[x], Root = x;
}
// down & len dont count root
// up & sum count root
int dep[150005], mxd;
void dfs(int x, int fa, long long down, long long up, long long sum, int fr) {
sz[x] = 1;
mxd = max(mxd, dep[x] = dep[fa] + 1);
if (deg[x] == 1)
lf[++lcnt] = ((node) { fr, down, up, sum, dep[x] });
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v != fa && !ban[v]) {
dfs(v, x, down + sum + a[v] - a[Root], up + a[v] * (dep[x] + 2), sum + a[v], fr);
sz[x] += sz[v];
}
}
}
long long ans = 0;
void Solve(int x) {
ban[x] = 1;
lcnt = 0;
dep[x] = 0;
mxd = 0;
sz[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (!ban[v]) {
dfs(v, x, a[v], a[v] * 2 + a[x], a[x] + a[v], v);
sz[x] += sz[v];
}
}
seg.Clear(1, 0, mxd);
lf[lcnt + 1].fr = lf[0].fr = -1;
for (int i = 1; i <= lcnt;) {
ans = max(ans, lf[i].down + a[x] * (lf[i].len + 1));
int j = i;
while (lf[j].fr == lf[i].fr) ans = max(ans, seg.Query(1, 0, mxd, lf[j].len) + lf[j].down), ++j;
while (i < j) seg.Insert(1, 0, mxd, (Line) { lf[i].sum, lf[i].up }), ++i;
}
seg.Clear(1, 0, mxd);
for (int i = lcnt; i;) {
int j = i;
while (lf[j].fr == lf[i].fr) ans = max(ans, seg.Query(1, 0, mxd, lf[j].len) + lf[j].down), --j;
while (i > j) seg.Insert(1, 0, mxd, (Line) { lf[i].sum, lf[i].up }), --i;
}
ans = max(ans, seg.Query(1, 0, mxd, 0));
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (!ban[v]) {
Rsz = inf;
getroot(v, 0, sz[v]);
Solve(Root);
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
++deg[u], ++deg[v];
}
for (int i = 1; i <= n; i++) cin >> a[i];
Rsz = inf;
getroot(1, 0, n);
Solve(Root);
cout << ans << "\n";
return 0;
}
T6
CF706F T-shirts
考虑把所有人拥有的钱放在一起考虑。对于每一件衣服，所有当前拥有的钱大于等于当前价格的人会进行购买，之后这些人的钱数减去当前价格，同时答案加一。考虑使用平衡树维护这个东西。若当前价格为 \(p\)，会发现钱数在 \([p, 2p]\) 之间的人钱数减去 \(p\) 之后落在 \([0, p]\)，而这和原本钱数在 \([0, p]\) 的人产生冲突，会导致平衡树无法正常合并（合并要求一棵树的最大值小于等于另一颗的最小值）。因此对于这部分，直接暴力插入即可。容易发现每个人每次被暴力插入会使得其钱数减少至少二分之一，因此每个人被暴力插入的次数在 \(\log\) 级别，总复杂度可以保证。
代码
#include <iostream>
#include <algorithm>
#include <random>
using namespace std;
random_device rd;
mt19937 mtrand(rd());
int n, q;
struct Shirt {
int c, q;
} a[200005];
struct node {
int l, r, v, id, sz, ans;
int tgv, tga;
unsigned pr;
} T[200005];
int ncnt;
int New(int v, int id) {
T[++ncnt] = (node) { 0, 0, v, id, 1, 0, 0, 0, mtrand() };
return ncnt;
}
void pushdown(int x) {
T[T[x].l].v += T[x].tgv;
T[T[x].l].tgv += T[x].tgv;
T[T[x].r].v += T[x].tgv;
T[T[x].r].tgv += T[x].tgv;
T[T[x].l].ans += T[x].tga;
T[T[x].l].tga += T[x].tga;
T[T[x].r].ans += T[x].tga;
T[T[x].r].tga += T[x].tga;
T[x].tga = T[x].tgv = 0;
}
void pushup(int x) { T[x].sz = T[T[x].l].sz + 1 + T[T[x].r].sz; }
void Split(int x, int& l, int& r, int v) {
if (!x)
return l = r = 0, void();
pushdown(x);
if (T[x].v <= v)
Split(T[x].r, T[l = x].r, r, v);
else
Split(T[x].l, l, T[r = x].l, v);
pushup(x);
}
int Merge(int x, int y) {
if (!x || !y)
return x | y;
pushdown(x), pushdown(y);
if (T[x].v > T[y].v)
swap(x, y);
if (T[x].pr < T[y].pr) {
T[x].r = Merge(T[x].r, y);
pushup(x);
return x;
} else {
T[y].l = Merge(x, T[y].l);
pushup(y);
return y;
}
}
int rt;
int to;
void dfs(int x, int v) {
pushdown(x);
if (T[x].l)
dfs(T[x].l, v);
if (T[x].r)
dfs(T[x].r, v);
T[x].l = T[x].r = 0;
pushup(x);
int a, b;
T[x].v -= v, T[x].ans++;
Split(to, a, b, T[x].v);
to = Merge(a, Merge(x, b));
}
int ans[1000005];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].c >> a[i].q;
sort(a + 1, a + n + 1, [](Shirt a, Shirt b) { return (a.q == b.q) ? (a.c < b.c) : (a.q > b.q); });
cin >> q;
for (int i = 1; i <= q; i++) {
int x, y, v;
cin >> v;
Split(rt, x, y, v);
rt = Merge(x, Merge(New(v, i), y));
}
for (int i = 1; i <= n; i++) {
int x, y, z, w;
Split(rt, x, w, a[i].c - 1);
Split(w, y, z, a[i].c << 1);
to = x;
dfs(y, a[i].c);
T[z].v -= a[i].c, T[z].tgv -= a[i].c;
T[z].ans++, T[z].tga++;
rt = Merge(to, z);
}
for (int i = 1; i <= q; i++) cout << ans[i] << " ";
cout << "\n";
return 0;
}