求最长的任意两元素差不超过M的子段——双指针+单调队列hdu4123

换根dp的部分比较容易,难点在于求求最长的任意两元素差不超过M的子段

首先会想到双指针维护(尺取法),如果p1,p2间的max-min>M,那么p1向右移动,直到p1,p2间的max-min>M

这个过程可以用线段树(ST)来询问max,min

另外有一种更强大的方案,因为只要max,min,所以只要维护两个单调队列来解决即可,当max-min>M时取队首元素最远的出队即可

/*
第一部分:求出数组a[]
第二部分:每次询问给出一个Q,求出最长的一段[L,R]使段中任意两个数据的差不超过Q
用双指针进行维护,用两个单调队列维护这指针间的最大最小值,然后O(n)求每个询问 */
#include<bits/stdc++.h>
#include<queue>
using namespace std;
#define N 50006
struct Edge{int to,nxt,w;}e[N<<];
int head[N],tot,n,m;
void init(){memset(head,-,sizeof head);tot=;}
void add(int u,int v,int w){
e[tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot++;
}
int d[N],a[N];
void dfs1(int u,int pre){
d[u]=;
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(v==pre)continue;
dfs1(v,u);
d[u]=max(d[u],d[v]+e[i].w);
}
}
void dfs2(int u,int pre,int up){
int mx1=,mx2=,id1=,id2=;
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(v==pre)continue;
if(d[v]+e[i].w>=mx1){
mx2=mx1,id2=id1;
mx1=d[v]+e[i].w,id1=v;
}
else if(d[v]+e[i].w>=mx2)
mx2=d[v]+e[i].w,id2=v;
}
if(up>=mx1){
mx2=mx1,id2=id1;
mx1=up,id1=;
}
else if(up>=mx2)
mx2=up,id2=;
a[u]=mx1; for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(v==pre)continue;
if(v==id1)
dfs2(v,u,mx2+e[i].w);
else dfs2(v,u,mx1+e[i].w);
}
} //双指针p,i,两个单调队列维护区间最大值,最小值
void solve(int Q){
deque<int>q1,q2;
int res=,p=;
for(int i=;i<=n;i++){
while(q1.size() && a[q1.back()]>=a[i])q1.pop_back();
q1.push_back(i);
while(q2.size() && a[q2.back()]<=a[i])q2.pop_back();
q2.push_back(i); while(a[q2.front()]-a[q1.front()]>Q){
p=min(q1.front(),q2.front())+;
while(q1.front()<p)q1.pop_front();
while(q2.front()<p)q2.pop_front();
}
res=max(res,i-p+);
}
cout<<res<<endl;
} int main(){
while(cin>>n>>m && n){
init();
for(int i=;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
dfs1(,);
dfs2(,,);
while(m--){
int q;scanf("%d",&q);
solve(q);
}
}
}
上一篇:servlet injection analysis


下一篇:BIA B452F Assignment