20220514 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

线段树分治 + 可撤销并查集动态维护直径，dp + 分块，贪心，dp + 树状数组

# A. 越野赛车问题

考虑对值域进行线段树分治，把在分治区间 $[L, R]$ 的边连上，动态维护树的直径即可。

关于如何维护直径，就是把原来直径的两个端点和新加进来的边的两个端点组合一下，距离最远的两个点就是新的直径。

再开个可撤销并查集维护历史直径信息，就可以动态更新了。

直接贺板子，好耶。

$code$

#include <bits/stdc++.h>
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
#define fi first
#define se second

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
int n, m;
struct node{
    int u, v;
}e[N];
vector <int> g[N], t[N << 2];

int fa[N], siz[N], son[N], dep[N];

inline void dfs1(int x, int f){
    fa[x] = f, siz[x] = 1, dep[x] = dep[f] + 1;
    for(auto y : g[x]){
        if(y == f) continue;
        dfs1(y, x), siz[x] += siz[y];
        if(siz[y] > siz[son[x]]) son[x] = y;
    }
}

int top[N];

inline void dfs2(int x, int topfa){
    top[x] = topfa;
    if(son[x]) dfs2(son[x], topfa);
    for(auto y : g[x])
        if(y != fa[x] && y != son[x]) dfs2(y, y);
}

inline int lca(int x, int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[x];
    }
    return dep[x] < dep[y] ? x : y;
}

inline int dist(int x, int y){
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}


struct Path{
    int p1, p2, dis;
    Path() {}
    Path(int _p1, int _p2) {p1 = _p1, p2 = _p2, dis = dist(p1, p2);}
    inline bool operator < (const Path &b) const {
        return dis < b.dis;
    }
    friend inline Path merge(Path x, Path y){
        Path p = max(x, y);
        p = max(p, max(Path(x.p1, y.p1), Path(x.p1, y.p2)));
        p = max(p, max(Path(x.p2, y.p1), Path(x.p2, y.p2)));
        return p;
    }
};

struct Dsu{
    Path p;
    int fa, siz;
}dsu[N];

struct Stack{
    int x, y;
    Path px, py;
    Stack() {}
    Stack(int _x, int _y, Path _px, Path _py){
        x = _x, y = _y, px = _px, py = _py;
    }
}stk[N];
int stop;

inline int find(int x){
    return dsu[x].fa == x ? x : find(dsu[x].fa);
}

inline int Union(int x, int y){
    x = find(x), y = find(y);
    if(dsu[x].siz < dsu[y].siz) swap(x, y);
    stk[++stop] = Stack(x, y, dsu[x].p, dsu[y].p);
    dsu[y].fa = x, dsu[x].siz += dsu[y].siz;
    dsu[x].p = merge(dsu[x].p, dsu[y].p);
    return dsu[x].p.dis;
}

inline void Delete(){
    Stack s = stk[stop--];
    int x = s.x, y = s.y;
    dsu[y].fa = y, dsu[x].siz -= dsu[y].siz;
    dsu[x].p = s.px, dsu[y].p = s.py;
}

int ans[N];

inline void update(int L, int R, int x, int l, int r, int rt){
    if(L > R || L > r || R < l) return;
    if(L <= l && r <= R) return t[rt].pb(x), void();
    update(L, R, x, l, mid, ls), update(L, R, x, mid + 1, r, rs);
}

inline void solve(int len, int l, int r, int rt){
    int now = stop;
    for(auto x : t[rt]) len = max(len, Union(e[x].u, e[x].v));
    if(l == r) ans[l] = ~ans[l] ? ans[l] : len;
    else solve(len, l, mid, ls), solve(len, mid + 1, r, rs);
    while(stop != now) Delete();
}

signed main(){
    n = read(), m = read();
    for(int i = 1; i < n; ++i){
        int u = read(), v = read(), l = read(), r = read();
        e[i] = (node){u, v}, update(l, r, i, 1, n, 1);
        g[u].pb(v), g[v].pb(u);
    }
    dfs1(1, 0), dfs2(1, 1);
    memset(ans, -1, sizeof(ans));
    for(int i = 1; i <= n; ++i) dsu[i] = (Dsu){Path(i, i), i, 1};
    solve(0, 1, n, 1);
    for(int i = 1; i <= m; ++i) write(ans[read()]), puts("");
    return 0;
}

