Asusetic
0%

2021.07.08模拟赛

发表于 分类于 Valine：
本文字数： 635 阅读时长 ≈ 1 分钟

T4不知道为啥乱入

2021.07.08 模拟赛

T1 超级计算机 & T3 土地购买问题

T1原题
T3原题

都是经典老题了

T2 赛马问题

其实也是原题

但是我没做过

考虑 dpi,jdp_{i,j} 表示前 ii 个数字 jj 个 $a > b $ 的

转移的时候就是 dpi,j=dpi−1,j+dpi−1,j−1×(li−j+1)dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times(l_i-j+1)

lil_i 是 bb 中小于 aia_i 的数量

设 gi=dpn,i(n−i)!g_i=dp_{n,i}(n-i)!

即至少有 ii 个满足条件的，(n−i)!(n-i)! 即随便排

然后至少恰好反演即可

T4 时代的眼泪·SP

伟大的分块

$2\times10^5 $ 8s 和题目名都在提醒我们分块

但是区间向上跳这个操作很离谱，感觉不太好维护

主要考虑整块修改，散点暴力重构即可

考虑如果一个点要跳过去的点已经被访问过了，那访问过的点一定永远比他高，也永远比他优

那么这个点就没用了，我们需要维护所有的有用的点，一开始用的带删除队列被卡爆了

用 dfs 序来判断虽然多个 log⁡\log 但是能跑过

O(nlog⁡n)−O(1)O(n\log n)-O(1) 的长链剖分求 kk 级祖先效果不太好，直接倍增也可以

