线段树

大略的的看了线段树的定义然后就开始练手, 可能很多地方可以优化, 仅供参考.

徘徊在AC的边缘, 提交代码要把cout/cin 缓存 printf/scanf 刚好能过.

 1 #include <iostream>
 2 using namespace std;
 3 
 4 #define MAXN 50010
 5 
 6 struct Node{
 7     int left,right;
 8     int max,min;
 9     Node * pleft,*pright;
10     Node():pleft(NULL),pright(NULL){}
11     Node(int l,int r):left(l),right(r),max(-1),min(0x7fffffff),pleft(NULL),pright(NULL){}
12 };
13 
14 struct Point{
15     int min;
16     int max;
17     Point(int ma,int mi):max(ma),min(mi){};
18 };
19 
20 int heights[MAXN];
21 
22 void build(Node*p){
23     if(p->left == p->right){
24         p->max = heights[p->left];
25         p->min = p->max;
26         return;
27     }
28     //calc the max and min value.
29     for (int i=p->left;i<=p->right;++i){
30         if(heights[i]>p->max)
31             p->max = heights[i];
32         if(heights[i]<p->min)
33             p->min = heights[i];
34     }
35     int mid = (p->left + p->right) >> 1;
36     p->pleft = new Node(p->left,mid);
37     build(p->pleft);
38     p->pright= new Node(mid+1,p->right);
39     build(p->pright);
40 }
41 
42 Point query(Node * p, int left,int right){
43     if(left==p->left && right == p->right)
44         return Point(p->max,p->min);
45     int mid = (p->left+p->right) >> 1;
46     if(left > mid)
47         return query(p->pright,left,right);
48     else if(right <= mid)
49         return query(p->pleft,left,right);
50     else{
51         Point pl = query(p->pleft,left,mid);
52         Point pr = query(p->pright,mid+1,right);
53         int tmin = pl.min < pr.min ? pl.min : pr.min;
54         int tmax = pl.max > pr.max ? pl.max : pr.max;
55         return Point(tmax,tmin);
56     }
57 }
58 
59 
60 // for debug.
61 void dfs(Node * p){
62     if(p == NULL)
63         return;
64     cout<<"DFS TO: ["<<p->left<<", "<<p->right<<"] , ("<<p->max<<", "<<p->min<<")"<<endl;
65     dfs(p->pleft);
66     dfs(p->pright);
67 }
68 int main(){
69     int N,Q;
70     cin>>N>>Q;
71     for(int i=0;i<N;++i){
72         cin>>heights[i];
73     }
74     Node * head = new Node(0,N-1);
75     build(head);
76     // dfs(head);
77     
78     int l,r;
79     for(int i=0;i<Q;++i){
80         cin>>l>>r;
81         Point point = query(head,l-1,r-1);
82         cout<<point.max - point.min<<endl;
83     }
84     return 0;  
85 }

AC代码:

#include <stdio.h>

#define MAXN 50010

struct Node{
    int left,right;
    int max,min;
    Node * pleft,*pright;
    Node():pleft(NULL),pright(NULL){}
    Node(int l,int r):left(l),right(r),max(-1),min(0x7fffffff),pleft(NULL),pright(NULL){}
};

struct Point{
    int min;
    int max;
    Point(int ma,int mi):max(ma),min(mi){};
};

int heights[MAXN];

void build(Node*p){
    if(p->left == p->right){
        p->max = heights[p->left];
        p->min = p->max;
        return;
    }
    //calc the max and min value.
    for (int i=p->left;i<=p->right;++i){
        if(heights[i]>p->max)
            p->max = heights[i];
        if(heights[i]<p->min)
            p->min = heights[i];
    }
    int mid = (p->left + p->right) >> 1;
    p->pleft = new Node(p->left,mid);
    build(p->pleft);
    p->pright= new Node(mid+1,p->right);
    build(p->pright);
}

Point query(Node * p, int left,int right){
    if(left==p->left && right == p->right)
        return Point(p->max,p->min);
    int mid = (p->left+p->right) >> 1;
    if(left > mid)
        return query(p->pright,left,right);
    else if(right <= mid)
        return query(p->pleft,left,right);
    else{
        Point pl = query(p->pleft,left,mid);
        Point pr = query(p->pright,mid+1,right);
        int tmin = pl.min < pr.min ? pl.min : pr.min;
        int tmax = pl.max > pr.max ? pl.max : pr.max;
        return Point(tmax,tmin);
    }
}


// for debug.
// void dfs(Node * p){
//     if(p == NULL)
//         return;
//     cout<<"DFS TO: ["<<p->left<<", "<<p->right<<"] , ("<<p->max<<", "<<p->min<<")"<<endl;
//     dfs(p->pleft);
//     dfs(p->pright);
// }
int main(){
    int N,Q;
    scanf("%d%d",&N,&Q);
    for(int i=0;i<N;++i){
        scanf("%d",&heights[i]);
    }
    Node * head = new Node(0,N-1);
    build(head);
    // dfs(head);
    
    int l,r;
    for(int i=0;i<Q;++i){
        scanf("%d%d",&l,&r);
        Point point = query(head,l-1,r-1);
        printf("%d
",point.max - point.min);
    }
    return 0;  
}

View Code