20210217 模拟赛总结

Review

T1 难度较低，写了正解，T2、T3写了暴力，不知道 T2 为什么没有分，120pts.
要注意看题，差点就把 T1 看错了，导致误判难度。还有要注意题目中的数据范围，比如 T2 $k\le5$ 就是一个很好的入手条件。

Solution

T1 god

在平面直角坐标系中，在 x 负半轴有一些位置，编号 $1$ ~ $n$ ，正半轴有 $m$ 个点 $(s_i,0)$ 。每个点有一个移动向量 $(x_i,y_i)$ 每一秒按此向量移动 ( $0\le x_i,y_i\le 10^5$ ) ，每个点的价值为它到编号为 $[l_i,r_i]$ 区间内位置的曼哈顿距离和， $q$ 个询问，每个询问给定 $t$ ，求 $y$ 时刻每个点价值的最小值。

设点 i 对时间的价值函数为 $val_i$

由于点只会往右上方跑，所以 $val_i$ 是一个一次函数，对所有的一次函数按斜率由大到小排序，用栈维护上凸壳即可。

查询时二分位置，找到当前最小的函数 $val_k$ ，则答案为 $val_k(t)$ 。

//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

#define int long long

const int MAXN = 3e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;

struct Line {
    int b, k;
    friend bool operator < (Line l1, Line l2) {
        if (l1.k != l2.k)
            return l1.k > l2.k;
        else
            return l1.b < l2.b;
    }
    bool operator == (Line l) {
        return b == l.b && k == l.k;
    }
} line[MAXN];

int n, m, q, cnt;
int s[MAXN], l[MAXN], r[MAXN], x[MAXN], y[MAXN], c[MAXN];
int sum[MAXN];
long double pos[MAXN];
int pid[MAXN];

long double cross_point(int l1, int l2) {
    if (line[l1].k == line[l2].k) return -1;
    long double k1 = line[l1].k, k2 = line[l2].k, b1 = line[l1].b, b2 = line[l2].b;
    return (b2 - b1) / (k1 - k2);
}

int value(int id, int pos) {
    return line[id].b + line[id].k * pos;
}

signed main() {
    fastin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        fastin >> s[i] >> l[i] >> r[i] >> x[i] >> y[i];
    }
    for (int i = 1; i <= m; i++) {
        fastin >> c[i];
        c[i] = -c[i];
        sum[i] = sum[i - 1] + c[i];
    }
    for (int i = 1; i <= n; i++) {
        line[i].b = sum[r[i]] - sum[l[i] - 1] + (r[i] - l[i] + 1) * s[i];
        line[i].k = (x[i] + y[i]) * (r[i] - l[i] + 1);
    }
    sort(line + 1, line + n + 1);
    cnt = unique(line + 1, line + n + 1) - line - 1;
    int st = 0;
    line[0].b = inf;
    for (int i = 1; i <= cnt; i++) {
        if (line[i].b < line[st].b) {
            st = i;
        }
        if (line[i].b == line[st].b && line[i].k < line[st].k) {
            st = i;
        }
    }
    pos[1] = 0;
    pid[1] = st;
    int top = 1;
    for (int i = st + 1; i <= cnt; i++) {
        while (cross_point(pid[top], i) <= pos[top]) {
            top--;
        }
        pos[top + 1] = cross_point(pid[top], i);
        pid[top + 1] = i;
        top++;
    }
    for (int i = 1, t; i <= q; i++) {
        fastin >> t;
        int p = upper_bound(pos + 1, pos + top + 1, t) - pos - 1;
        printf("%lld\n", value(pid[p], t));
    }
    return 0;
}

overwatch

给一颗 $n$ 个点的树，点有权值 $a_i$ ，定义一条链的值为链上所有点权值和。

$q$ 个询问，每个询问两个数 $w,k$ 。改变一个点的权值为 $w$ ，求每次改变后的树中长度为 $k$ (点的个数为 $k$ ) 的链的最大值。

$n,q\le10^5$ ， $k\le5$

$k$ 的大小不超过 $5$ ，这是一个很好的入手条件。

发现对于点 $x$ 的每个儿子,里面可能有很多长度为 $k$ 的小路径可以接上点 $x$ 变成一条长度为 $k + 1$ 的小路径,但是我们只需要那条权值最大的就行了。所以对于每个点,我们开 $k$ 个 set (每个长度开一个),每个 set 的大小为这个点的孩子个数,把每个儿子当前长度权值最大的那条小路径塞进去,然后计算答案的话拼一拼就好了 (还是要特判来自同一子树)。
对于一次修改 $(x, w)$ , 只会影响到点 $x$ 以及 Ta 的 $1\ldots(k − 1)$ 级祖先,我们先把原来最长的小路径删去,然后再把现在新的最长的小路径加上就好了,对于每个被修改的点,以 Ta 为 lca 的大路径的答案可能发生变化,所以我们可以在外层写一个可删堆,里面塞上以每个点为 lca 的大路径的答案。那么现在对于每个被修改的点,只要把原先在外层可删堆里的答案删掉,再重新拼一拼计算出新的答案,塞回外层可删堆里就好了。

还没有调完，代码就先不放了

jypb

还不会。

HNOI2021-Index