BZOJ 1699[Usaco 2007 Jan]Balanced Lineupキューセグメントツリー


タイトル:リンク


方法:線分ツリー


解析:


題意はすぐに解く。


区間最大値と最小値の差を複数回尋ねると,明らかにセグメントツリーまたはrmqメンテナンス区間最値を直接上線すればよい.


コード:

#include 
#include 
#include 
#include 
#define N 50010
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pa pair
using namespace std;
int n,q;
int ma[N<<2],mi[N<<2],dis[N<<2];
void init()
{
    memset(ma,-1,sizeof(ma));
    memset(mi,0x3f,sizeof(mi));
}
void pushup(int rt)
{
    ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
    mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        int x;
        scanf("%d",&x);
        ma[rt]=mi[rt]=x;
        return;
    }
    int mid=(l+r)>>1;
    build(lson),build(rson);
    pushup(rt);
}
pa query(int L,int R,int l,int r,int rt)
{
    pa ret;
    ret.first=-1,ret.second=0x3f3f3f3f;
    if(L<=l&&r<=R)
    {
        pa p;
        p.first=ma[rt],p.second=mi[rt];
        return p;
    }
    int mid=(l+r)>>1;
    if(L<=mid)
    {
        pa tmp=query(L,R,lson);
        ret.first=max(ret.first,tmp.first),ret.second=min(ret.second,tmp.second);
    }
    if(R>mid)
    {
        pa tmp=query(L,R,rson);
        ret.first=max(ret.first,tmp.first),ret.second=min(ret.second,tmp.second);
    }
    return ret;
}
int main()
{
    init();
    scanf("%d%d",&n,&q);
    build(1,n,1);
    for(int i=1;i<=q;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        pa tmp=query(x,y,1,n,1);
        printf("%d
"
,tmp.first-tmp.second); } }