相遇 Railway
题目描述：
已知我国有 n 座城市，这些城市通过 $n-1$ 条高铁相连。且任意两个城市联通。
小 A 想从 $x_1$ 号城市出发，到 $y_1$ 号城市，小 B 想从 $x_2$ 号城市出发，到 $y_2$ 号
城市，问他们是否可能在路途中相遇（出现在同一城市）
你需要回答 $m$ 次这样的问题。
输入:
第一行一个数 $T$，表示数据组数
对于每一组数据：
第一行两个数 $n,m$（1 ≤ $n$,$m$ ≤ $100,000$）
第 $2～n$ 行，每行两个数$ x,y $表示有一条铁路连接城市$ x$ 和 $y$
接下来 $m$ 行每行四个数，分别表示 $x_1,y_1,x_2,y_2$，表示一次询问
输出：
对于每次询问输出 YES 或 NO
直接求LCA，然后分类讨论啊！
#include <bits/stdc++.h> using namespace std; #define N 1000010 inline int read(){ int x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-')s = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + (c - '0'); c = getchar(); } return x * s; } struct node{ int v, next; } t[N << 1]; int f[N]; int bian = 0; inline void add(int u, int v){ t[++bian] = (node){v, f[u]}, f[u] = bian; t[++bian] = (node){u, f[v]}, f[v] = bian; return ; } namespace LCA{ int fa[N], son[N], siz[N], top[N], deth[N]; #define v t[i].v void dfs1(int now, int father){ siz[now] = 1; fa[now] = father; deth[now] = deth[father] + 1; for(int i = f[now]; i; i = t[i].next){ if(v != father){ dfs1(v, now); siz[now] += siz[v]; if(siz[v] > siz[son[now]]) son[now] = v; } } return ; } void dfs2(int now, int tp){ top[now] = tp; if(!son[now]) return ; dfs2(son[now], tp); for(int i = f[now]; i; i = t[i].next){ if(v != fa[now] && v != son[now]) dfs2(v, v); } return ; } #undef v int lca(int x, int y){ while(top[x] != top[y]){ if(deth[top[x]] < deth[top[y]]) swap(x ,y); x = fa[top[x]]; } return deth[x] <= deth[y] ? x : y; /*lca肯定是深度比较小（在上面的）的那个*/ } inline void clean(){ memset(fa, 0, sizeof(fa)); memset(son, 0, sizeof(son)); memset(siz, 0, sizeof(siz)); memset(top, 0, sizeof(top)); memset(deth, 0, sizeof(deth)); return ; } inline bool judge(int x1, int y1, int x2, int y2){ int lca1 = lca(x1 , y1); int lca2 = lca(x2 , y2); if(lca1 == lca2) return 1; if(deth[lca1] > deth[lca2]){ if(lca(lca1 , x2) == lca1 || lca(lca1 , y2) == lca1) return 1; else return 0; } else if(deth[lca1] < deth[lca2]){ if(lca(lca2, x1) == lca2 || lca(lca2, y1) == lca2) return 1; else return 0; } return 0; } } int n, m; inline void clean(){ LCA::clean(); for(int i = 1;i <= bian; i++){ t[i] = (node){0,0}; } memset(f, 0, sizeof(f)); bian = 0; return ; } int main(){ // freopen("railway.in", "r", stdin); // freopen("railway.out", "w", stdout); int T = read(); while(T--){ clean(); n = read(), m = read(); for(int i = 1;i < n; i++){ int x = read(), y = read(); add(x, y); } LCA::dfs1(1, 1); LCA::dfs2(1, 1); for(int i = 1;i <= m; i++){ int a = read(), b = read(), c = read(), d = read(); if(LCA::judge(a, b, c, d)) printf("YES "); else printf("NO "); } } return 0; }
计数 Count
推公式：
设$maxn_{l,r}$表示$l$ ~ $r$的最大值，$minn_{l,r}$表示$l$ ~ $r$的最小值。
那么，我们有
$ans = Σ_{l=1}^nΣ_{r=l}^n maxn_{l,r} - Σ_{l=1}^nΣ_{r=l}^n minn_{l,r} $
考虑将两部分分开来求：
对于一个数字$a_i$, 我们设$l_i$ 为左边第一个比它的数的位置，$r_i$为右边第一个比它大的位置，那么，则有：
$Σ_{l=1}^nΣ_{r=l}^n maxn_{l,r}$ $=$ $Σ_{i=1}^n (r_i - i) * (i - l_i) * a[i]$
原因：
一个数能管辖的范围，即为从$l_i$到$i$, $i$ 到$r_i$的所有区间
那么，对于最小值，也是一模一样的式子，只不过是将$l_i$, $r_i$换成最小值而已
#include <bits/stdc++.h> using namespace std; #define N 100010 #define ll long long inline ll read(){ ll x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-')s = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); } return x * s; } ll l[N], r[N]; ll a[N]; ll ans = 0; inline void clear(int n){ memset(l, 0, sizeof(l)); for(ll i = 1;i <= n; i++)r[i] = n + 1; return ; } int main(){ int T = read(); while(T--){ ans = 0; int n = read(); clear(n); for(int i = 1;i <= n; i++) a[i] = read(); for(int i = 1;i <= n; i++){ for(int j = i - 1; j > 0; j--){ if(a[j] > a[i]){ l[i] = j; break; } } for(int j = i + 1;j <= n; j++){ if(a[j] > a[i]){ r[i] = j; break; } } } for(int i = 1;i <= n; i++) ans += (r[i] - i) * (i - l[i]) * a[i]; clear(n); for(int i = 1;i <= n; i++){ for(int j = i - 1; j > 0; j--){ if(a[j] < a[i]){ l[i] = j; break; } } for(int j = i + 1;j <= n; j++){ if(a[j] < a[i]){ r[i] = j; break; } } } for(int i = 1;i <= n; i++) ans -= (r[i] - i) * (i - l[i]) * a[i]; cout << ans << endl; } return 0; }