（线段树）Balanced Lineup --POJ --3264-白红宇

（线段树）Balanced Lineup --POJ --3264

阅读量：4960 次

发布时间：2019-06-12

本文共 1652 字，大约阅读时间需要 5 分钟。

链接：

对于POJ老是爆，我也是醉了，链接等等再发吧！

只是简单的建树，每个节点上记录它的最大值和最小值，最后查询一下，就ok了

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 const int N = 50005; 8 using namespace std; 9 10 #define Lson r<<111 #define Rson r<<1|112 #define mid a[r].Mid()13 14 struct node15 {16 int L, R;17 int Max, Min;18 int Mid()19 {20 return (L+R)>>1;21 }22 int len()23 {24 return (R-L+1);25 };26 } a[N<<2];27 28 void BuildTree(int r, int L, int R)29 {30 a[r].L=L, a[r].R=R;31 32 if(L==R)33 {34 scanf("%d", &a[r].Min);35 a[r].Max = a[r].Min;36 return ;37 }38 39 BuildTree(Lson, L, mid);40 BuildTree(Rson, mid+1, R);41 42 a[r].Min = min(a[Lson].Min, a[Rson].Min);43 a[r].Max = max(a[Lson].Max, a[Rson].Max);44 }45 46 int QueryMax(int r, int L, int R)47 {48 if(a[r].L==L && a[r].R==R)49 return a[r].Max;50 51 if(R<=mid)52 return QueryMax(Lson, L, R);53 else if(L>mid)54 return QueryMax(Rson, L, R);55 else56 {57 return max(QueryMax(Lson, L, mid), QueryMax(Rson, mid+1, R));58 }59 }60 61 int QueryMin(int r, int L, int R)62 {63 if(a[r].L==L && a[r].R==R)64 return a[r].Min;65 66 if(R<=mid)67 return QueryMin(Lson, L, R);68 else if(L>mid)69 return QueryMin(Rson, L, R);70 else71 {72 return min(QueryMin(Lson, L, mid), QueryMin(Rson, mid+1, R));73 }74 }75 76 77 78 int main()79 {80 int n, m;81 while(scanf("%d%d", &n, &m)!=EOF)82 {83 84 BuildTree(1, 1, n);85 86 int L, R;87 88 while(m--)89 {90 scanf("%d%d", &L, &R);91 printf("%d\n", QueryMax(1, L, R)-QueryMin(1, L, R));92 }93 }94 95 return 0;96 }