题解 CF935F 【Fafa and Array】

· · 题解

题意:

给出一个序列A ,定义函数f(A)=\sum_{i=1}^{n-1}|a_i-a_{i+1}|

给出两种操作:

$2.l$ $r$ $x$ ,把区间$[l,r]$ 加上$x n\le10^5,q\le10^5,x_i\le10^9

记ans=f(A)

考虑a_i+x与a_{i-1},a_{i+1}的大小关系

一:a_i+x\lt a_{i-1},a_i+x\lt a_{i+1}

\Delta=-2x

二:a_{i-1}\lt a_i+x\lt a_{i+1}

\Delta=(|(a_i+x)-a_{i+1}|+|a_{i-1}-(a_i+x)|)-(|a_i-a_{i+1}|+|a_{i-1}-a_i|) =-x+|a_i-a_{i-1}+x|+|a_i-a_{i-1}|\le 0

三:a_{i-1}\le a_i+x,a_{i+1}\le a_i+x

再考虑a_i与a_{i-1},a_{i+1}的大小关系

①:a_{i-1}\le a_i,a_{i+1}\le a_i,\Delta=2*x

②:a_{i-1}\le a_i\lt a_{i+1},\Delta=2*x-2*(a_{i+1}-a_i)

③:a_i\lt a_{i-1},a_i\lt a_{i+1},\Delta=2*x-2*[(a_{i-1}-a_i)+(a_{i+1}-a_i)]

显然只有第三种情况是可能对答案贡献是正的

所以我们可以考虑用线段树维护min\{max(0,a_{i-1}-a_i)+max(0,a_{i+1}-a_i)\}

区间修改,考虑差分,令a_i=a_{i+1}-a_i

那么我们就是维护min\{max(0,-a_{i-1})+max(0,a_i)\}

注意特判一下l=1,r=n的情况

那么有没有\Delta一定是负数的情况呢?

有,当l=r时,我们只能修改这个值,所以可能出现负贡献,特判一下就好了

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=1e5+5;
const long long inf=1e18;
typedef long long ll;
int n,m;ll ans,a[N],tr[N<<2];
#define lc p<<1
#define rc p<<1|1
inline void up(int p){tr[p]=min(tr[lc],tr[rc]);}
void build(int p,int L,int R){
    if(L==R){
        if(L>1)tr[p]=max(0ll,a[L])+max(0ll,-a[L-1]);
        ans+=abs(a[L]);return;
    }int mid=(L+R)>>1;
    build(lc,L,mid),build(rc,mid+1,R);
    up(p);
}
void mdy(int p,int L,int R,int x,int w){
    if(L==R){
        ans+=abs(a[L]+w)-abs(a[L]),a[L]+=w;
        if(x>1)tr[p]=max(0ll,-a[L-1])+max(0ll,a[L]);
        if(w&&x<n-1)mdy(1,1,n-1,x+1,0);return;
    }int mid=(L+R)>>1;
    if(x<=mid)mdy(lc,L,mid,x,w);
    else mdy(rc,mid+1,R,x,w);up(p);
}
ll qry(int p,int L,int R,int a,int b){
    if(a<=L&&R<=b)return tr[p];
    int mid=(L+R)>>1;
    if(b<=mid)return qry(lc,L,mid,a,b);
    if(a>mid)return qry(rc,mid+1,R,a,b);
    return min(qry(lc,L,mid,a,b),qry(rc,mid+1,R,a,b));
}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n);int op,l,r,x;
    fp(i,1,n)sd(a[i]);
    fp(i,1,n)a[i]=a[i+1]-a[i];
    build(1,1,n-1);sd(m);
    while(m--){
        sd(op),sd(l),sd(r),sd(x);
        if(op==1){
            if(l==r){
                if(l==1)we(ans-abs(a[l])+abs(a[l]-x));
                else if(l==n)we(ans-abs(a[l-1])+abs(a[l-1]+x));
                else we(ans-abs(a[l-1])-abs(a[l])+abs(a[l-1]+x)+abs(a[l]-x));
            }else{
                ll tp=2*(x-qry(1,1,n-1,l>1?l:2,r));
                if(l==1)cmax(tp,-abs(a[l])+abs(a[l]-x));
                if(r==n)cmax(tp,-abs(a[r-1])+abs(a[r-1]+x));
                we(ans+max(0ll,tp));
            }
        }else{
            l>1?mdy(1,1,n-1,l-1,x):void();
            r<n?mdy(1,1,n-1,r,-x):void();
        }
    }
return Ot(),0;
}