//线段树大大大大水题

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn =5e4;
const int inf =1e7;

struct
{
    int l,r;
    int ma,mi;
}tree[maxn*4+10];

void update(int x)
{
    if(tree[x].l==tree[x].r)
        return;
    tree[x].ma=max(tree[x*2].ma,tree[x*2+1].ma);
    tree[x].mi=min(tree[x*2].mi,tree[x*2+1].mi);
}

void build(int x,int l,int r)
{
    tree[x].l=l;
    tree[x].r=r;
    if(l==r)
    {
        int w;
        scanf("%d",&w);
        tree[x].ma=tree[x].mi=w;
    }
    else
    {
        int mid=(l+r)/2;
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
        update(x);
    }
}

int getmax(int x,int l,int r)
{
    if(l<=tree[x].l&&r>=tree[x].r)
        return tree[x].ma;
    else
    {
        int res=0;
        int mid=(tree[x].l+tree[x].r)/2;
        if(l<=mid)
            res=max(res,getmax(x*2,l,r));
        if(r>mid)
            res=max(res,getmax(x*2+1,l,r));
        return res;
    }
}

int getmin(int x,int l,int r)
{
    if(l<=tree[x].l&&r>=tree[x].r)
        return tree[x].mi;
    else
    {
        int res=inf;
        int mid=(tree[x].l+tree[x].r)/2;
        if(l<=mid)
            res=min(res,getmin(x*2,l,r));
        if(r>mid)
            res=min(res,getmin(x*2+1,l,r));
        return res;
    }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        int ll,rr;
        scanf("%d%d",&ll,&rr);
        //printf("%d %d\n",getmax(1,ll,rr),getmin(1,ll,rr));
        printf("%d\n",getmax(1,ll,rr)-getmin(1,ll,rr));
    }
    return 0;
}

• Re:水水水水水水水水水水 (1817) li784414652 2019-08-19 00:09:28