2013年10月26日 星期六

TIOJ 1603 胖胖殺蚯事件

[線段樹]
第一次寫TIOJ上的線段樹 :3



#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define N 100000
#define inf 2147483649
#define max(a,b) ((a)>(b)) ? (a):(b)
#define min(a,b) ((a)>(b)) ? (b):(a)
long long int TREE[N*4];
long long int MAXTREE[N*4];
long long int MINTREE[N*4];
int base;
int n;
void BuildTree()
{
    for(int lx=1;lx<=n;lx++)
    {
        for(int prc=(base+lx)>>1;prc;prc>>=1)
        {
            MAXTREE[prc]=max(MAXTREE[prc],TREE[base+lx]);
            MINTREE[prc]=min(MINTREE[prc],TREE[base+lx]);
        }
    }
}
long long int FindSub(int a,int b)
{
    long long int gmin=TREE[b+base];
    long long int gmax=TREE[b+base];
    for(a+=base-1,b+=base+1;(a^b^1);a>>=1,b>>=1)
    {
        if(~a&1)
        {
            gmin=min(gmin,MINTREE[a^1]);
            gmax=max(gmax,MAXTREE[a^1]);
        }
        if(b&1)
        {
            gmin=min(gmin,MINTREE[b^1]);
            gmax=max(gmax,MAXTREE[b^1]);
        }
    }
    return gmax-gmin;
}
int main()
{
    int m;scanf("%d %d",&n,&m);
    memset(MINTREE,inf,sizeof(MINTREE));
    base=pow(2,ceil(log2(n)))-1;
    for(int lx=1;lx<=n;lx++)
    {
        scanf("%I64d",&TREE[lx+base]);
        MINTREE[lx+base]=TREE[lx+base];
        MAXTREE[lx+base]=TREE[lx+base];
    }
    BuildTree();
    for(int lx=0;lx<m;lx++)
    {
        int a,b;scanf("%d %d",&a,&b);
        printf("%d\n",FindSub(a,b));
    }
    return 0;
}

沒有留言:

張貼留言