POJ 3264 线段树 ST-白红宇

POJ 3264 线段树 ST

阅读量：6026 次

发布时间：2019-06-20

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

题意：给你一个数列，从中挑一段，问你这段数的最大值减最小值是多少。

思路：线段树。

// by Sirius_Ren#include 
     
      #include 
      
       #define N 50000using namespace std;int n,q,xx,yy,tree[N*4],MAX[N*4],MIN[N*4],ansmax,ansmin;void build(int l,int r,int pos){    if(l==r){scanf("%d",&tree[pos]);MAX[pos]=MIN[pos]=tree[pos];return;}    int mid=(l+r)/2;    build(l,mid,pos*2),build(mid+1,r,pos*2+1);    MAX[pos]=max(MAX[pos*2],MAX[pos*2+1]);MIN[pos]=min(MIN[pos*2],MIN[pos*2+1]);}void query(int l,int r,int pos){    if(l>=xx&&r<=yy){ansmax=max(ansmax,MAX[pos]);ansmin=min(ansmin,MIN[pos]);return;}    int mid=(l+r)/2;    if(mid>=yy)query(l,mid,pos*2);    else if(mid

这里写图片描述

ST：

#include 
     
      #include 
      
       #include 
       
        using namespace std;int n,m,xx,yy,MAX,MIN,f[1000001][17],g[1000001][17];int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        scanf("%d",&f[i][0]),g[i][0]=f[i][0];    for(int j=1;j<=16;j++)        for(int i=1;i<=n;i++)            if(i+(1<
        
         <=n){                f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);                g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);            }    while(m--){        scanf("%d%d",&xx,&yy);        int k=log(yy-xx+1)/log(2.0);        MAX=max(f[xx][k],f[yy-(1<

这里写图片描述