题解：CF2057D Gifts Order

· · 题解

简要说明题意：

给出一个有 n 个元素的数组 a 和 q 次查询，对于初始状态和每次查询结束后的状态，求 \max\{a_l,a_{l+1},\dots,a_{r-1},a_r\}-\min\{a_l,a_{l+1},\dots,a_{r-1},a_r\}-(r-l) 的最大值，其中 1 \leq l \leq r \leq n。

题目分析：

应该不难想到，l,r 一定是区间的两个最值，可以用反证法证明。

那么我们可以把后面的 r-l 这一项整合进前面的式子。

如果最大值在最小值的右边，那就等价于 b_i=a_i-i 求全局的 \max\{b_r-b_l\} \quad (1 \leq l \leq r \leq n)。最大值在最小值左边的情况也同理，b_i=a_i+i，求全局的 \max\{b_l-b_r\} \quad (1 \leq l \leq r \leq n)。

考虑到最大值不是在最小值左边就是右边（重合的情况两个式子都可以考虑到），所以我们同时维护两种情况，然后求两种情况的最大即可。

那么现在问题来了，要怎么维护这个带了一点条件（即最大在最小的右/左边）的极值？我们不能直接维护最大/最小，但我们如果已知两个区间的最大值，最小值和答案，我们可以合并成一个区间，这个过程就是线段树的 push_up 操作。

给出类似的题目：CF527C 和 SPOJGSS3。用线段树维护区间的答案，最大/最小值。然后在 push_up 操作里维护。

具体看代码吧：

#include<cstdio>
#include<algorithm>
using namespace std;
int a[200001],c[200001];
struct node{
    int l,r;
    long long min,max,cnt;
    node(int l_=-1,int r_=-1,long long min_=1.3e9,long long max_=-1.3e9,long long cnt_=0ll) :l(l_),r(r_),min(min_),max(max_),cnt(cnt_) {}
}tree0[800001],tree1[800001];
node push_up_tree0(node l,node r){
    node temp(l.l,r.r);
    temp.min=min(l.min,r.min);
    temp.max=max(l.max,r.max);
    temp.cnt=max(l.cnt,r.cnt);
    temp.cnt=max(temp.cnt,r.max-l.min);
    return temp;
}
node push_up_tree1(node l,node r){
    node temp(l.l,r.r);
    temp.min=min(l.min,r.min);
    temp.max=max(l.max,r.max);
    temp.cnt=max(l.cnt,r.cnt);
    temp.cnt=max(temp.cnt,l.max-r.min);
    return temp;
}
auto push_up=push_up_tree0;
void build(node* tree,int p,int l,int r,node push_up(node,node)){ //这个是函数指针，如果你是OI选手，这个和sort传cmp一样
    tree[p]=node(l,r);
    if(l==r) tree[p].min=tree[p].max=c[l];
    else build(tree,p<<1,l,(l+r)>>1,push_up),build(tree,(p<<1)|1,((l+r)>>1)+1,r,push_up),tree[p]=push_up(tree[p<<1],tree[(p<<1)|1]);
}
void modify(node* tree,int p,int x,int v,node push_up(node,node)){
    // printf("p=%d tree[p].l=%d tree[p].r=%d x=%d\n",p,tree[p].l,tree[p].r,x);
    if(tree[p].l==tree[p].r&&tree[p].l==x){
        tree[p].max=tree[p].min=v;
        return;
    }
    int mid=(tree[p].l+tree[p].r)>>1;
    if(x<=mid) modify(tree,p<<1,x,v,push_up);
    else modify(tree,(p<<1)|1,x,v,push_up);
    tree[p]=push_up(tree[p<<1],tree[(p<<1)|1]);
}
node query(node* tree,int p,int l,int r,node push_up(node,node)){ //答案合并和push_up的流程完全一样
    if(tree[p].l<=l&&tree[p].r<=r) return tree[p];
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid&&mid<=r) return push_up(query(tree,p<<1,l,r,push_up),query(tree,(p<<1)|1,l,r,push_up));
    if(l<=mid) return query(tree,p<<1,l,r,push_up);
    return query(tree,(p<<1)|1,l,r,push_up);
}
int main(){
    int T,n,q,x,y;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;++i) scanf("%d",a+i),c[i]=a[i]-i;
        build(tree0,1,1,n,push_up_tree0);
        for(int i=1;i<=n;++i) c[i]=a[i]+i;
        build(tree1,1,1,n,push_up_tree1);
        printf("%lld\n",max(query(tree0,1,1,n,push_up_tree0).cnt,query(tree1,1,1,n,push_up_tree1).cnt));
        while(q--){
            scanf("%d%d",&x,&y);
            modify(tree0,1,x,y-x,push_up_tree0),modify(tree1,1,x,y+x,push_up_tree1);
            printf("%lld\n",max(query(tree0,1,1,n,push_up_tree0).cnt,query(tree1,1,1,n,push_up_tree1).cnt));
        }
    }
    return 0;
}