タイトル：リンク
方法:線分ツリー
解析:
題意はすぐに解く。
区間最大値と最小値の差を複数回尋ねると,明らかにセグメントツリーまたは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);
}
}