神仙 DS。
首先关于第一问可以轻松想到一个 DP，(dp_{i,j}) 表示考虑到第 (i) 位，这一位奇偶性为 (j) 的最大权值，时间复杂度 (n^2q)，可以拿到 (3) 分的好成绩（大雾），如果稍微动点脑子使用前缀和优化还可以拿到 (9) 分的好成绩，但是显然这个做法是没有前途的，因为这个 DP 对第二问没有任何启发作用，并且也无法将它优化到每次询问都可以在低于 (mathcal O(n)) 内处理的复杂度，因此我们只好放弃这个思路。
按照我们做题的经验，我们考虑分析一下这个权值最大的序列有什么性质，手玩几组数据后你就能发现以下性质：
Observation 1. 对于一个序列 (a)，我们如果将 (a) 划分成一段段上升段和下降段，那么我们选择的子序列的第 (2k+1) 个元素一定是第 (k) 个极小值点，第 (2k+2) 个元素一定是第 (k) 个极大值点
具体证明可用调整法，留给读者自己思考。
也就是说，第 (2k+1) 和第 (2k+2) 个元素一定是第 (k) 个上升段的开头和结尾，这个序列的权值就是所有上升段的结尾值减去开头的值。
注意到这个上升段、下降段维护起来有点棘手，因此我们不妨换个角度，用与其联系紧密的差分序列 (b_i=a_{i+1}-a_i) 来看待这个问题，因为差分序列的正负性即暗示了该元素位于上升段中还是下降段中。注意到对于一段上升序列，其末尾元素与开头元素的差就是这个差分序列中所有元素的和，而对于下降序列，其差分序列中所有元素都非正，因此我们稍微转化一下即可得到以下性质：
Observation 2. 对于序列 (a)，其子序列点值的最大值就是其差分序列中所有正数的和
这样第一问就解决了，因为每次区间加操作最多影响差分序列中两个元素的权值，因此这个贡献是可以 (mathcal O(1)) 计算的。
接下来考虑第二问，每次操作相当于移动最优序列中下标 (2k,2k+1) 元素，而根据之前的推论这两个元素必然是同一个下降段的首尾元素，而显然对于下降段中的某个元素 (x)，将 (x) 移至 (x+1) 会使得权值加上 (b_x)，因此操作等价于选择某个下降段中的某个不相交的前缀和后缀，并令权值加上这段前缀和后缀中所有元素的和，问最少几次操作能使权值 (le 0)。
由于下降段的差分序列中每个元素都 (le 0)，因此我们肯定会贪心地选择长度加起来等于下降段减 (1) 的前后缀，也就是将下标 (2k,2k+1) 元素移至某对相邻位置 (p,p+1)，这样贡献就是这个相邻段中差分序列权值之和加上 (b_p)，而我们显然会选择 (b_p) 最大的 (p) 作为目标位置，因此可以得到：
Observation 3. 对于差分序列上每个非正段，其移动一次权值最大减少量就是这段差分序列权值之和减去这段中 (b_i) 的最大值。
因此对于每个非正整数的段，其进行一次操作权值的最大减少量是确定的，而我们肯定会优先选择减少量最大的下降段，因此我们可以将所有连续段权值最大减少量扔进一个平衡树，每次询问在平衡树上二分即可。每次修改操作导致连续段的变化量是 (mathcal O(1)) 级别的，用个 set 维护一下即可，差分数组的区间最小值可用线段树维护。于是这题就被我们拆分成几步解决了，时间复杂度 (nlog n)。
注意点：注意特殊判断第一段和最后一段下降段。
码了 188 行
const int MAXN=1e5;
int n,qu,a[MAXN+5];ll b[MAXN+5],sum=0;
struct segtree{
struct node{int l,r;ll sum,mx;} s[MAXN*4+5];
void clear(int k){
if(s[k].l==s[k].r) return s[k].l=s[k].r=s[k].sum=s[k].mx=0,void();
clear(k<<1);clear(k<<1|1);s[k].l=s[k].r=s[k].sum=s[k].mx=0;
}
void pushup(int k){
s[k].mx=max(s[k<<1].mx,s[k<<1|1].mx);
s[k].sum=s[k<<1].sum+s[k<<1|1].sum;
}
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;if(l==r) return s[k].mx=s[k].sum=b[l],void();
int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k);
}
void modify(int k,int p,ll x){
if(s[k].l==s[k].r) return s[k].mx=s[k].sum=x,void();int mid=s[k].l+s[k].r>>1;
(p<=mid)?modify(k<<1,p,x):modify(k<<1|1,p,x);pushup(k);
}
ll getmax(int k,int l,int r){
if(l<=s[k].l&&s[k].r<=r) return s[k].mx;int mid=s[k].l+s[k].r>>1;
if(r<=mid) return getmax(k<<1,l,r);else if(l>mid) return getmax(k<<1|1,l,r);
else return max(getmax(k<<1,l,mid),getmax(k<<1|1,mid+1,r));
}
ll getsum(int k,int l,int r){
if(l<=s[k].l&&s[k].r<=r) return s[k].sum;int mid=s[k].l+s[k].r>>1;
if(r<=mid) return getsum(k<<1,l,r);else if(l>mid) return getsum(k<<1|1,l,r);
else return getsum(k<<1,l,mid)+getsum(k<<1|1,mid+1,r);
}
} st;
struct fhqtreap{
struct node{int ch[2],key,siz;ll sum,val;} s[MAXN*3+5];
int rt,ncnt;
fhqtreap(){rt=ncnt=0;}
void init(){
for(int i=1;i<=ncnt;i++) s[i].ch[0]=s[i].ch[1]=s[i].key=s[i].siz=s[i].sum=s[i].val=0;
rt=ncnt=0;
}
void pushup(int k){
s[k].sum=s[s[k].ch[0]].sum+s[s[k].ch[1]].sum+s[k].val;
s[k].siz=s[s[k].ch[0]].siz+s[s[k].ch[1]].siz+1;
}
void split(int k,ll v,int &a,int &b){
if(!k) return a=b=0,void();
if(s[k].val<=v) return a=k,split(s[k].ch[1],v,s[k].ch[1],b),pushup(k),void();
else return b=k,split(s[k].ch[0],v,a,s[k].ch[0]),pushup(k),void();
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(s[x].key<s[y].key) return s[x].ch[1]=merge(s[x].ch[1],y),pushup(x),x;
else return s[y].ch[0]=merge(x,s[y].ch[0]),pushup(y),y;
}
void insert(ll x){
// printf("insert %lld
",x);
s[++ncnt].sum=x;s[ncnt].val=x;s[ncnt].key=rand();s[ncnt].siz=1;
int k1,k2;split(rt,x-1,k1,k2);rt=merge(merge(k1,ncnt),k2);
// printf("%d
",rt);
}
void del(ll x){
// printf("del %lld
",x);
int k1,k2,k3;split(rt,x-1,k1,k2);split(k2,x,k2,k3);
rt=merge(merge(k1,s[k2].ch[0]),merge(s[k2].ch[1],k3));
}
int walk(int k,ll v){
if(v<=0) return 0;
if(s[k].sum+v>0) return -1;
// printf("%d %lld %lld %lld %lld
",k,v,s[s[k].ch[0]].sum,s[s[k].ch[1]].sum);
if(s[s[k].ch[0]].sum+v<=0) return walk(s[k].ch[0],v);
else if(s[s[k].ch[0]].sum+s[k].val+v<=0) return s[s[k].ch[0]].siz+1;
else return s[s[k].ch[0]].siz+1+walk(s[k].ch[1],v+(s[s[k].ch[0]].sum+s[k].val));
}
} trp;
ll getval(int l,int r){return st.getsum(1,l,r)-st.getmax(1,l,r);}
set<pii> itv;
void delitv(int l,int r){
assert(l<=r);
// printf("delitv %d %d
",l,r);
itv.erase(itv.find(mp(l,r)));
if((l^1)&&(r^(n-1))) trp.del(getval(l,r));
}
void insitv(int l,int r){
assert(l<=r);
// printf("insitv %d %d
",l,r);
itv.insert(mp(l,r));
if((l^1)&&(r^(n-1))) trp.insert(getval(l,r));
}
void chg(int x,ll v){
sum-=max(b[x],0ll);sum+=max(v,0ll);
if(b[x]>0&&v<=0){
pii nxt=*itv.upper_bound(mp(x,n+1));
pii pre=*--itv.lower_bound(mp(x,0));
int l=x,r=x;
if(nxt.fi==x+1) delitv(nxt.fi,nxt.se),r=nxt.se;
if(pre.se==x-1) delitv(pre.fi,pre.se),l=pre.fi;
st.modify(1,x,v);insitv(l,r);
} else if(b[x]<=0&&v>0){
pii lrg=*--itv.lower_bound(mp(x,n+1));
delitv(lrg.fi,lrg.se);st.modify(1,x,v);
if(lrg.se^x) insitv(x+1,lrg.se);
if(lrg.fi^x) insitv(lrg.fi,x-1);
} else if(b[x]<=0){
pii t=*--itv.lower_bound(mp(x,n+1));
delitv(t.fi,t.se);st.modify(1,x,v);
insitv(t.fi,t.se);
} else st.modify(1,x,v);
b[x]=v;
}
void clear(){
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
sum=0;itv.clear();trp.init();st.clear(1);
}
void solve(){
scanf("%d%d",&n,&qu);clear();
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++) b[i]=a[i+1]-a[i],sum+=max(b[i],0ll);
st.build(1,1,n-1);itv.insert(mp(-1,-1));itv.insert(mp(n+1,n+1));
int pre=0;
for(int i=1;i<n;i++) if(b[i]>0){
if(pre^(i-1)) insitv(pre+1,i-1);
pre=i;
} if(pre^(n-1)) insitv(pre+1,n-1);
while(qu--){
int opt;scanf("%d",&opt);
if(opt==0){
int l,r,v;scanf("%d%d%d",&l,&r,&v);
if(l^1) chg(l-1,b[l-1]+v);
if(r^n) chg(r,b[r]-v);
} else {
printf("%lld %d
",sum,trp.walk(trp.rt,sum));
}
}
}
int main(){int qu;scanf("%d",&qu);while(qu--) solve();return 0;}