# B. Native - DP II

CF101E Candies and Stones

非常显然的 $\text{dp}$ ，设 $f_{i, j}$ 表示走到 $i, j$ 的最大收益，那么转移就是：

$f_{i, j} = \max\{f_{i - 1, j} + f_{i, j - 1} + val_{i, j} \}$

但是这样空间复杂度是 $O(nm)$ 的，不知道比 $\text{43.95M}$ 高了多少。

考虑如何优化空间。

我们把 $n \times m$ 的矩阵按行分块，即每处理 $\sqrt n$ 行存一下答案，记录 $\text{dp}$ 值，以及路径。

最后再倒着枚举每一块跑一遍 $\text{dp}$ ，找路径。

$code$

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e4 + 10;
const int B = 150;
int n, m, mod, t, l = 1;
int x[N], y[N], f[B][N], g[B][N], df[B][N], dg[2][N];
int dir[2][N], dp[2][N];
stack <int> ans;

inline int add(int x) {return x >= mod ? x % mod : x;}

signed main(){
    n = read() - 1, m = read() - 1, mod = read(), t = max(sqrt(n), 1.0);
    for(int i = 0; i <= n; ++i) x[i] = read();
    for(int i = 0; i <= m; ++i) y[i] = read();
    for(int i = 0; i <= n; ++i, l ^= 1){
        memset(dir[l], 0, sizeof(dir[l]));
        memset(dp[l], 0, sizeof(dp[l]));
        for(int j = 0; j <= m; ++j){
            dp[l][j] = dp[l ^ 1][j] + add(x[i] + y[j]), dir[l][j] = 1;
            if(j && dp[l][j] < dp[l][j - 1] + add(x[i] + y[j]))
                dp[l][j] = dp[l][j - 1] + add(x[i] + y[j]), dir[l][j] = 0;
        }
        if(i % t == 0){
            memcpy(f[i / t], dp[l], sizeof(dp[l]));
            memcpy(g[i / t], dir[l], sizeof(dir[l]));
        }
    }
    int tx = n, ty = m;
    for(int i = n / t; i >= 0; --i){
        memcpy(df[0], f[i], sizeof(f[i]));
        memcpy(dg[0], g[i], sizeof(g[i]));
        for(int j = i * t + 1; j <= min(n, (i + 1) * t); ++j){
            for(int k = 0; k <= m; ++k){
                df[j - i * t][k] = df[j - i * t - 1][k] + add(x[j] + y[k]), dg[j - i * t][k] = 1;
                if(k && df[j - i * t][k] < df[j - i * t][k - 1] + add(x[j] + y[k]))
                    df[j - i * t][k] = df[j - i * t][k - 1] + add(x[j] + y[k]), dg[j - i * t][k] = 0;
            }
        }
        while(tx >= (i * t + 1)){
            ans.push(dg[tx - i * t][ty]);
            if(!dg[tx - i * t][ty]) ty--;
            else tx--;
        }
    }
    while(ty) ans.push(0), ty--;
    write(dp[l ^ 1][m]), puts("");
    while(!ans.empty()) putchar(ans.top() ? 'C' : 'S'), ans.pop();
    return 0;
}

# C. 椅子

AT2645 [ARC076D] Exhausted?

可以直接暴力最大流，能拿不少部分分。

然后考场上以为是线段树优化建图什么的，然而并不是。

本题大力贪心即可。

首先一个假贪心：

按照 $l_i$ 从小到大排序，相同的按 $r_i$ 从小到大排序。
对于每个人先在左边找，让他在 $\leq l_i$ 的最右边的空位置坐下，如果左边没有位置了，让他去右边找，在 $\geq r_i$ 的最左边的空位置坐下，如果都没有就加一张椅子。
这个贪心可以被以下数据 $\text{hack}$ ：
1
2
3
4
3 4
1 3
2 5
2 5

如何避免这一情况呢？

重新考虑这一过程，还是和上面一样的操作。

我们考虑到了第 $i$ 个人，在 $l_i$ 左边找到了空位置，让 $i$ 坐下。

