国外网站服务器地址,skycc营销软件,惠州有做网站的吗,网站开发人员调试A - ST 表 RMQ 问题 题目思路:st表的板子题用于静态区间求最值,通过倍增的思想,先通过预处理将各个区间的最大值通过转移式求出f[i][j] max(f[i][j - 1], f[i (1 (j - 1))][j - 1]);然后再进行重叠查询查询,k log2(r - l 1);,max(f[l][k], f[r - (1 RMQ 问题 题目思路:st表的板子题用于静态区间求最值,通过倍增的思想,先通过预处理将各个区间的最大值通过转移式求出f[i][j] max(f[i][j - 1], f[i (1 (j - 1))][j - 1]);然后再进行重叠查询查询,k log2(r - l 1);,max(f[l][k], f[r - (1 k) 1][k]).
实现代码:
#includebits/stdc.h
using namespace std;
#define N 2000005
typedef long long ll;
ll n, m, t, a, b, c, k, d, r, l;
ll f[N][32], dp[N];
ll ans, maxx, minn 1e9;
inline int read()
{int x 0, f 1; char ch getchar();while (ch 0 || ch9) { if (ch -) f -1; ch getchar(); }while (ch 0 ch 9) { x x * 10 ch - 48; ch getchar(); }return x * f;
}
int main()
{cin n m;for (int i 1; i n; i) f[i][0] read();for (int j 1; j 20; j) {for (int i 1; i (l j) - 1 n; i) {f[i][j] max(f[i][j - 1], f[i (1 (j - 1))][j - 1]);}}for (int i 1; i m; i) {l read(), r read();k log2(r - l 1);cout max(f[l][k], f[r - (1 k) 1][k]) \n;}return 0;
} P3379 【模板】最近公共祖先LCA 题目思路:dep[u]存u点的深度,f[u][i]存从u点向上提哦啊2^i层的祖先节点,首先通过dfs进行倍增递推打表,从小到大枚举,然后跑一边lca进行二进制拆分,从大到小枚举.用快读读取,卡时间
代码实现:
#includebits/stdc.h
using namespace std;
#define N 2000005
typedef long long ll;
ll n, m, t, a, b, c, k, d, r, l;
ll f[N][30], dep[N];
ll ans, maxx, minn 1e9;
vectorllv[N];
inline int read()
{int x 0, f 1; char ch getchar();while (ch 0 || ch9) { if (ch -) f -1; ch getchar(); }while (ch 0 ch 9) { x x * 10 ch - 48; ch getchar(); }return x * f;
}
void dfs(ll u, ll father) {dep[u] dep[father] 1;f[u][0] father;for (int i 1; i 20; i) {f[u][i] f[f[u][i - 1]][i - 1];}for (ll v : v[u]) {if (v ! father)dfs(v, u);}
}ll lca(ll u, ll v) {if (dep[u] dep[v]) swap(u, v);for (int i 20; i 0; i--)if (dep[f[u][i]] dep[v])u f[u][i];if (u v) return v;for (int i 20; i 0; i--) {if (f[u][i] ! f[v][i])u f[u][i], v f[v][i];}return f[u][0];
}
int main()
{cin n m t;for (int i 1; i n-1; i) {a read(), b read();v[a].push_back(b), v[b].push_back(a);}dfs(t, 0);for (int i 1; i m; i) {a read(), b read();cout lca(a,b) \n;}return 0;
}
