《信息学奥赛一本通·高手专项训练》集训 Day 6

· · 个人记录

树状数组

\color{Green}100\color{Black}+\color{Green}100\color{Black}+\color{Red}0\color{Black}=\color{#92E411}200\color{Black}/\color{Silver}\text{Rank 2}

\color{#52C41A}\text{A. 书籍分配}

题目

现在有 n 个书架，一开始没有任何书。有两种操作：

题解

有个很显然的贪心思想是，让这 s 个人尽量拿书本数量 \ge s 的书柜上的书。

这个常识般的思维给我们的发现是，尽量拿书本数量 \ge s 的书柜上的书会导致多出一些书无法使用，而拿书本数量 < s 的书柜上的书则在总数满足要求的情况下一定不会出现有书而没有 c 个书柜拿的情况。

对于后者的证明：设书本数量 < s 的书柜的书的数量为 a_{1\sim k}，则 \sum_{i=1}^ka_i\ge c\times s,a_i<s，所以 k>c，显然这个条件是任何时候都满足的所以后者是正确的。

因此，设书本数量 \ge s 的书柜数量为 cnt，只要满足两个之一，操作就能成功：

用权值树状数组维护每个数值的出现次数和数值和即可。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 2e6 + 10;
int n, m;
struct que {
    int opt;
    ll x, y, y_;
} q[N];
ll c1[N], c2[N], b[N], tot, a[N], d[N];
void add1(int x, ll v) {
    for (; x <= tot; x += x & -x) c1[x] += v;
}
void add2(int x, ll v) {
    for (; x <= tot; x += x & -x) c2[x] += v;
}
ll ask1(int x) {
    ll ans = 0;
    for (; x; x -= x & -x) ans += c1[x];
    return ans;
}
ll ask2(int x) {
    ll ans = 0;
    for (; x; x -= x & -x) ans += c2[x];
    return ans;
}
int main() {
    freopen("book.in", "r", stdin);
    freopen("book.out", "w", stdout);
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        char op;
        ll x, y;
        cin >> op;
        q[i].x = read();
        q[i].y = read();
        b[i] = q[i].y;
        q[i].opt = (op == 'Z');
    }
    b[m + 1] = 0;
    sort(b + 1, b + m + 2);
    tot = unique(b + 1, b + m + 2) - b - 1;
    for (int i = 1; i <= m; i++)
        q[i].y_ = lower_bound(b + 1, b + tot + 1, q[i].y) - b;
    for (int i = 1; i <= n; i++) {
        a[i] = 1;
        add1(1, 1);
    }
    for (int i = 1; i <= m; i++) {
        if (q[i].opt == 0) {
            add1(a[q[i].x], -1);
            add2(a[q[i].x], -d[q[i].x]);
            a[q[i].x] = q[i].y_;
            d[q[i].x] = q[i].y;
            add1(a[q[i].x], 1);
            add2(a[q[i].x], d[q[i].x]);
        } else {
            if (ask2(tot) < q[i].x * q[i].y) {
                puts("NIE");
                continue;
            }
            ll c_ = q[i].x - (ask1(tot) - ask1(q[i].y_ - 1));
            if (ask2(q[i].y_ - 1) >= c_ * q[i].y)
                puts("TAK");
            else
                puts("NIE");
        }
    }
    return 0;
}

\color{#3498DB}\text{B.最优团队}

题目

有 n 个人，按 1\sim n 进行编号，编号为 i 的人有属性 a_i 和 r_i。

定义一个团队由一个队长与若干个队员组成，其中队员人数要至少有一人，队长必须有且只能有一人。

设队长的编号为 x，队员编号组成的集合为 S，那么队员与队长必须满足：

\forall y\in S,r_x\ge r_y\&|a_x-a_y|\le K

其中 K 为给定的参数。

有 m 组询问，每组询问给定两个数 x,y，询问编号为 x 和 y 的人在同一个团队内时，团队最多可以有多少人（在符合条件的前提下，队长可以是包括 x 和 y 在内的任何人）。

题解

我们发现每个人做队长可以带的最多的人数是固定的，于是可以预处理出每个人做队长可以带的最多的人数。具体来说，按 r_i 从小到大枚举队员 x，用树状数组维护每个 a_i 出现的次数，那么 x 做队长最多的成员数为 a_i 在 [a_x-K,a_x+K] 的成员的个数。

然后考虑询问，对于一组询问 x,y，设 a_x<a_y，则一个人能做 x,y 的队长需要满足 r_i\ge \max(r_x,r_y),a_i\in[a_x+K,a_y-K]，这回我们可以把询问离线，按 r_i 从大到小把每个人做队长最多的成员数扔进线段树里，如果 r_i=\max(r_x,r_y)，则询问 x,y 的答案为 [a_x+K,a_y-K]] 的最大值。如果 a_x+K>a_y-K 则无法组成团队，输出 -1。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 4e5 + 10;
int n, k, r[N], a[N], m, res[N], head[N], nxt[N];
int c[N], b[N], t, d[N], ma[N], ans[N];
vector<int> e[N];
struct asdf {
    int x, y;
} q[N];
bool cmp1(int x, int y) { return r[x] < r[y]; }
void add(int x, int v) {
    for (; x <= t; x += x & -x) c[x] += v;
}
int ask(int x) {
    int ans = 0;
    for (; x; x -= x & -x) ans += c[x];
    return ans;
}
#define pl p << 1

#define pr p << 1 | 1

#define S_T_T int

struct Segment_Tree {
    struct Tree {
        int l, r;
        S_T_T val;
    } a[N * 4];
    void pushup(int p) { a[p].val = max(a[pl].val, a[pr].val); }
    void build(int p, int l, int r) {
        a[p].l = l;
        a[p].r = r;
        if (l == r) {
            a[p].val = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(pl, l, mid);
        build(pr, mid + 1, r);
        pushup(p);
    }
    void change(int p, int x, S_T_T v) {
        if (a[p].l == a[p].r) {
            a[p].val = max(a[p].val, v);
            return;
        }
        int mid = (a[p].l + a[p].r) >> 1;
        if (x <= mid)
            change(pl, x, v);
        if (x > mid)
            change(pr, x, v);
        pushup(p);
    }
    S_T_T ask(int p, int l, int r) {
        if (l <= a[p].l && a[p].r <= r) {
            return a[p].val;
        }
        int mid = (a[p].l + a[p].r) >> 1;
        S_T_T ans = 0;
        if (l <= mid)
            ans = max(ans, ask(pl, l, r));
        if (r > mid)
            ans = max(ans, ask(pr, l, r));
        return ans;
    }
} tree;
int main() {
    freopen("group.in", "r", stdin);
    freopen("group.out", "w", stdout);
    n = read();
    k = read();
    for (int i = 1; i <= n; i++) {
        b[++t] = r[i] = read();
        d[i] = i;
    }
    sort(b + 1, b + t + 1);
    t = unique(b + 1, b + t + 1) - b - 1;
    for (int i = 1; i <= n; i++) r[i] = lower_bound(b + 1, b + t + 1, r[i]) - b;
    t = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        b[++t] = a[i];
        b[++t] = a[i] - k;
        b[++t] = a[i] + k;
    }
    sort(b + 1, b + t + 1);
    t = unique(b + 1, b + t + 1) - b - 1;
    for (int i = 1; i <= n; i++) {
        head[i] = lower_bound(b + 1, b + t + 1, a[i] - k) - b;
        nxt[i] = lower_bound(b + 1, b + t + 1, a[i] + k) - b;
        a[i] = lower_bound(b + 1, b + t + 1, a[i]) - b;
    }
    sort(d + 1, d + n + 1, cmp1);
    for (int i = 1; i <= n; i++) {
        int j = i;
        while (j + 1 <= n && r[d[j + 1]] == r[d[i]]) j++;
        for (int p = i; p <= j; p++) add(a[d[p]], 1);
        for (int p = i; p <= j; p++)
            res[d[p]] = ask(nxt[d[p]]) - ask(head[d[p]] - 1);
        i = j;
    }
    tree.build(1, 1, t);
    m = read();
    for (int i = 1; i <= m; i++) {
        int x, y;
        x = read();
        y = read();
        if (a[x] > a[y])
            swap(x, y);
        q[i].x = x;
        q[i].y = y;
        e[max(r[x], r[y])].push_back(i);
    }
    for (int i = n; i >= 1; i--) {
        int j = i;
        while (j - 1 >= 1 && r[d[j - 1]] == r[d[i]]) j--;
        for (int p = i; p >= j; p--) tree.change(1, a[d[p]], res[d[p]]);
        for (int p = 0; p < e[r[d[i]]].size(); p++) {
            int w = e[r[d[i]]][p];
            if (nxt[q[w].x] < head[q[w].y])
                ans[w] = -1;
            else
                ans[w] = tree.ask(1, head[q[w].y], nxt[q[w].x]);
            if (ans[w] < 2)
                ans[w] = -1;
        }
        i = j;
    }
    for (int i = 1; i <= m; i++) {
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}

\color{#9D3DCF}\text{C. 拆分集合}

题目

给定一个有 n 个数的序列 h_i，下标从 1 开始，且 h_0=0。把 1\sim n 分成两个集合 S_a,S_b（可以为空），然后再向 S_a 和 S_b 各加入元素 0。对于一个集合 S=\{P_1,P_2,…,P_{|S|}\}，其中 P_1<P_2<…<P_{|S|}，贡献值为 \sum_{i=2}^{|S|}|h_{P_i}-h_{P_{i-1}}|，求两个集合的贡献值的和的最小值。

题解

设 f_{i,j} 表示第一个集合末尾元素为 i，第二个集合末尾元素为 j 的贡献最小值，可以得出：

f_{i,j}=\begin{cases}f_{i-1,j}+|h_i-h_{j-1}|&i-1>j\\\min\{f_{i-1,k}+|h_i-h_k|\}&i-1=j\end{cases}

我们发现如果是连续选择几个数在某个集合，则会进行冗余的计算，只有选择的数被放在的集合不一样时才更有意义，也就是“断点”位置更有用，于是设 G_i=f_{i,i-1}，sum_i=sum_{i-1}+|h_i-h_{i-1}|，所以 G_i=\min\{G_j+sum_{i-1}-sum_j+|h_i-h_{j-1}|\}，答案为 \min\{G_i+sum_n-sum_i\}。

这个转移式算起来仍是 O(n^2) 的，但我们可以把式子变换一下：

G_i=\begin{cases}(G_j-sum_j-h_{j-1})+(sum_{i-1}+h_i)&h_i\ge h_{j-1}\\(G_j-sum_j+h_{j-1})+(sum_{i-1}-h_i)&h_i< h_{j-1}\end{cases}

每个式子前面的部分显然可以用树状数组维护。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 5e5 + 10;
int n;
ll h[N], b[N], c1[N], c2[N], s[N], ans, tot;
void add1(int x, ll v) {
    for (; x <= tot; x += x & -x) c1[x] = min(c1[x], v);
}
void add2(int x, ll v) {
    for (; x <= tot; x += x & -x) c2[x] = min(c2[x], v);
}
ll ask1(int x) {
    ll ans = 1e17;
    for (; x; x -= x & -x) ans = min(ans, c1[x]);
    return ans;
}
ll ask2(int x) {
    ll ans = 1e17;
    for (; x; x -= x & -x) ans = min(ans, c2[x]);
    return ans;
}
int main() {
    freopen("sprung.in", "r", stdin);
    freopen("sprung.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++) {
        b[i] = h[i] = read();
        s[i] = s[i - 1] + abs(h[i] - h[i - 1]);
    }
    memset(c1, 0x3f, sizeof(c1));
    memset(c2, 0x3f, sizeof(c2));
    sort(b + 1, b + n + 1);
    tot = unique(b + 1, b + n + 1) - b;
    ans = s[n];
    add1(1, 0);
    add2(tot + 1, 0);
    for (int i = 2; i <= n; i++) {
        int h_ = lower_bound(b + 1, b + tot, h[i]) - b + 1;
        ll g = min(ask1(h_) + h[i], ask2(tot - h_ + 1) - h[i]) + s[i - 1];
        ans = min(ans, g + s[n] - s[i]);
        h_ = lower_bound(b + 1, b + tot, h[i - 1]) - b + 1;
        add1(h_, g - s[i] - h[i - 1]);
        add2(tot - h_ + 1, g - s[i] + h[i - 1]);
    }
    write(ans);
    return 0;
}

RMQ 问题

\color{Green}100\color{Black}+\color{Orange}50\color{Black}+\color{Red}0\color{Black}=\color{#92E411}150\color{Black}/\color{Silver}\text{Rank 2}

\color{#9D3DCF}\text{A. 数列求值}

题目

给定一个长度为 n 的数列 a。我们可以选择一个正整数 k（不一定要在数列中出现过），然后标记数列中所有小于等于 k 的数。定义此时你的得分为每一个连续极长标记区间的长度的平方之和除以 k。

给定 T 组询问，每组询问给定两个数 l,r(l\le r)，求被标记数组成的连续极长标记区间个数在 [l,r] 之间时你可以得到的最高得分。

连续极长标记区间：我们称区间 [l,r] 为连续极长标记区间，当且仅当 [l,r] 之间的数都被标记，且不存在区间 [l',r']\subsetneq[l,r]，使得 [l',r'] 之间的数都被标记。

本题强制在线。

题解

我们可以从小到大枚举 k，预处理答案。

具体来说，我们可以开个线段树维护当前被标记的数的连续极长标记区间的个数和长度平方和，每次 k 增加 1 后，把新被打标记的位置在线段树中单点修改，然后对整个区间查询，把结果的区间个数处的答案更新上得分。

对于更新后的答案，我们再开一个线段树，维护以区间个数为下标，区间的最大得分，在线回答询问即可。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 3e6 + 10;
int n, t;
ll a[N], k = 1;
vector<int> e[N];
struct ANS {
    ll s, k;
} ans[N], tmp;
bool cmp(ANS x, ANS y) {
    if (x.s == -1)
        return 1;
    if (y.s == -1)
        return 0;
    if (x.s * y.k == y.s * x.k)
        return x.k < y.k;
    return x.s * y.k < y.s * x.k;
}
#define pl p << 1

#define pr p << 1 | 1

#define S_T_T ll

struct Segment_Tree {
    struct Tree {
        int l, r;
        S_T_T sum, lmx, rmx, cnt;
    } a[N * 4], d;
    void pushup(int p) {
        a[p].lmx = a[pl].lmx;
        if (a[pl].lmx == a[pl].r - a[pl].l + 1)
            a[p].lmx += a[pr].lmx;
        a[p].rmx = a[pr].rmx;
        if (a[pr].rmx == a[pr].r - a[pr].l + 1)
            a[p].rmx += a[pl].rmx;
        a[p].sum = a[pl].sum + a[pr].sum;
        a[p].cnt = a[pl].cnt + a[pr].cnt;
        if (a[pl].rmx && a[pr].lmx) {
            a[p].sum += 2 * a[pl].rmx * a[pr].lmx;
            a[p].cnt--;
        }
    }
    void pushdown(int p) { ; }
    void build(int p, int l, int r) {
        a[p].l = l;
        a[p].r = r;
        if (l == r) {
            a[p].sum = a[p].lmx = a[p].rmx = a[p].cnt = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(pl, l, mid);
        build(pr, mid + 1, r);
        pushup(p);
    }
    void change(int p, int x, S_T_T v) {
        if (a[p].l == a[p].r) {
            a[p].sum = a[p].lmx = a[p].rmx = a[p].cnt = v;
            return;
        }
        pushdown(p);
        int mid = (a[p].l + a[p].r) >> 1;
        if (x <= mid)
            change(pl, x, v);
        if (x > mid)
            change(pr, x, v);
        pushup(p);
    }
    Tree ask(int p, int l, int r) {
        if (l <= a[p].l && a[p].r <= r) {
            return a[p];
        }
        pushdown(p);
        int mid = (a[p].l + a[p].r) >> 1;
        if (l <= mid && r > mid) {
            Tree ans, tl = ask(pl, l, r), tr = ask(pr, l, r);
            ans.l = tl.l;
            ans.r = tr.r;
            ans.lmx = tl.lmx;
            if (tl.lmx == tl.r - tl.l + 1)
                ans.lmx += tr.lmx;
            ans.rmx = tr.rmx;
            if (tr.rmx == tr.r - tr.l + 1)
                ans.rmx += tl.rmx;
            ans.sum = tl.sum + tr.sum;
            ans.cnt = tl.cnt + tr.cnt;
            if (tl.rmx && tr.lmx) {
                ans.sum += 2 * tl.rmx * tr.lmx;
                ans.cnt--;
            }
            return ans;
        }
        if (l <= mid)
            return ask(pl, l, r);
        if (r > mid)
            return ask(pr, l, r);
    }
} tree;
struct Segment_Tree2 {
    struct Tree2 {
        int l, r;
        ANS mx;
    } a[N * 4];
    ANS max_(ANS x, ANS y) {
        if (cmp(x, y))
            return y;
        else
            return x;
    }
    void pushup(int p) { a[p].mx = max_(a[pl].mx, a[pr].mx); }
    void build(int p, int l, int r) {
        a[p].l = l;
        a[p].r = r;
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(pl, l, mid);
        build(pr, mid + 1, r);
        pushup(p);
    }
    void change(int p, int x, ANS v) {
        if (a[p].l == a[p].r) {
            a[p].mx = v;
            return;
        }
        int mid = (a[p].l + a[p].r) >> 1;
        if (x <= mid)
            change(pl, x, v);
        if (x > mid)
            change(pr, x, v);
        pushup(p);
    }
    ANS ask(int p, int l, int r) {
        if (l <= a[p].l && a[p].r <= r)
            return a[p].mx;
        int mid = (a[p].l + a[p].r) >> 1;
        ANS ans;
        ans.k = -1;
        ans.s = -1;
        if (l <= mid)
            ans = max_(ans, ask(pl, l, r));
        if (r > mid)
            ans = max_(ans, ask(pr, l, r));
        return ans;
    }
} tree2;
int main() {
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    n = read();
    t = read();
    tree.build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        k = max(k, a[i]);
        e[a[i]].push_back(i);
        ans[i].s = ans[i].k = -1;
    }
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < e[i].size(); j++) tree.change(1, e[i][j], 1);
        tree.d = tree.ask(1, 1, n);
        tmp.s = tree.d.sum;
        tmp.k = i;
        if (!cmp(tmp, ans[tree.d.cnt]))
            ans[tree.d.cnt] = tmp;
    }
    tree2.build(1, 1, n);
    for (int i = 1; i <= n; i++)
        tree2.change(1, i, ans[i]);
    ll lastans = 0;
    for (int i = 1; i <= t; i++) {
        ll a, b, x, y, l, r;
        a = read();
        b = read();
        x = read();
        y = read();
        l = (a * lastans + x - 1) % n + 1;
        r = (b * lastans + y - 1) % n + 1;
        if (l > r)
            swap(l, r);
        ANS c = tree2.ask(1, l, r);
        if (c.s == -1) {
            puts("-1 -1");
            lastans = 1;
            continue;
        }
        printf("%lld %lld\n", c.s, c.k);
        lastans = c.s % n * c.k % n;
    }
    return 0;
}

\color{#9D3DCF}\text{B. 最优序列}

题目

给定一个长度为 n 的序列 a_i，下标从 1 开始。

再给定两个正整数 l,r。

对于所有的 1\le i\le n，求

f_i=\max_{1\le x\le i\le y\le n\land l\le y-x+1\le r}\{\sum_{j=x}^ya_j\}

题解

其实 f_i 就是包含 i 的长度在 l\sim r 之间的最大的区间和，\sum_{j=x}^ya_j 可以转化为前缀和相减，即 sum_y-sum_{x-1}。

考虑对于一个区间 $[l,r]$，如何更新 $f_i$： 1. $f_i$ 被 $[l,mid]$ 中的点对更新。 1. $f_i$ 被 $[mid+1,r]$ 中的点对更新。 1. $f_i$ 被左端点在 $[l,mid]$ ，右端点在 $[mid+1,r]$ 中的点对更新。 对于前两种情况，递归解决即可，对于第三种情况，对于 $i\in [l,mid]$ 的 $f_i$，若以 $i$ 为序列左端点计算答案：$\max_{\max(i+L-1,mid)\le j\le \min(i+R-1,r)}\{sum_j-sum_{i-1}\}$，则得到的答案可以更新 $f_i$ 值，能更新 $f_i$ 的还有所有以 $j\in [l,i-1]$ 为开头的序列的相应答案，计算前缀最大值即可，求答案时要维护 $sum_i$ 的区间最值，用 $\text{ST}$ 表即可。 对于 $i\in [mid+1,r]$ 的 $f_i$ 也同理。 ### 代码 ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; long long read() { long long x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } return x * f; } void write(long long x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } const int N = 1e5 + 10; int n, L, R; ll a[N], sum[N], f[N], tmp[N]; struct ST { ll f[N][20]; int Log2[N]; ll op(ll x, ll y) { return max(x, y); } void init(int n, ll *a) { memset(f, 0xcf, sizeof(f)); f[0][0] = 0; Log2[0] = -1; for (int i = 1, j = 0; i <= n; i++) { f[i][0] = a[i]; Log2[i] = Log2[i >> 1] + 1; if (i + 1 == 1 << (j + 1)) j++; } Log2[n + 1] = Log2[(n + 1) >> 1] + 1; for (int j = 1; j <= Log2[n + 1]; j++) for (int i = 0; i + (1 << (j - 1)) <= n; i++) f[i][j] = op(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); } ll ask(int l, int r) { int k = Log2[r - l + 1]; return op(f[l][k], f[r - (1 << k) + 1][k]); } } st1; struct ST2 { ll f[N][20]; int Log2[N]; ll op(ll x, ll y) { return min(x, y); } void init(int n, ll *a) { memset(f, 0x3f, sizeof(f)); f[0][0] = 0; Log2[0] = -1; for (int i = 1, j = 0; i <= n; i++) { f[i][0] = a[i]; Log2[i] = Log2[i >> 1] + 1; if (i + 1 == 1 << (j + 1)) j++; } Log2[n + 1] = Log2[(n + 1) >> 1] + 1; for (int j = 1; j <= Log2[n + 1]; j++) for (int i = 0; i + (1 << (j - 1)) <= n; i++) f[i][j] = op(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); } ll ask(int l, int r) { int k = Log2[r - l + 1]; return op(f[l][k], f[r - (1 << k) + 1][k]); } } st2; void solve(int l, int r) { if (l == r) { if (L == 1) f[l] = max(f[l], a[l]); return; } int mid = (l + r) >> 1; solve(l, mid); solve(mid + 1, r); for (int i = l - 1; i <= r + 1; i++) tmp[i] = -1e17; for (int i = l; i <= mid; i++) { if (i + L - 1 <= r && i + R - 1 >= mid) tmp[i] = st1.ask(max(i + L - 1, mid), min(i + R - 1, r)) - sum[i - 1]; tmp[i] = max(tmp[i - 1], tmp[i]); f[i] = max(f[i], tmp[i]); } for (int i = r; i > mid; i--) { if (i - L + 1 >= l && i - R + 1 <= mid) tmp[i] = sum[i] - st2.ask(max(i - R, l - 1), min(i - L, mid)); tmp[i] = max(tmp[i + 1], tmp[i]); f[i] = max(f[i], tmp[i]); } } int main() { freopen("range.in", "r", stdin); freopen("range.out", "w", stdout); n = read(); L = read(); R = read(); for (int i = 1; i <= n; i++) { a[i] = read(); sum[i] = sum[i - 1] + a[i]; } st1.init(n, sum); st2.init(n, sum); memset(f, 0xcf, sizeof(f)); solve(1, n); for (int i = 1; i <= n; i++) cout << f[i] << " "; return 0; } ``` ## $\color{#3498DB}\text{C. 路径覆盖}

题目

有 n 个城市，城市之间有一些道路，城市和道路刚好组成了一棵树。给定 m 条树上路径 (A,B)，有 Q 个询问，每组询问给定两个正整数 L,R(1\le l\le r\le m)，求被从第 L 条路径到第 R 条路径覆盖了 R-L+1 次的边的总长度。

题解

题意转化下就是求第 L 条路径到第 R 条路径的交路径的长度。若要合并路径 (x1,y1),(x2,y2)，则他们合并后的路径交为 \text{LCA}(x1,x2),\text{LCA}(x1,y2),\text{LCA}(y1,x2),\text{LCA}(y1,y2) 中深度较大的两个点之间的路径。

于是就可以用 \text{ST} 表预处理区间路径交，但是需要最快求出 \text{LCA}，我们可以通过树的 \text{dfs} 序 +\ \text{ST} 表预处理 \text{LCA}，做到 O(1) 查询。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 2e5 + 10, M = 4e5 + 10;
int n, m, fm, q;
int dep[N], pos[N], f[M][20], Log[M];
int head[N], ver[M << 1], nxt[M << 1], edge[M << 1], tot;
ll dis[N];
void add(int x, int y, int z) {
    ver[++tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
int lca(int x, int y) {
    x = pos[x];
    y = pos[y];
    if (x > y)
        swap(x, y);
    int k = Log[y - x + 1];
    if (dep[f[x][k]] < dep[f[y - (1 << k) + 1][k]])
        return f[x][k];
    return f[y - (1 << k) + 1][k];
}
struct path {
    int x, y;
    path() {}
    path(int x_, int y_) : x(x_), y(y_) {}
} g[N][20];
bool cmp(int x, int y) { return dep[x] > dep[y]; }
path merge(path a, path b) {
    int c[4];
    c[0] = lca(a.x, b.x);
    c[1] = lca(a.x, b.y);
    c[2] = lca(a.y, b.x);
    c[3] = lca(a.y, b.y);
    sort(c, c + 4, cmp);
    return path(c[0], c[1]);
}
ll ask_path(int x, int y) {
    int k = Log[y - x + 1];
    path p = merge(g[x][k], g[y - (1 << k) + 1][k]);
    return dis[p.x] + dis[p.y] - 2 * dis[lca(p.x, p.y)];
}
void dfs(int x, int fa) {
    dep[x] = dep[fa] + 1;
    f[++fm][0] = x;
    pos[x] = fm;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == fa)
            continue;
        dis[y] = dis[x] + edge[i];
        dfs(y, x);
        f[++fm][0] = x;
    }
}
int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    Log[0] = -1;
    for (int i = 1; i < M; i++) Log[i] = Log[i >> 1] + 1;
    n = read();
    for (int i = 1; i < n; i++) {
        int x, y, z;
        x = read();
        y = read();
        z = read();
        add(x, y, z);
        add(y, x, z);
    }
    dfs(1, 0);
    for (int j = 1; j <= Log[fm]; j++)
        for (int i = 1; i + (1 << j) - 1 <= fm; i++) {
            if (dep[f[i][j - 1]] < dep[f[i + (1 << (j - 1))][j - 1]])
                f[i][j] = f[i][j - 1];
            else
                f[i][j] = f[i + (1 << (j - 1))][j - 1];
        }
    m = read();
    for (int i = 1; i <= m; i++) {
        int u, v;
        u = read();
        v = read();
        g[i][0] = path(u, v);
    }
    for (int j = 1; j <= Log[m]; j++)
        for (int i = 1; i + (1 << j) - 1 <= m; i++)
            g[i][j] = merge(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
    q = read();
    for (int i = 1; i <= q; i++) {
        int l, r;
        l = read();
        r = read();
        write(ask_path(l, r));
        putchar('\n');
    }
    return 0;
}