9.27模拟赛题解
Actinoi
9月 28, 2020
9.27模拟赛题解
相遇
树上路径求交模版题。
、
由于一共有 个点与 条边，所以便隐晦地告诉我们这张图没有环。
要看 是否有公共路径，我们可以分别求出 以及 ，如果 的话，那么两个路径都经过一个相同的点，直接输出 YES 就可以了。
那么，就像上面这张图，当 的话，虽然有相同的路径，但是 ， ，这应该怎么办呢？我们就可以判断 或 的值是否等于 。反之当 在 上方时同理求出。
#include <queue>#include <string>#include <cstdio>#include <cstring>#include <algorithm>#define maxx 1000001int 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 100001long 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;}