POJ3264 - Balanced Lineup(세그먼트 트리 기본)

사고의 방향

struct Node
{
    int l, r; //         
    int ls, rs; //     ，     
    int maxn, minn; //        
}

코드

#include 
#include 
#include 

using namespace std;

struct tNode
{
    int l, r;
    int ls, rs;
    int maxn, minn;
}tree[400100];
int nCount = 1;
int num[200100];

void build(int root, int l, int r)
{
    if(l==r)
    {
        //       1  
        tree[root].maxn = tree[root].minn = num[l];
        tree[root].l = tree[root].r = l;
    }
    else
    {
        //       
        tree[root].l = l;
        tree[root].r = r;
        //      
        int ls = tree[root].ls = ++nCount;
        int rs = tree[root].rs = ++nCount;
        //   build    
        build(ls, l, (l+r)/2);
        build(rs, (l+r)/2+1, r);
        //            ，       
        tree[root].maxn = max(tree[ls].maxn, tree[rs].maxn);
        tree[root].minn = min(tree[ls].minn, tree[rs].minn);
    }
}


void query(int root, int l, int r, pair<int, int> & ans)
{
    if(tree[root].l==l&&tree[root].r==r)
    {
        //            
        ans.first = max(ans.first, tree[root].maxn);
        ans.second = min(ans.second, tree[root].minn);
    }
    else if(l>=tree[tree[root].rs].l)
    {
        //        
        query(tree[root].rs, l, r, ans);
    }
    else if(r<=tree[tree[root].ls].r)
    {
        //        
        query(tree[root].ls, l, r, ans);
    }
    else
    {
        //       
        query(tree[root].ls, l, tree[tree[root].ls].r, ans);
        query(tree[root].rs, tree[tree[root].rs].l, r, ans);
    }
}

int main()
{
    int n, q;
    int l, s;
    pair<int, int> ans; //              

    scanf("%d%d", &n, &q);
    for(int i=1; i<=n; i++) scanf("%d", num+i);

    build(1, 1, n);

    for(int i=1; i<=q; i++)
    {
        scanf("%d%d", &l, &s);
        ans = pair<int, int>(0, 0x7fffffff);
        query(1, l, s, ans);
        printf("%d
", ans.first-ans.second);
    }
    return 0;
}