题解 CF2057D Gifts Order

cjh20090318 · 2025-01-06 08:19:53 · 题解

非常好 D，让我晚一秒交上去，结果掉分了。

题意

一个长度为 n 的序列 a，定义函数 f(l,r)：

有 q 次修改，在第一次修改前和每一次修改 a_p \gets x 后，求对于所有 1 \le l \le r \le n，f(l,r) 的最大值。

分析

为了让以上值最大区间长度一定不能浪费，所以能取最大值的只可能有两种情况：

所以直接用线段树分别维护 a_i - i 和 a_i + i 的最值即可。

具体操作见代码，时间复杂度 O(n \log n)。

代码

//the code is from chenjh
#include<cstdio>
#include<algorithm>
#define MAXN 200002
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
using ci=const int;
int n,q;
struct Node{
    //a_l + l - (a_r + r)
    //a_r - r - (a_l - l)
    int mx1,mx2,mn1,mn2,ans;// 1 表示 a_i + i，2 表示 a_i - i。
    Node operator + (const Node&A){//节点合并。
        Node ret;
        ret.mx1=max(mx1,A.mx1),ret.mx2=max(mx2,A.mx2);//对两个最大值取最大值。
        ret.mn1=min(mn1,A.mn1),ret.mn2=min(mn2,A.mn2);//对两个最小值取最小值。
        ret.ans=max({ans,A.ans,mx1-A.mn1,A.mx2-mn2});//两边的答案，以及 (a_l + l) - (a_r + r) 和 (a_r - r) - (a_l - l) 两种情况。
        return ret;
    }
}t[MAXN<<2];//线段树空间记得开 4 倍，要不然就会像我 RE on #7 遗憾离场。
int a[MAXN];
void bld(ci rt,ci l,ci r){
    if(l==r){t[rt].mx1=t[rt].mn1=a[l]+l,t[rt].mx2=t[rt].mn2=a[l]-l,t[rt].ans=0;return;}//线段树建树。
    int mid=(l+r)>>1;
    bld(lson,l,mid),bld(rson,mid+1,r);
    t[rt]=t[lson]+t[rson];
}
void upd(ci rt,ci l,ci r,ci p,ci v){//单点修改。
    if(l==r){a[l]=v,t[rt].mx1=t[rt].mn1=a[l]+l,t[rt].mx2=t[rt].mn2=a[l]-l,t[rt].ans=0;return;}
    int mid=(l+r)>>1;
    p<=mid?upd(lson,l,mid,p,v):upd(rson,mid+1,r,p,v);
    t[rt]=t[lson]+t[rson];
}
void solve(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    bld(1,1,n);
    printf("%d\n",t[1].ans);//直接查询全局最大值。
    for(int p,x;q--;){
        scanf("%d%d",&p,&x);
        upd(1,1,n,p,x);
        printf("%d\n",t[1].ans);
    }
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve(); 
    return 0;
}