题解：P14028 【MX-X20-T2】「FAOI-R7」最小极差（jicha）

· · 题解

思路：

首先，考虑极差为 0 的情况需要满足什么：

假设第 i 个数可以被修改 sum_i 次，那么这个数的最大值为 a_i + sum_i，最小值为 a_i - sum_i，也就是说这个数可以是区间 [a_i-sum_i,a_i+sum_i] 中的任意数。只要有一个数在所有 a_i 被修改后可以是的区间内，那么就说明修改后的 a_i 可以全部相等，也就是极差为 0。

考虑用差分维护可以被修改的次数。

对于其它情况：

我们知道极差是序列里最大值和最小值的差，于是我们可以把所有可能的最大值里的最小值和所有可能的最小值里的最大值做差即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
LL maxx[int(2*1e5+10)],minn[int(2*1e5+10)];
int diff[int(2*1e5+10)];
LL sum;
int n,m,T,u,v;
LL a[int(2*1e5+10)];
void solve(){
    cin>>n>>m;
    diff[0]=diff[n+1]=0;sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];diff[i]=0;
    }
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        diff[u]++;diff[v+1]--;
    }
    bool bj=0;
    for(int i=1;i<=n;i++){
        sum+=diff[i];
        maxx[i]=a[i]+sum;
        minn[i]=a[i]-sum;
        // cout<<sum<<" ";
    }
    LL ma=maxx[1],mi=minn[1];
    LL l=1e9+10,r=0;
    for(int i=2;i<=n;i++){
        if(maxx[i]<mi||minn[i]>ma){
            bj=1;
        }
        mi=max(mi,minn[i]);
        ma=min(maxx[i],ma);
        // l=min(l,minn[i]);
        // r=max(r,maxx[i]);
    }
    if(!bj){
        cout<<"0\n";
        return;
    }
    cout<<abs(mi-ma)<<"\n";
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(;T--;solve());
    return 0;
}

/*
｀　　　　　　　　　　　　　　　　　　　　　　　４　　　　０００　　　　　　４
　　　　　　　　　　　　　　　　　　　　　　　４４　　　０　　　０　　　　４４
ｘ　　　ｘ　　ｙ　　　ｙ　　ｘ　　　ｘ　　　　４４　　　０　　　０　　　　４４
ｘ　　　ｘ　　ｙ　　　ｙ　　ｘ　　　ｘ　　　４　４　　　０　　　０　　　４　４
　ｘ　ｘ　　　ｙ　　　ｙ　　　ｘ　ｘ　　　　４　４　　　０　　　０　　　４　４
　　ｘ　　　　　ｙ　ｙ　　　　　ｘ　　　　４　　４　　　０　　　０　　４　　４
　ｘ　ｘ　　　　ｙ　ｙ　　　　ｘ　ｘ　　　４４４４４　　０　　　０　　４４４４４
ｘ　　　ｘ　　　　ｙ　　　　ｘ　　　ｘ　　　　　４　　　０　　　０　　　　　４
ｘ　　　ｘ　　　　ｙ　　　　ｘ　　　ｘ　　　　　４　　　　０００　　　　　　４
　　　　　　　ｙｙ
*/