Codeforces Hello 2025 D题解

这道题感觉很好，于是打算写一篇题解。

https://codeforces.com/contest/2057/problem/D

先不考虑 q次修改。不修改的情况下，要想使得max(al​,al+1​,…,ar​)−min(al​,al+1​,…,ar​)−(r−l)最大，那么al ,ar都必须是端点。不然（r-l）会变大，然而max-min却不会变，会使得答案变小。

所以考虑最大值在左边和最大值在右边的情况

在左边：ans=(al+l)-(ar+r);

在右边：ans=(ar-r)-(al-l);

那么对于q次询问只要建立一颗线段树动态维护即可。

对于转移 当前节点答案可以选择一个分界点 答案可以从分界点左侧 分界点右侧 和分界点两侧转移过来 只要取最大就好了。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define lr (ro*2)
#define rr (ro*2+1)
#define mid ((l+r)/2)
using namespace std; 
const int N=1e6;
int a[N];
int n,q;
struct node
{
    int max1,min1; 
    int max2,min2; 
    int ans1,ans2; 
};
node tr[N*4];

void push_up(int ro){
    tr[ro].max1=max(tr[lr].max1,tr[rr].max1);
    tr[ro].min1=min(tr[lr].min1,tr[rr].min1);
    tr[ro].max2=max(tr[lr].max2,tr[rr].max2);
    tr[ro].min2=min(tr[lr].min2,tr[rr].min2);
    tr[ro].ans1=max({tr[lr].ans1,tr[rr].ans1,tr[lr].max1-tr[rr].min1});
    tr[ro].ans2=max({tr[lr].ans2,tr[rr].ans2,tr[rr].max2-tr[lr].min2});
}
void build(int ro=1,int l=1,int r=n){
    if(l==r){
        tr[ro].max1=tr[ro].min1=a[l]+l;
        tr[ro].max2=tr[ro].min2=a[l]-l;
        tr[ro].ans1=tr[ro].ans2=0;
        return;
    }
    build(lr,l,mid);
    build(rr,mid+1,r);
    push_up(ro);
}
void update(int x,int d,int ro=1,int l=1,int r=n){
    if(l==r){
        tr[ro].max1=tr[ro].min1=d+x;
        tr[ro].max2=tr[ro].min2=d-x;
        tr[ro].ans1=tr[ro].ans2=0;
        return;
    }
    if(x<=mid)
        update(x,d,lr,l,mid);
    else
        update(x,d,rr,mid+1,r);
    push_up(ro);
}
signed main(){
    int T;
    cin>>T;
    while (T--)
    {
        cin>>n>>q;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        build();
        cout<<max(tr[1].ans1,tr[1].ans2)<<endl;
        while (q--)
        {
            int p,x;
            cin>>p>>x;
            update(p,x);
            cout<<max(tr[1].ans1,tr[1].ans2)<<endl;
        }
    }
}