codevs 3304フルーツ姉さんフルーツ街をぶらぶらI

-昨日の夜に私の線分の木のやり方を調整していないで、今日やっと来て、この問題の正解は線分の木かもしれないと感じて、前にDPという方法は少し引っ張って、しかし過ぎることができて、過ぎることができて良いQQQ*テーマのリンク:http://codevs.cn/problem/3304/ -最大値、最小値、答えの3つの値を同時に返すため、クエリ時に構造体型のAsk関数を定義することで、Ask_を単独で書く必要がなくなります.maxとAsk_min関数は、時間と労力を節約します.Ask関数を返すたびに、答えと右(左)区間の最大値を左(右)区間の最小値の値と比較することに注意してください.コード:

#include
#include
#include
#include
#include
using namespace std;

const int maxn=2e5+10,inf=1e8+10;
int n,m,Ans;
int a[maxn];
struct hh
{
    int l,r;
    int maxx,minn,ans1,ans2;
}tree[maxn<<2];
struct lxt
{
    int ma,mi,ans;
};

void build(int l,int r,int i)
{
    tree[i].l=l;
    tree[i].r=r;
    if(l==r) 
    {
        tree[i].minn=tree[i].maxx=a[l];
        tree[i].ans1=tree[i].ans2=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,i<<1);
    build(mid+1,r,i<<1|1);
    tree[i].minn=min(tree[i<<1].minn,tree[i<<1|1].minn);
    tree[i].maxx=max(tree[i<<1].maxx,tree[i<<1|1].maxx);
    tree[i].ans1=max(tree[i<<1|1].maxx-tree[i<<1].minn,max(tree[i<<1|1].ans1,tree[i<<1].ans1));
    tree[i].ans2=max(tree[i<<1].maxx-tree[i<<1|1].minn,max(tree[i<<1|1].ans2,tree[i<<1].ans2));
    if(tree[i].ans1<0) tree[i].ans1=0;
    if(tree[i].ans2<0) tree[i].ans2=0;
}
lxt ask_one(int l,int r,int i)
{
    lxt f;
    f.ans=0;
    f.mi=inf;
    f.ma=-inf;
    int lx=tree[i].l,rx=tree[i].r;
    if(lx>=l&&rx<=r)
    {
        f.ans=tree[i].ans1;
        f.ma=tree[i].maxx;
        f.mi=tree[i].minn;
        return f;
    }
    int mid=(lx+rx)>>1;
    lxt A,B;
    if(l<=mid) 
    {
        A=ask_one(l,r,i<<1); 
        f.ans=max(f.ans,A.ans);
        f.mi=min(f.mi,A.mi);
        f.ma=max(f.ma,A.ma);
    }
    if(r>mid) 
    {
        B=ask_one(l,r,i<<1|1);
        f.ans=max(f.ans,B.ans);
        f.mi=min(f.mi,B.mi);
        f.ma=max(f.ma,B.ma);
    }
    if(l<=mid&&r>mid) 
      f.ans=max(f.ans,B.ma-A.mi);
    return f;
}
lxt ask_two(int l,int r,int i)
{
    lxt f;
    f.ans=0;
    f.mi=inf;
    f.ma=-inf;
    int lx=tree[i].l,rx=tree[i].r;
    if(lx>=l&&rx<=r)
    {
        f.ans=tree[i].ans2;
        f.ma=tree[i].maxx;
        f.mi=tree[i].minn;
        return f;
    }

    int mid=(lx+rx)>>1;
    lxt A,B;
    if(l<=mid) 
    {
        A=ask_two(l,r,i<<1); 
        f.ans=max(f.ans,A.ans);
        f.mi=min(f.mi,A.mi);
        f.ma=max(f.ma,A.ma);
    }
    if(r>mid) 
    {
        B=ask_two(l,r,i<<1|1);
        f.ans=max(f.ans,B.ans);
        f.mi=min(f.mi,B.mi);
        f.ma=max(f.ma,B.ma);
    }
    if(l<=mid&&r>mid) 
      f.ans=max(f.ans,A.ma-B.mi);
    return f;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    build(1,n,1);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        Ans=0;
        if(x<y) Ans=ask_one(x,y,1).ans;
        else if(x>y) Ans=ask_two(y,x,1).ans;
        printf("%d
",Ans);
    }
    return 0;
}