另外这题的数据巨水，基本上块越小跑的越快

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
using ll    = long long;
int n, m, rt;
int a[N];
namespace IO {
inline int read() {
    int x   = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch)) {
        x  = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
} // namespace IO
using namespace IO;
namespace Tree {
const int LOG_LIM = 18;
int lg[N], p2[55];
ll dis[N];
int fa[N][LOG_LIM + 1];
int maxdep[N], son[N], top[N];
vector<int> up[N], down[N];
int dfn[N], dfn_cnt;
int siz[N], dep[N];
struct Graph {
    struct Node {
        int v;
        ll w;
    };
    std::vector<Node> edge[N];
    void add(int u, int v, int w) {
        edge[u].emplace_back(Node{v, w});
    }
} Tr, preTr;
void init() {
    lg[1] = 0;
    for (int i = 2; i < N; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    p2[0] = 1;
    for (int i = 1; i <= 25; i++) {
        p2[i] = p2[i - 1] << 1;
    }
}
void dfs_dfn(int x, int fa) {
    dfn[x] = ++dfn_cnt;
    for (auto e : preTr.edge[x]) {
        if (e.v == fa)
            continue;
        dfs_dfn(e.v, x);
    }
}
void dfs1(int x) {
    for (int i = 1; i <= LOG_LIM; i++) {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    }
    siz[x] = 1;
    for (auto e : Tr.edge[x]) {
        auto &v = e.v;
        if (v == fa[x][0]) {
            continue;
        }
        fa[v][0] = x;
        dis[v]   = dis[x] + e.w;
        dep[v]   = dep[x] + 1;
        dfs1(v);
        siz[x] += siz[v];
        maxdep[x] = max(maxdep[x], maxdep[v] + 1);
        if (!son[x] || maxdep[v] > maxdep[son[x]]) {
            son[x] = v;
        }
    }
}
void dfs2(int x, int topf) {
    top[x] = topf;
    if (!son[x])
        return;
    dfs2(son[x], topf);
    for (auto e : Tr.edge[x]) {
        auto &v = e.v;
        if (v != son[x] && v != fa[x][0])
            dfs2(e.v, e.v);
    }
    if (top[x] == x) {
        int now = x;
        while (now) {
            down[x].push_back(now);
            now = son[now];
        }
        now = x;
        for (int i = 0; i <= maxdep[x]; i++) {
            up[x].push_back(now);
            now = fa[now][0];
        }
    }
}

int LA(int x, int k) {
    if (!k)
        return x;
    x = fa[x][lg[k]];
    if (!x)
        return rt;
    k -= p2[lg[k]];
    k -= maxdep[top[x]] - maxdep[x];
    x = top[x];
    if (k >= 0) {
        if (k < up[x].size()) {
            return up[x][k];
        }
        return rt;
    }
    return down[x][-k];
}
} // namespace Tree
namespace SqrtDS {
using namespace Tree;
const int B = 4005;
int belong[N], lb[N], rb[N];
int BLOCK_SIZE, cnt;
ll mmin[B];
ll tag[B];
int lim[N], s[N], t[N], b[N];
void build(int id) {
    for (int i = lb[id]; i <= rb[id]; i++) {
        a[i] = LA(a[i], tag[id]);
        b[i] = a[i];
    }
    mmin[id] = (1ll << 60);
    tag[id]  = 0;
    s[id]    = lb[id];
    t[id]    = rb[id];
    sort(b + s[id], b + t[id] + 1);
    int uplim = t[id];
    t[id]     = s[id];
    for (int i = s[id] + 1; i <= uplim; i++) {
        if (b[i] > lim[b[t[id]]]) {
            b[++t[id]] = b[i];
        }
    }
    for (int i = s[id]; i <= t[id]; i++) {
        mmin[id] = min(mmin[id], dis[b[i]]);
    }
}
void update(int id) {
    mmin[id] = (1ll << 60);
    for (int i = s[id]; i <= t[id]; i++)
        b[i] = fa[b[i]][0];
    sort(b + s[id], b + t[id] + 1);
    int uplim = t[id];
    t[id]     = s[id];
    for (int i = s[id] + 1; i <= uplim; i++) {
        if (b[i] > lim[b[t[id]]]) {
            b[++t[id]] = b[i];
        }
    }
    for (int i = s[id]; i <= t[id]; i++) {
        mmin[id] = min(mmin[id], dis[b[i]]);
    }
}
void init() {
    BLOCK_SIZE = 52;
    int tot    = n / BLOCK_SIZE;
    if (n % BLOCK_SIZE)
        tot++;
    for (int i = 1; i <= tot; i++)
        lb[i] = rb[i - 1] + 1, rb[i] = rb[i - 1] + BLOCK_SIZE;
    rb[tot] = n;
    for (int i = 1; i <= tot; i++)
        for (int j = lb[i]; j <= rb[i]; j++)
            belong[j] = i;
    for (int i = 1; i <= tot; i++)
        build(i);
}
ll query(int l, int r) {
    int L = belong[l], R = belong[r];
    ll res = (1ll << 60);
    if (L == R) {
        for (int i = l; i <= r; i++) {
            res = min(res, dis[LA(a[i], tag[L])]);
        }
        return res;
    }
    for (int i = l; i <= rb[L]; i++) {
        res = min(res, dis[LA(a[i], tag[L])]);
    }
    for (int i = lb[R]; i <= r; i++) {
        res = min(res, dis[LA(a[i], tag[R])]);
    }
    for (int i = L + 1; i < R; i++) {
        res = min(res, mmin[i]);
    }
    return res;
}
void modify(int l, int r) {
    int L = belong[l], R = belong[r];
    if (L == R) {
        for (int i = l; i <= r; i++) {
            a[i] = fa[a[i]][0];
        }
        build(L);
        return;
    }
    for (int i = l; i <= rb[L]; i++) {
        a[i] = fa[a[i]][0];
    }
    for (int i = lb[R]; i <= r; i++) {
        a[i] = fa[a[i]][0];
    }
    build(L);
    build(R);
    for (int i = L + 1; i < R; i++) {
        tag[i]++;
        update(i);
    }
}
} // namespace SqrtDS
using Tree::dfn;
using Tree::preTr;
using Tree::Tr;
int u[N], v[N], w[N];
int main() {
    // scanf("%d%d%d", &n, &m, &rt);
    n  = read();
    m  = read();
    rt = read();
    for (int i = 1; i < n; i++) {
        // scanf("%d%d%d", &u[i], &v[i], &w[i]);
        u[i] = read();
        v[i] = read();
        w[i] = read();
        preTr.add(u[i], v[i], w[i]);
        preTr.add(v[i], u[i], w[i]);
    }
    Tree::init();
    Tree::dfs_dfn(rt, 0);
    rt = dfn[rt];
    for (int i = 1; i < n; i++) {
        Tr.add(dfn[u[i]], dfn[v[i]], w[i]);
        Tr.add(dfn[v[i]], dfn[u[i]], w[i]);
    }
    Tree::dfs1(rt);
    Tree::dfs2(rt, rt);
    for (int i = 1; i <= n; i++) {
        // scanf("%d", &a[i]);
        a[i]           = read();
        a[i]           = dfn[a[i]];
        SqrtDS::lim[i] = i + Tree::siz[i] - 1;
    }
    SqrtDS::init();
    while (m--) {
        int opt, l, r;
        // scanf("%d%d%d", &opt, &l, &r);
        opt = read();
        l   = read();
        r   = read();
        if (opt == 1) {
            SqrtDS::modify(l, r);
        } else {
            printf("%lld\n", SqrtDS::query(l, r));
        }
    }
}