思路一：树上倍增
//我们讲一讲这个是怎么逼近
//可以证明f[u][0]一定是f[father[u]][i]购买路径上的节点
//把一个查询作为一个节点。那么最后就是看从查询的u节点开始能最多跳多少次，并且不超过v节点。
//往上倍增寻找第一个比a[u]大的节点下面那个节点(他的父亲就是第一个比a[u]大的节点);
int x=fa;
for(int i=20; i>=0; i--){
//找到<=a[u]的第一个节点。那么这个节点肯定处于f[x][i]~f[x][i-1]
//从f[x][i-1]开始区间长度为i-1。继续逼近
if(f[x][i]&&a[u]>=a[f[x][i]]){
x=f[x][i];
}
}
f[u][0]=f[x][0];//f[x][0]就是第一个比a[u]大的节点思路二：dfs+线段树
思路三：dfs+单调栈
//思路一：
#include <bits/stdc++.h>
using namespace std;
int a[200005], R[200005];
vector<vector<int> > v(200005);
int f[200005][25], deep[200005];
void dfs(int u, int fa){
deep[u]=deep[fa]+1;
if(a[u]<a[fa]){//若父节点p的val比u的val大，fa[u][0] = p
f[u][0]=fa;
}
else{
int x=fa;
for(int i=20; i>=0; i--){//x逼近第一个比a[u]大的结点下方的结点
if(f[x][i]&&a[u]>=a[f[x][i]]){
x=f[x][i];
}
}
f[u][0]=f[x][0];
}
for(int i=1; i<=20; i++){//更新倍增数组;
f[u][i]=f[f[u][i-1]][i-1];
}
for(auto x: v[u]){
if(x!=fa){
dfs(x, u);
}
}
}
int main(){
int n, q, x, y, z; scanf("%d%d", &n, &q);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
}
for(int i=1; i<n; i++){
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1; i<=q; i++){
scanf("%d%d%d", &x, &y, &z);
v[n+i].push_back(x);//每个询问新加一个结点连在u下面
v[x].push_back(n+i);
a[n+i]=z, R[i]=y;//这个查询时的u节点对应的v节点;
}
dfs(1, 0);
for(int i=1; i<=q; i++){
int x=i+n, ans=0;//这次查询时x节点在图中代表的节点;
for(int k=20; k>=0; k--){
if(deep[f[x][k]]>=deep[R[i]]){//从u往上倍增找,位置不能超过v的位置;
x=f[x][k]; ans+=(1<<k);//往上走了几步,即宝石更新了几次;
}
}
printf("%d\n", ans);
}
return 0;
}
思路二：
#include<bits/stdc++.h>
#define LL long long
#define mid (l+r)/2
using namespace std;
struct Node{
LL l, r;
LL mx, pos;
}node[1000005];
void BT(LL i, LL l, LL r){
node[i].l=l; node[i].r=r;
if(l==r){
node[i].mx=node[i].pos=0; return ;
}
BT(i<<1, l, mid); BT((i<<1)+1, mid+1, r);
}
void GX(LL i, LL x, LL y){
if(node[i].l==node[i].r){
node[i].pos=x;node[i].mx=y; return ;
}
if(x<=(node[i].l+node[i].r)/2) GX(i<<1, x, y);
else GX((i<<1)+1, x, y);
if(node[i<<1].mx>node[(i<<1)+1].mx){
node[i].mx=node[i<<1].mx; node[i].pos=node[i<<1].pos;
}
else{
node[i].mx=node[(i<<1)+1].mx; node[i].pos=node[(i<<1)+1].pos;
}
}
int CXid(LL i, LL k){
if(node[i].l==node[i].r) return node[i].l;
if(node[(i<<1)+1].mx>k) return CXid((i<<1)+1, k);
else if(node[i<<1].mx>k) return CXid(i<<1, k);
return 0;
}
LL mx=0, pos=0;
void CXmax(LL i, int l, int r){
if(node[i].l==l&&node[i].r==r){
if(node[i].mx>mx){
mx=node[i].mx; pos=node[i].pos;
}
return ;
}
if(r<=(node[i].l+node[i].r)/2){
CXmax(i<<1, l, r); return ;
}
if(l>(node[i].l+node[i].r)/2){
CXmax((i<<1)+1, l, r); return;
}
CXmax(i<<1, l, (node[i].l+node[i].r)/2);
CXmax((i<<1)+1, (node[i].l+node[i].r)/2+1, r);
}
/*************************************************/
int a[200005], ans[200005], f[200005], b[200005], tot=0;
vector<vector<int> > v(200005);
vector<pair<int, int> > q[200005];
void DFS(int u, int fa){
b[u]=++tot;
int id=CXid(1, a[u]);//查询链上距离u最进并且a[id]>a[u]的节点
f[b[u]]=f[id]+1;
GX(1, b[u], a[u]);//把u的影响加入线段树
for(auto x: q[u]){//处理查询
mx=0, pos=0;
CXmax(1, b[x.first], b[u]);
ans[x.second]=f[b[u]]-f[pos];
}
for(int x: v[u]){
if(x!=fa){
DFS(x, u);
}
}
GX(1, b[u], 0);//删除u的影响
--tot;
}
int main(){
int n, Q, x, y, c; scanf("%d%d", &n, &Q);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
}
for(int i=1; i<n; i++){
scanf("%d%d", &x, &y);
v[x].push_back(y); v[y].push_back(x);
}
BT(1, 1, n);
for(int i=1; i<=Q; i++){
scanf("%d%d%d", &x, &y, &c);
a[n+i]=c;
v[n+i].push_back(x); v[x].push_back(n+i);
q[n+i].push_back({y, i});
}
DFS(1, 0);
for(int i=1; i<=Q; i++){
printf("%d\n", ans[i]);
}
return 0;
}
//思路三
#include <bits/stdc++.h>
using namespace std;
#define LL long long
int a[200005];
struct node{
int v, id;
}st[200005];
vector<vector<int> > v(200005);
vector<vector<node> > q(200005);//查询
int deep[200005], ans[200005], tot=0;
struct bc{
int tot, x;//tot:栈的元素个数 改变的下标：x
node t;//栈里的内容
}b[200005];
int ER(int u, int v){
int l=1, r=tot, pos1=1, pos2=0;
while(l<=r){//最大第一个deep>=v的节点
int mid=(l+r)/2;
if(st[mid].id>=deep[v]){
pos1=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
l=1; r=tot;
while(l<=r){//最后一个a[pos2]>a[u]的节点
int mid=(l+r)/2;
if(st[mid].v>a[u]){
pos2=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
return max(0, pos2-pos1+1);
}
void DFS(int u, int fa, int d){
b[u].tot=tot;
deep[u]=++d;//保存深度
while(tot&&st[tot].v<=a[u]){//把节点u加入单调栈
tot--;
}
b[u].x=++tot, b[u].t=st[tot];//保存单调栈的变化
st[tot]=node{a[u], deep[u]};
// printf("%d: ", u);
// for(int i=1; i<=tot; i++){
// printf("%d ", st[i].v);
// }
// printf("\n");
for(auto x: q[u]){//处理查询
ans[x.id]=ER(u, x.v);
}
for(auto x: v[u]){
if(x==fa) continue;
DFS(x, u, d);
}
tot=b[u].tot;//恢复单调栈的变化
st[b[u].x]=b[u].t;
}
int main(){
int n, Q, x, y, c; scanf("%d%d", &n, &Q);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
}
for(int i=1; i<n; i++){
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1; i<=Q; i++){//把查询变成节点
scanf("%d%d%d", &x, &y, &c);
a[n+i]=c;
v[n+i].push_back(x);
v[x].push_back(n+i);
q[n+i].push_back(node{y, i});
}
DFS(1, 0, 0);
for(int i=1; i<=Q; i++){
printf("%d\n", ans[i]);
}
return 0;
}
京公网安备 11010502036488号