ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#460 | #94. 「NOIP2021」报数 | Pigsyy | 0 | 0ms | 0kb | C++23 | 4.4kb | 2025-04-24 14:04:36 | 2025-04-24 14:04:36 |
answer
#include <bits/stdc++.h>
#define F(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define G(i,l,r) for(int i=(l),i##end=(r);i>=i##end;--i)
#define pii pair<int,int>
#define x first
#define y second
#define mp(x,y) make_pair(x,y)
#define ep emplace_back
using namespace std;
typedef long long ll;
constexpr int N = 5e5;
struct Edge {
int nxt;
int to;
} ed[2 * N];
int head[N + 9];
int pp;
void adde(int x, int y) {
++pp;
ed[pp].nxt = head[x];
ed[pp].to = y;
head[x] = pp;
}
struct question {
int id, l, r, k;
} q[N + 9];
struct node {
int l, r, x;
} sk[N + 9];
int dep[N + 9];
int st[20][N + 9];
int dfn[N + 9];
int a[N + 9];
int n, dfntot;
void dfs(int x, int fa) {
dep[x] = dep[fa] + 1;
st[0][dfn[x] = ++dfntot] = dep[fa];
for (int i = head[x], u = ed[i].to; i; u = ed[i = ed[i].nxt].to)
if (u != fa)
dfs(u, x);
}
int ask(int x) {
int u = dfn[x], v = dfn[x + 1];
if (u > v)
swap(u, v);
int l = __lg(v - u++);
return min(st[l][u], st[l][v - (1 << l) + 1]);
}
void init() {
F(i, 1, __lg(n))F(j, 1, n - (1 << i) + 1) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
F(i, 1, n - 1) sk[i].x = a[i] = ask(i);
int stk[N + 9], top = 0;
stk[0] = 0;
F(i, 1, n - 1) {
while (top && a[stk[top]] >= a[i])
sk[stk[top--]].r = i - 1;
sk[i].l = stk[top] + 1;
stk[++top] = i;
}
F(i, 1, top) sk[stk[i]].r = n - 1;
}
void chkmin(int &x, int y) {
if (y < x)
x = y;
}
void chkmax(int &x, int y) {
if (y > x)
x = y;
}
namespace zkw {
int tr[1 << 21], n;
void init(int n_) {
n = 1;
while (n <= n_)
n <<= 1;
memset(tr, 0, sizeof(int) * (2 * n + 1));
}
void modify(int x, int y) {
if (tr[x += n] < y)
tr[x] = y;
else
return ;
for (; x >>= 1;)
tr[x] = max(tr[x << 1], tr[x << 1 | 1]);
}
int ask(int l, int r) {
int ans = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1)
ans = max(ans, tr[l++]);
if (r & 1)
ans = max(ans, tr[--r]);
}
return ans;
}
}
int out[N + 9];
int m;
namespace solve {
int st[20][N + 9];
void main() {
F(i, 1, n) st[0][i] = dep[i];
F(i, 1, __lg(n))F(j, 1, n - (1 << i) + 1)st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
F(i, 1, m)if (q[i].k == 0) {
q[i].r++;
int l = __lg(q[i].r - q[i].l + 1);
out[i] = max(st[l][q[i].l], st[l][q[i].r - (1 << l) + 1]);
}
}
}
void read(int &x) {
x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
}
char hi[10];
int hii;
void write(int x) {
hii = 0;
while (x)
hi[++hii] = x % 10, x /= 10;
G(i, hii, 1)putchar(hi[i] + '0');
}
int main() {
freopen("query.in", "r", stdin);
freopen("query.out", "w", stdout);
read(n);
F(i, 1, n - 1) {
int u, v;
read(u);
read(v);
adde(u, v);
adde(v, u);
}
dfs(1, 0);
read(m);
F(i, 1, m)q[i].id = i, read(q[i].l), read(q[i].r), read(q[i].k), q[i].k--, q[i].r--;
solve::main();
init();
sort(q + 1, q + m + 1, [](const question & a, const question & b) {
return a.k > b.k;
});
sort(sk + 1, sk + n, [](const node & a, const node & b) {
return a.r - a.l > b.r - b.l;
});
zkw::init(n);
int tot = 0;
F(i, 1, m) {
if (!q[i].k)
break;
while (tot < n && sk[tot + 1].r - sk[tot + 1].l + 1 >= q[i].k) {
++tot;
zkw::modify(sk[tot].l, sk[tot].x);
}
chkmax(out[q[i].id], zkw::ask(q[i].l, q[i].r - q[i].k + 1));
}
sort(q + 1, q + m + 1, [](const question & a, const question & b) {
return a.l < b.l;
});
sort(sk + 1, sk + n, [](const node & a, const node & b) {
return a.l < b.l;
});
zkw::init(n);
tot = 0;
F(i, 1, m) {
if (!q[i].k)
continue;
while (tot < n && sk[tot + 1].l <= q[i].l) {
++tot;
zkw::modify(sk[tot].r, sk[tot].x);
}
chkmax(out[q[i].id], zkw::ask(q[i].l + q[i].k - 1, n));
}
F(i, 1, m)write(out[i]), putchar('\n');
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 0
Dangerous Syscalls
input:
498 89 22 22 63 22 67 67 149 89 74 89 80 63 54 54 205 63 177 205 20 149 66 80 96 96 194 194 170 96 1...
output:
result:
Test #2:
score: 0
Dangerous Syscalls
input:
496 376 35 35 334 35 49 376 328 35 184 334 9 184 216 35 50 49 108 9 79 79 274 9 325 274 416 416 272 ...
output:
result:
Test #3:
score: 0
Dangerous Syscalls
input:
4996 58 212 212 251 251 501 251 358 58 483 501 200 212 173 501 21 501 34 34 506 483 266 173 144 266 ...
output:
result:
Test #4:
score: 0
Dangerous Syscalls
input:
4997 599 56 599 83 56 283 56 292 283 764 283 148 56 770 83 251 83 362 362 199 770 871 362 448 871 48...
output:
result:
Test #5:
score: 0
Dangerous Syscalls
input:
5000 130 241 241 561 561 17 130 208 130 444 208 437 208 362 437 325 325 419 325 47 325 629 362 487 6...
output:
result:
Test #6:
score: 0
Dangerous Syscalls
input:
100000 1 89135 89135 42606 42606 51140 51140 88708 88708 24332 24332 42871 42871 42697 42697 49402 4...
output:
result:
Test #7:
score: 0
Dangerous Syscalls
input:
100000 1 9530 9530 22076 22076 39846 39846 47126 47126 11168 11168 31227 31227 92667 92667 73020 730...
output:
result:
Test #8:
score: 0
Dangerous Syscalls
input:
100000 1 56545 56545 4442 4442 30021 30021 12958 12958 3882 3882 81161 81161 17303 17303 59356 59356...
output:
result:
Test #9:
score: 0
Dangerous Syscalls
input:
100000 1 28773 28773 60979 60979 62259 62259 23921 23921 94894 94894 14535 14535 25483 25483 15766 1...
output:
result:
Test #10:
score: 0
Dangerous Syscalls
input:
500000 1 266014 266014 196927 196927 19617 19617 450868 450868 244252 244252 69345 69345 240592 2405...
output:
result:
Test #11:
score: 0
Dangerous Syscalls
input:
500000 1 278484 278484 369808 369808 117284 117284 296213 296213 395873 395873 259275 259275 43124 4...
output:
result:
Test #12:
score: 0
Dangerous Syscalls
input:
500000 1 402048 402048 181762 181762 153002 153002 57994 57994 330080 330080 309815 309815 101203 10...
output:
result:
Test #13:
score: 0
Dangerous Syscalls
input:
500000 1 404040 404040 422879 422879 251314 251314 437072 437072 166277 166277 496632 496632 137251 ...
output:
result:
Test #14:
score: 0
Dangerous Syscalls
input:
500000 945 968 968 931 968 52 931 923 945 696 696 900 696 180 696 8 52 581 900 867 900 629 581 453 4...
output:
result:
Test #15:
score: 0
Dangerous Syscalls
input:
500000 668 773 668 181 181 92 773 267 181 471 92 260 92 455 455 574 267 298 455 81 574 838 838 434 8...
output:
result:
Test #16:
score: 0
Dangerous Syscalls
input:
500000 146 93 146 98 146 171 93 12 146 52 52 237 12 279 279 36 171 189 52 243 237 122 122 25 122 212...
output:
result:
Test #17:
score: 0
Dangerous Syscalls
input:
100000 9 271 9 115 115 270 271 234 9 136 136 22 9 134 115 196 22 195 196 52 22 151 22 268 134 11 268...
output:
result:
Test #18:
score: 0
Dangerous Syscalls
input:
100000 38 135 38 114 38 155 135 645 38 52 135 593 155 491 645 251 593 245 491 40 52 269 245 622 40 3...
output:
result:
Test #19:
score: 0
Dangerous Syscalls
input:
100000 255 350 255 14 14 222 14 415 222 40 415 232 14 65 40 174 222 438 65 29 232 152 232 261 261 20...
output:
result:
Test #20:
score: 0
Dangerous Syscalls
input:
100000 880 278 278 659 278 211 659 509 659 270 659 634 659 819 819 501 659 474 474 11 474 221 270 69...
output:
result:
Test #21:
score: 0
Dangerous Syscalls
input:
500000 9 278 278 66 9 410 278 580 580 5 5 609 410 610 410 44 609 632 44 304 5 210 632 692 610 529 63...
output:
result:
Test #22:
score: 0
Dangerous Syscalls
input:
500000 471 528 471 418 471 256 418 18 18 64 18 461 256 577 577 167 64 537 461 273 64 154 64 354 354 ...
output:
result:
Test #23:
score: 0
Dangerous Syscalls
input:
500000 261 10 261 301 261 180 10 241 241 498 498 265 261 388 388 561 241 25 265 331 265 63 561 156 2...
output:
result:
Test #24:
score: 0
Dangerous Syscalls
input:
500000 12 21 12 30 21 53 21 58 12 75 53 14 30 40 14 72 53 26 58 67 75 42 14 66 14 29 72 71 42 49 71 ...
output:
result:
Test #25:
score: 0
Dangerous Syscalls
input:
500000 43 28 28 2 2 49 28 12 43 18 49 45 2 34 28 41 18 3 12 5 34 24 5 44 41 16 24 47 5 36 24 7 44 48...