Cauphenuny's blog

20210217 模拟赛总结

发表于 更新于 分类于 ，

Index

Review

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

Solution

T1 god

在平面直角坐标系中，在 x 负半轴有一些位置，编号 11 ~ nn ，正半轴有 mm 个点 (si,0)(s_i,0) 。每个点有一个移动向量 (xi,yi)(x_i,y_i) 每一秒按此向量移动 (0≤xi,yi≤1050\le x_i,y_i\le 10^5) ，每个点的价值为它到编号为 [li,ri][l_i,r_i] 区间内位置的曼哈顿距离和，qq 个询问，每个询问给定 tt ，求 yy 时刻每个点价值的最小值。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//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

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

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

n,q≤105n,q\le10^5，k≤5k\le5

kk 的大小不超过 55 ，这是一个很好的入手条件。

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

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

jypb

还不会。

HNOI2021-Index