Balanced Lineup poj 3264

也可以用st表做

但st表不支援動态更新

資料結構碼得還是太少，本廢物給您表演一個花式手抖

#include <iostream>
#include <math.h>
#include <string.h>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <algorithm>
#include <cstdio>
using namespace std;
int maxn[200007],minn[200007];
void update(int root,int v,int p,int l,int r)
{
    if(l==r)
     {
         maxn[root]=max(maxn[root],v);
         minn[root]=min(minn[root],v);
         return ;
     }
     int mid=(l+r)>>1;
     
     if(p<=mid)
     {
         update(root<<1,v,p,l,mid);
     }
     if(p>mid)
     {
         update(root*2+1,v,p,mid+1,r);
     }
     maxn[root]=max(maxn[root<<1],maxn[root*2+1]);
     minn[root]=min(minn[root<<1],minn[root*2+1]);
}
int  query1(int root,int l,int r,int ql,int qr)
{  
  //  if(l==r) return maxn[root];
    if(l>qr||r<ql) return 0;

    if(l>=ql&&r<=qr)
    {
        return maxn[root];
    }
    int mid=(l+r)>>1,ans=-1;
    if(ql<=mid)
    {
        ans=max(ans,query1(root<<1,l,mid,ql,qr));
    }
    if(qr>mid)
    {
        ans=max(ans,query1(root*2+1,mid+1,r,ql,qr));
    }
    return ans;
}
int  query2(int root,int l,int r,int ql,int qr)
{
     if(l>qr||r<ql) return (1<<27);

    if(l>=ql&&r<=qr)
    {
        return minn[root];
    }
    int mid=(l+r)>>1,ans=1<<27;
    if(ql<=mid)
    {
        ans=min(ans,query2(root<<1,l,mid,ql,qr));
    }
    if(qr>mid)
    {
        ans=min(ans,query2(root*2+1,mid+1,r,ql,qr));
    }
    return ans;
}
int main()
{
    

//    freopen("lys.in","r",stdin);
    memset(maxn,0,sizeof(maxn));
    memset(minn,0x3f,sizeof(minn));
    
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%d",&a);
        update(1,a,i,1,n);
    }
    for(int i=1;i<=m;i++)
    {
        int ql,qr;
        scanf("%d%d",&ql,&qr);
        printf("%d\n",query1(1,1,n,ql,qr)-query2(1,1,n,ql,qr));
    }
}