9.27模拟赛题解
Actinoi
9月 28, 2020
9.27模拟赛题解
相遇
树上路径求交模版题。
、
由于一共有 个点与 条边，所以便隐晦地告诉我们这张图没有环。
要看 是否有公共路径，我们可以分别求出 以及 ，如果 的话，那么两个路径都经过一个相同的点，直接输出 YES 就可以了。
那么，就像上面这张图，当 的话，虽然有相同的路径，但是 ， ，这应该怎么办呢？我们就可以判断 或 的值是否等于 。反之当 在 上方时同理求出。
#include <queue>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxx 1000001
int n, m, s;
int cnt, head[maxx];
struct node{
int to, next;
} e[maxx];
void add_edge(int x, int y) {
cnt++;
e[cnt].to = y;
e[cnt].next = head[x];
head[x] = cnt;
}
int deep[maxx], father[maxx][21], log[maxx];
void DFS(int now, int fa) {
father[now][0] = fa;
deep[now] = deep[fa] + 1;
for (int i = 1; i <= log[deep[now]]; i++) {
father[now][i] = father[father[now][i - 1]][i - 1];
}
for (int i = head[now]; i; i = e[i].next) {
if (e[i].to != fa)
DFS(e[i].to, now);
}
}
int LCA(int x, int y) {
if (deep[x] < deep[y]) std::swap(x, y); //使 x 一直处于下面， y 一直处于上面
for (int i = 20; i >= 0; i--) {
if (deep[father[x][i]] >= deep[y])
x = father[x][i];
if (x == y) return x;
}
for (int i = 20; i >= 0; i--) {
if (father[x][i] != father[y][i]) {
x = father[x][i];
y = father[y][i];
}
}
return father[x][0];
}
int main() {
//freopen("railway.in", "r", stdin);
//freopen("railway.out", "w", stdout);
int T;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n - 1; i++) {
int x, y;
scanf("%d %d", &x, &y);
add_edge(x, y);
add_edge(y, x);
}
for (int i = 1; i <= n; i++) {
log[i] = log[i - 1] + (1 << log[i - 1] == i);
}
s = 1;
DFS(s, 0);
for (int i = 1; i <= m; i++) {
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
int p = LCA(x1, y1), q = LCA(x2, y2);
if (p == q) {
printf("YES\n");
continue;
} else if (deep[p] > deep[q]) {
if (LCA(p, x2) == p || LCA(p, y2) == p) printf("YES\n");
else printf("NO\n");
} else {
if (LCA(q, x1) == q || LCA(q, y1) == q) printf("YES\n");
else printf("NO\n");
}
}
cnt = 0;
memset(head, 0, sizeof(head));
memset(deep, 0, sizeof(deep));
memset(father, 0, sizeof(father));
memset(log, 0, sizeof(log));
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
计数
求 可以转化为求 。
对于序列中第 个数字 ，可以求出它在哪一段区间内的是最大值，在哪一段区间内是最小值。
设第 个数字左边第一个比它大的数字的下标为 ，右边第一个比它大的数字的下标为 ，因此就可以得出数字 有贡献的区间的个数为 ，这些区间的贡献值加起来就是 。同理，可以求出每个数字在哪一段区间内是最小值，用 就求出了最后的答案。
#include <cstdio>
#define MAXN 100001
long long n;
long long stack[MAXN], top = 0; //stack 为单调递减的栈，top 为指针下标
struct node{
long long pos, dis;
} a[MAXN];
long long L_max[MAXN], R_max[MAXN]; //存储 x 左边第一个比 x 大的以及 x 右边第一个比 x 大的
long long L_min[MAXN], R_min[MAXN];
void find_max() {
a[0].pos = 0, a[0].dis = 2147483647;
for (long long i = 1; i <= n; i++) { //维护一个单调递减的栈
if (a[i].dis <= a[stack[top]].dis) { //能够添加元素
top++;
stack[top] = i;
L_max[i] = a[stack[top - 1]].pos;
} else { //为维护队列单调性，删除元素
while (a[i].dis > a[stack[top]].dis) {
R_max[a[stack[top]].pos] = i; //记录当前被弹出元素
top--;
}
top++;
stack[top] = i;
L_max[i] = a[stack[top - 1]].pos;
}
}
while (top >= 1) { //把栈最后几个元素赋值右边最大值
R_max[a[stack[top]].pos] = n + 1;
top--;
}
}
void find_min() {
a[0].pos = 0, a[0].dis = 0;
for (long long i = 1; i <= n; i++) { //维护一个单调递增的栈
if (a[i].dis >= a[stack[top]].dis) { //能够添加元素
top++;
stack[top] = i;
L_min[i] = a[stack[top - 1]].pos;
} else { //为维护队列单调性，删除元素
while (a[i].dis < a[stack[top]].dis) {
R_min[a[stack[top]].pos] = i; //记录当前被弹出元素
top--;
}
top++;
stack[top] = i;
L_min[i] = a[stack[top - 1]].pos;
}
}
while (top >= 1) { //把栈最后几个元素赋值右边最大值
R_min[a[stack[top]].pos] = n + 1;
top--;
}
}
int main() {
//freopen("count.in", "r", stdin);
//freopen("count.out", "w", stdout);
long long T;
scanf("%lld", &T);
while (T--) {
scanf("%lld", &n);
for (long long i = 1; i <= n; i++) {
scanf("%lld", &a[i].dis);
a[i].pos = i;
}
find_max(); //找到最大值贡献
find_min();
long long ans = 0;
for (long long i = 1; i <= n; i++)
ans += a[i].dis * (R_max[i] - i) * (i - L_max[i]) - a[i].dis * (R_min[i] - i) * (i - L_min[i]);
printf("%lld\n", ans);
top = 0;
}
//fclose(stdin);
//fclose(stdout);
return 0;
}