这时第 $j$ 个人来了，但是我们在 $l_j$ 左边找不到空位置了，我们考虑是否让 $i$ 起来，去右边找位置，并让 $j$ 坐在 $i$ 坐的位置上（排过序了，所以 $i$ 坐的位置 $j$ 肯定能坐）。

如何维护这一“反悔”操作呢？

我们开一个小根堆，如果 $i$ 在 $\leq l_i$ 找到了空位置，我们把 $r_j$ 插入到小根堆中。

还是考虑如果 $i$ 在左边找不到位置，此时堆顶为 $r_j$ ，我们分两种情况讨论：

$r_i < r_j$ ，那就直接让 $i$ 去右边找个空位置坐下就行。
$r_i \geq r_j$ ，我们让 $i$ 去坐 $j$ 的位置，然后让 $j$ 去 $\geq r_j$ 找空位置。

然后就 $\text{ok}$ 了。

$code$

代码中找空位置坐下跟上面略有不同，自己看代码理解一下吧 QwQ

#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e5 + 10;
int n, m;
struct node{
    int l, r;
    inline bool operator < (const node &b) const{
        return l != b.l ? l < b.l : r < b.r;
    }
}p[N];
priority_queue <int, vector<int>, greater<int> > q;
int pos = 1, ans, tot;
int R[N];

signed main(){
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) p[i] = (node){read(), read()};
    sort(p + 1, p + 1 + n);
    for(int i = 1; i <= n; ++i){
        q.push(p[i].r);
        if(pos > p[i].l || pos > m) R[++tot] = q.top(), q.pop();
        else pos++;
    }
    sort(R + 1, R + 1 + tot);
    for(int i = tot, j = m; i >= 1; --i){
        if(j >= pos && j >= R[i]) j--;
        else ans++;
    }
    write(ans), puts("");
    return 0;
}

# D. 方舟系统

本来是没这题的，但是 $\text{B}$ 题大家之前都做过，所以就加了道题 /kk

$O(n^2)$ 的暴力 $\text{dp}$ 非常好想，设 $f_i$ 表示处理到了第 $i$ 个数，最少的代价。

转移方程：

$f_i = \min\{f_{j- 1} + |a_j - (i - j)| \}$

能得 $\text{60pts}$ ，好耶。

那么如何优化呢？

我们转移过程中就取了个最小值，所以我们只要能够维护一手前缀最小值即可。

先把这个绝对值打开，即 $a_j - (i - j)$ 或者 $(i - j) - a_j$ 。

$i$ 是定值，不用管它，所以就剩下了 $a_j + j$ 和 $-a_j - j$ 。

所以我们开两个树状数组，分别维护 $f_{j - 1} + a_j + j$ 和 $f_{j - 1} - a_j - j$ 的最小值。

不要忘记这两个值可不是想用就能用的，绝对值的符号是固定的，所以一个是前缀最小值，一个是后缀最小值，自己判断一下吧。

$code$

#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 10;
const int inf = 1e9 + 1e5;
int n;
int a[N], f[N];

unordered_map <int, int> c1, c2;

inline void add1(int x, int y){
    for(; x; x -= x & (-x)) 
        c1[x] = c1.find(x) != c1.end() ? min(c1[x], y) : y;
}

inline int qry1(int x){
    int res = inf;
    for(; x <= inf; x += x & (-x))
        res = c1.find(x) != c1.end() ? min(res, c1[x]) : res;
    return res;
}

inline void add2(int x, int y){
    for(; x <= inf; x += x & (-x))
        c2[x] = c2.find(x) != c2.end() ? min(c2[x], y) : y;
}

inline int qry2(int x){
    int res = inf;
    for(; x; x -= x & (-x))
        res = c2.find(x) != c2.end() ? min(res, c2[x]) : res;
    return res;
}

signed main(){
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i){
        int r1 = qry1(i), r2 = qry2(i);
        f[i] = min(r1 - i, r2 + i);
        add1(a[i] + i, f[i - 1] + a[i] + i), add2(a[i] + i, f[i - 1] - a[i] - i);
    }
    write(f[n]), puts("");
    return 0;
}

# A. 越野赛车问题

# B. Native - DP II

# C. 椅子

# D. 方舟系统

dp 题目选做

20220518