poj 3162 线段树 hdu 4123 bfs + RMQ预处理

题意：给你一棵树，然后标号为1~n，每条边都有一定的边权，那么从每个点出发都有一个最远距离num[i];
先求出num【】数组，然后再有500个询问，每个询问输入一个整数m，求num数组中最大值与最小值绝对值之差不超过m的最长的连续区间是多少。

这是2011福州区域赛的题目，咋一看蛮难的，其实是个大水题，poj也有类似的题目，应该说是改编过来的吧。
好了，讲讲我是怎么做的吧
1：利用树的最长路的结论我们首先预处理出num数组
2：由于后面需要查询区间最值，所以先用RMQ预处理num【】，后面查询的时候就可以做到O(1)查询，如果用线段树的话复杂度会太大
3：对于每个询问，可以做到O(n)回答，维护两个指针l,r 如果当前区间满足条件r++,否则l++，每个点都被插入删除一次，区间最值的查询是O(1）的，所以询问的复杂度是
q*n即500*50000.
总复杂度是nlog(n)+q*n
所以就是q*n的复杂度，即500*50000，时限两秒，小轻松啊~

[cpp] 
#include<cstdio> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
const int inf = ~0u>>2; 
const int maxn = 50010; 
int n,m; 
struct Edge{ 
    int v,w,next; 
}edge[2*maxn]; 
int head[maxn],E,num[maxn]; 
void add_edge(int a,int b,int w) 
{ 
    edge[E].v=b; 
    edge[E].w=w; 
    edge[E].next=head[a]; 
    head[a]=E++; 
} 
int dis1[maxn],dis2[maxn]; 
bool vis[maxn]; 
int q[maxn]; 
void bfs(int s,int &ss,int dist[])   { 
    fill(dist,dist+n+1,inf); 
    fill(vis,vis+n+1,false); 
    vis[s]=true; 
    dist[s]=0; 
    int front(0),tail(0),u,v,w; 
    q[0]=s;int Max=0; 
    while(front<=tail)    { 
        u=q[front++]; 
        for(int i=head[u];i!=-1;i=edge[i].next)    { 
            v=edge[i].v,w=edge[i].w; 
            if(vis[v]) continue; 
            vis[v]=true; 
            dist[v]=dist[u]+w; 
            if(dist[v]>Max)      { 
                Max=dist[v]; 
                ss=v; 
            } 
            q[++tail]=v; 
        } 
    } 
} 
int LOG[2*maxn]; 
int dp1[20][2*maxn]; 
int dp2[20][2*maxn]; 
inline int min(int a,int b){ 
    return a<b?a:b; 
} 
inline int max(int a,int b){ 
    return a>b?a:b; 
} 
void rmq_init(int n) 
{ 
    int i,j; 
    for(j=1;j<=n;j++)   { 
        dp1[0][j]=num[j]; 
        dp2[0][j]=num[j]; 
    } 
    for(j=1;j<=LOG[n];j++)   { 
        int limit=n+1-(1<<j); 
        for(i=1;i<=limit;i++)    { 
            int x=i+(1<<j>>1); 
            dp1[j][i]=min(dp1[j-1][x],dp1[j-1][i]); 
            dp2[j][i]=max(dp2[j-1][x],dp2[j-1][i]); 
        } 
    } 
} 
int rmq_min(int l,int r) 
{ 
    int m=LOG[r-l+1]; 
    return min(dp1[m][l],dp1[m][r-(1<<m)+1]); 
} 
int rmq_max(int l,int r) 
{ 
    int m=LOG[r-l+1]; 
    return max(dp2[m][l],dp2[m][r-(1<<m)+1]); 
} 
int main() 
{ 
    int q; 
    LOG[0]=-1; 
    for(int i=1;i<2*maxn;i++) LOG[i]=LOG[i>>1]+1; 
    while(scanf("%d%d",&n,&q),n||q) 
    { 
        E=0;fill(head,head+n+1,-1); 
        for(int i=2,a,b,w;i<=n;i++) 
        { 
            scanf("%d%d%d",&a,&b,&w); 
            add_edge(a,b,w); 
            add_edge(b,a,w); 
        } 
        int ss,tt; 
        bfs(1,ss,dis1); 
        bfs(ss,tt,dis1); 
        bfs(tt,ss,dis2); 
        for(int i=1;i<=n;i++)     num[i]=max(dis1[i],dis2[i]); 
        rmq_init(n); 
        while(q--)    { 
            scanf("%d",&m); 
            int ans=0; 
            int l=1,r=1,mx,mi; 
            while(r<=n)    { 
                mx=rmq_max(l,r); 
                mi=rmq_min(l,r); 
                if(mx-mi<=m)    { 
                    ans=max(ans,r-l+1); 
                    r++; 
                } 
                else l++; 
            } 
            printf("%d/n",ans); 
        } 
    } 
    return 0; 
} 

http://poj.org/problem?id=3162
poj 3162这题呢有100W个点啊，RMQ的话空间开不下，所以只能线段树查询区间最值了，复杂度n*log(n),discuss说还有O(n)的做法，好像是单调队列的做法，还不会，等会了再贴上来吧。
c++跑了5 S 多

[cpp] 
#include<cstdio> 
#include<set> 
#include<cstring> 
#include<algorithm> 
using namespace std; 
#define lson l,m,rt<<1 
#define rson m+1,r,rt<<1|1 
const int inf = ~0u>>2; 
const int maxn = 1000010; 
int n,m; 
struct Edge{ 
    int v,w,next; 
}edge[2*maxn]; 
int head[maxn],E,num[maxn]; 
void add_edge(int a,int b,int w) 
{ 
    edge[E].v=b; 
    edge[E].w=w; 
    edge[E].next=head[a]; 
    head[a]=E++; 
} 
int dis1[maxn],dis2[maxn]; 
bool vis[maxn]; 
int q[maxn]; 
void bfs(int s,int &ss,int dist[])   { 
    fill(dist,dist+n+1,inf); 
    fill(vis,vis+n+1,false); 
    vis[s]=true; 
    dist[s]=0; 
    int front(0),tail(0),u,v,w; 
    q[0]=s;int Max=0; 
    while(front<=tail)   { 
        u=q[front++]; 
        for(int i=head[u];i!=-1;i=edge[i].next) { 
              v=edge[i].v,w=edge[i].w; 
              if(vis[v]) continue; 
              vis[v]=true; 
              dist[v]=dist[u]+w; 
              if(dist[v]>Max)      { 
                  Max=dist[v]; 
                  ss=v; 
              } 
              q[++tail]=v; 
        } 
    } 
} 
inline int min(int a,int b){ 
    return a<b?a:b; 
} 
inline int max(int a,int b){ 
    return a>b?a:b; 
} 
int mx[maxn<<2],mi[maxn<<2]; 
void pushup(int rt){ 
    mx[rt]=max(mx[rt<<1],mx[rt<<1|1]); 
    mi[rt]=min(mi[rt<<1],mi[rt<<1|1]); 
} 
void build(int l,int r,int rt){ 
    if(l==r){ 
        mx[rt]=mi[rt]=num[l]; 
        return ; 
    } 
    int m=(l+r)>>1; 
    build(lson); 
    build(rson); 
    pushup(rt); 
} 
int find_min(int L,int R,int l,int r,int rt) 
{ 
    if(L<=l&&r<=R) 
    { 
        return mi[rt]; 
    } 
    int m=(l+r)>>1; 
    int ret=inf; 
    if(L<=m) ret=min(ret,find_min(L,R,lson)); 
    if(R>m) ret=min(ret,find_min(L,R,rson)); 
    return ret; 
} 
int find_max(int L,int R,int l,int r,int rt) 
{ 
    if(L<=l&&r<=R) 
    { 
        return mx[rt]; 
    } 
    int m=l+r>>1; 
    int ret=0; 
    if(L<=m) ret=max(ret,find_max(L,R,lson)); 
    if(R>m) ret=max(ret,find_max(L,R,rson)); 
    return ret; 
} 
int main() 
{ 
    scanf("%d%d",&n,&m); 
    E=0;fill(head,head+n+1,-1); 
    for(int i=2,fa,w;i<=n;i++) 
    { 
        scanf("%d%d",&fa,&w); 
        add_edge(i,fa,w); 
        add_edge(fa,i,w); 
    } 
    int ss,tt; 
    bfs(1,ss,dis1); 
    bfs(ss,tt,dis1); 
    bfs(tt,ss,dis2); 
    for(int i=1;i<=n;i++)  
    { 
        num[i]=max(dis1[i],dis2[i]); 
    } 
    int l=1,r=1,mx,mi; 
    int ans=0; 
    build(1,n,1); 
    while(r<=n) 
    { 
        mx=find_max(l,r,1,n,1); 
        mi=find_min(l,r,1,n,1); 
        if(mx-mi<=m) 
        { 
            ans=max(ans,r-l+1); 
            r++; 
        } 
        else { 
         
            l++; 
        } 
    } 
    printf("%d/n",ans); 
    return 0; 
}