义乌中学暑假集训 2021.07.15 B

#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define int long long
using namespace std;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(int x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
Cn int N=1e5+10;
int Tt,n,q,a[N];
class SegmentTree{
    private:
        #define mid (l+r>>1)
        #define PT CI x=1,CI l=1,CI r=n-1
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
        #define PU(x) (T[x].S=T[x<<1].S+T[x<<11].S,T[x].SS=T[x<<1].SS+T[x<<11].SS-(T[x<<11].pre>0&&T[x<<1].suf>0),T[x].pre=T[x<<1].pre?T[x<<1].pre:T[x<<11].pre,T[x].suf=T[x<<11].suf?T[x<<11].suf:T[x<<1].suf)
    public:
        struct node{int S,SS,pre,suf;}T[N<<2];
        I void B(PT){
            if(l==r) return T[x].pre=T[x].suf=a[l+1]-a[l],T[x].S=max(T[x].pre,0LL),T[x].SS=(T[x].pre>0LL),void();
            B(LT),B(RT),PU(x);
        }
        I void U(CI p,CI v,PT){
            if(l==r) return T[x].pre+=v,T[x].suf+=v,T[x].S=max(T[x].pre,0LL),T[x].SS=(T[x].pre>0LL),void();
            p<=mid?U(p,v,LT):U(p,v,RT),PU(x);
        }
}S;
signed main(){
    RI i,o,x,y,z;read(Tt);W(Tt--){
        for(read(n),read(q),i=1;i<=n;i++) read(a[i]);
        for(S.B(),i=1;i<=q;i++) read(o),o?write(S.T[1].S),pc(' '),write(S.T[1].SS<<1),pc('\n'):(read(x),read(y),read(z),x>1&&(S.U(x-1,z),0),y<n&&(S.U(y,-z),0));
    }return 0;
}