前言
前置trick:超级钢琴
打模拟赛遇上这个，如果知道trick，很容易往超级钢琴上想，但又有不同之处，遂爆零。
为了纪念第一次自己改出T4，于是作此篇报告。
题目描述
定义一个合法二元组 \((i,j)\) 需要满足 \(i\),\(j\) 为整数，且 \(i≤j\)。如果 \(i>j\)，则 \((i,j)\)不构成合法二元组。
定义一个合法二元组 (i,j)(i,j) 的分数为 \(a_i-a_j\)。
定义一个合法二元组 \((i,j)\) 在区间 \([l,r]\) 内，当且仅当 \(l≤i,j≤r\)。
有 \(m\) 次操作：
1 l r x：表示将序列中第 \(l\) 个位置到第 \(r\) 个位置都加上 \(x\)。
2 l r k：表示询问选出 \(k\) 个不同的合法二元组，每个合法二元组都在区间 \([l,r]\)内，这些合法二元组的分数和最高是多少。
关联与区别
超级钢琴的 trick 就是用堆来维护可选答案集合，对于每个堆顶还可以再分成范围更小的答案集合，取出\(k\)次堆顶就可以求出答案。
与之类似的还有可持久化0/1trie的一道题：异或粽子
回到这题，我们会发现这道题带修，这好说，用线段树来维护，只不过将查询复杂度由之前st表的\(O(1)\)变为\(O(logn)\)(无妨，这题数据范围小一点，给的时限也长)。
除此之外，在超级钢琴中我们固定一个端点，另一端为一个区间，但在这题，左右端点都在一个区间里，这个处理起来便会有些复杂。
对答案集合的操作
因为两端都是区间的原因，所以我们要找到一个可以便捷求答案的左右区间，分别是：（设左端点可选区间为\([l_1,r_1]\),右端点可选区间为\([l_2,r_2]\)）
- \(l_1=l_2\),\(r_1=r_2\) : 就是求区间最大差值（用线段树维护）
- \(r_1<l_2\) : 就是两区间无交集，答案为左区间最大值减去右区间最小值，还可以用线段树维护
由上，我们在将大的答案集合分成若干小的答案集合，也应分成上面这两种，最开始的区间满足第一种情况，接下来的“分裂”应是这样：
设当前左端点的可选区间为\([l_1,r_1]\),右端点可选区间为\([l_2,r_2]\),最优答案的左端点为\(x\),右端点为\(y\)(线段树上维护，根据上面的方法可以很好求出来),当然因为第一种情况下\(l_1=l_2,r_1=r_2\)，这里不再区分。
对于第一种情况(同一区间)
下一次最优答案的左右端点可能在下面这几种情况：
左右端点均在\([l,x-1]\)内，可选条件：\(x>l\)
左端点在\([l,x-1]\)，右端点在\([x,r]\)内，可选条件：\(x>l\)
左端点不动，右端点也在左端点处，可选条件：\(x\neq y\)
左端点不动，右端点在\([x+1,y-1]\)内，可选条件：\(x<y-1\)
左端点不动，右端点在\([y+1,r]\)内，可选条件：\(y<r\)
左右端点均在\([x+1,r]\)处，可选条件：\(x<r\)
观察发现，我们其实是在对左端点进行分类讨论，随着左端点可选区间的右移，右端点可选区间也在变化。
对于第二种情况（无交区间）
还是讨论下一次最优答案的可选区间，以左端点为标准。
左端点在\([l_1,x-1]\),右端点在\([l_2,r_2]\),可选条件：\(x>l_1\)
左端点不动，右端在\([l_2,y-1]\)内，可选条件：\(l_2<y\)
左端点不动，右端点在\([y+1,r_2]\)内，可选条件：\(y<r_2\)
左端点在\([x+1,r_1]\),右端点在\([l_2,r_2]\),可选条件：\(x<r1\)
至此关键步骤已经解决，接下来难点在于线段树维护
线段树要干啥
综合上述，不难发现，答案查询以及带修操作均需要线段树，因此线段树要维护这些：
pair<int,int> max//最大值以及他的位置
pair<int,int> min//最小值以及他的位置
int val//区间最大差值
int x,y//区间最大差值的左右端点
int tag//区修懒标记
对应的\(pushup\)与\(query\)皆要变化，可以通过代码理解。
代码（写的有点长）
点击查看代码
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<tuple>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int maxn=1e5+5;
#define int long long
int n,m,a[maxn];
struct nd
{int l,r,tag;pair<int,int> ma,mi;int val;int val_L,val_R;
}v[maxn<<2];
void pushup(int rt)
{v[rt].ma=max(v[lson].ma,v[rson].ma);v[rt].mi=min(v[lson].mi,v[rson].mi);if(v[lson].val>=v[rson].val&&v[lson].val>=v[lson].ma.first-v[rson].mi.first){v[rt].val=v[lson].val;v[rt].val_L=v[lson].val_L;v[rt].val_R=v[lson].val_R;}else if(v[rson].val>=v[lson].val&&v[rson].val>=v[lson].ma.first-v[rson].mi.first){v[rt].val=v[rson].val;v[rt].val_L=v[rson].val_L;v[rt].val_R=v[rson].val_R;}else{v[rt].val=v[lson].ma.first-v[rson].mi.first;v[rt].val_L=v[lson].ma.second;v[rt].val_R=v[rson].mi.second;}
}
void pushdown(int rt)
{if(v[rt].tag==0) return;v[lson].ma.first+=v[rt].tag;v[lson].mi.first+=v[rt].tag;v[rson].ma.first+=v[rt].tag;v[rson].mi.first+=v[rt].tag;v[lson].tag+=v[rt].tag;v[rson].tag+=v[rt].tag;v[rt].tag=0;
}
void build(int rt,int l,int r)
{v[rt].l=l,v[rt].r=r;if(l==r){v[rt].ma={a[l],l};v[rt].mi={a[l],l};v[rt].val_L=v[rt].val_R=l;v[rt].val=0;return;}int mid=(l+r)>>1;build(lson,l,mid);build(rson,mid+1,r);pushup(rt);
}
void update(int rt,int L,int R,int val)
{if(v[rt].l>=L&&v[rt].r<=R){v[rt].ma.first+=val;v[rt].mi.first+=val;v[rt].tag+=val;return;}pushdown(rt);int mid=(v[rt].l+v[rt].r)>>1;if(L<=mid) update(lson,L,R,val);if(R>mid) update(rson,L,R,val);pushup(rt);
}
nd query(int rt,int L,int R)
{if(v[rt].l>=L&&v[rt].r<=R) return v[rt];pushdown(rt);int mid=(v[rt].l+v[rt].r)>>1;if(R<=mid) return query(lson,L,R);else if(L>mid) return query(rson,L,R);else{nd v1=query(lson,L,R),v2=query(rson,L,R);nd ret={};ret.ma=max(v1.ma,v2.ma);ret.mi=min(v1.mi,v2.mi);if(v1.val>=v2.val&&v1.val>=v1.ma.first-v2.mi.first){ret.val=v1.val;ret.val_L=v1.val_L;ret.val_R=v1.val_R;}else if(v2.val>=v1.val&&v2.val>=v1.ma.first-v2.mi.first){ret.val=v2.val;ret.val_L=v2.val_L;ret.val_R=v2.val_R;}else{ret.val=v1.ma.first-v2.mi.first;ret.val_L=v1.ma.second;ret.val_R=v2.mi.second;}return ret;}
}
struct zz
{int l1,r1,l2,r2,val,pos_x,pos_y;bool operator <(const zz &vv) const{return val<vv.val;}
};
priority_queue<zz> q;
int solve(int l,int r,int k)
{int ret=0;while(!q.empty()) q.pop();nd op=query(1,l,r);q.push({l,r,l,r,op.val,op.val_L,op.val_R});while(k&&!q.empty()){zz gh=q.top();q.pop();ret+=gh.val;k--;if(gh.l1==gh.l2&&gh.r1==gh.r2){if(gh.pos_x>gh.l1){nd df=query(1,gh.l1,gh.pos_x-1);q.push({gh.l1,gh.pos_x-1,gh.l1,gh.pos_x-1,df.val,df.val_L,df.val_R});nd jk=query(1,gh.pos_x,gh.r1);q.push({gh.l1,gh.pos_x-1,gh.pos_x,gh.r1,df.ma.first-jk.mi.first,df.ma.second,jk.mi.second});}if(gh.pos_x!=gh.pos_y){q.push({gh.pos_x,gh.pos_x,gh.pos_x,gh.pos_x,0,gh.pos_x,gh.pos_x});}if(gh.pos_x<gh.pos_y-1){nd df=query(1,gh.pos_x,gh.pos_x);nd jk=query(1,gh.pos_x+1,gh.pos_y-1);q.push({gh.pos_x,gh.pos_x,gh.pos_x+1,gh.pos_y-1,df.ma.first-jk.mi.first,df.ma.second,jk.mi.second});}if(gh.pos_y<gh.r1){nd df=query(1,gh.pos_x,gh.pos_x);nd jk=query(1,gh.pos_y+1,gh.r1);q.push({gh.pos_x,gh.pos_x,gh.pos_y+1,gh.r1,df.ma.first-jk.mi.first,df.ma.second,jk.mi.second});}if(gh.pos_x<gh.r1){nd df=query(1,gh.pos_x+1,gh.r1);q.push({gh.pos_x+1,gh.r1,gh.pos_x+1,gh.r1,df.val,df.val_L,df.val_R});}}else if(gh.r1<gh.l2){if(gh.pos_x>gh.l1){nd df=query(1,gh.l1,gh.pos_x-1);nd jk=query(1,gh.l2,gh.r2);q.push({gh.l1,gh.pos_x-1,gh.l2,gh.r2,df.ma.first-jk.mi.first,df.ma.second,jk.mi.second});}if(gh.l2<gh.pos_y){nd df=query(1,gh.pos_x,gh.pos_x);nd jk=query(1,gh.l2,gh.pos_y-1);q.push({gh.pos_x,gh.pos_x,gh.l2,gh.pos_y-1,df.ma.first-jk.mi.first,df.ma.second,jk.mi.second});}if(gh.pos_y<gh.r2){nd df=query(1,gh.pos_x,gh.pos_x);nd jk=query(1,gh.pos_y+1,gh.r2);q.push({gh.pos_x,gh.pos_x,gh.pos_y+1,gh.r2,df.ma.first-jk.mi.first,df.ma.second,jk.mi.second});}if(gh.pos_x<gh.r1){nd df=query(1,gh.pos_x+1,gh.r1);nd jk=query(1,gh.l2,gh.r2);q.push({gh.pos_x+1,gh.r1,gh.l2,gh.r2,df.ma.first-jk.mi.first,df.ma.second,jk.mi.second});}}else cout<<"666 ";//调试 }return ret;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);freopen("D.in","r",stdin);freopen("D.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);for(int i=1,op,l,r,k;i<=m;i++){cin>>op>>l>>r>>k;if(op==1) update(1,l,r,k);else cout<<solve(l,r,k)<<'\n';}return 0;
}