风信子（线段树）

有一个长为 $n$ 的序列 $a$。

定义一个合法二元组 $(i,j)$ 需要满足 $i,j$ 为整数，且 $i\le j$。它的分数为 $a_i?a_j$。

合法二元组 $(i,j)$ 在区间 $[l,r]$ 内，当且仅当 $l\le i,j\le r$。

有 $m$ 次操作：

1 l r x：表示将序列中第 $l$ 个位置到第 $r$ 个位置都加上 $x$。

2 l r k：表示询问选出 $k$ 个不同的合法二元组，每个合法二元组都在区间 $[l,r]$ 内，这些合法二元组的分数和最高是多少。

两个合法二元组 $(i_1,j_1)$ 与 $(i_2,j_2)$ 相同，等价于 $i_1=i_2$ 且 $j_1=j_2$。

$1\le n,m\le 10^5,1\le l\le r\le n,1\le (\sum k)\le 3\times 10^5,?10^6\le a_i,x\le 10^6$

前 $50\%$ 数据：$1\le n,m\le 1000$

另 $15\%$ 数据：$k=1$

---

前置题：[NOI2010] 超级钢琴

$50$ 分做法：对于每次询问都做一遍超级钢琴。

$15$ 分做法：由于 $k=1$，那么可以用线段树维护答案，答案是左右儿子的答案，左儿子最大值减右儿子最小值，这三者的最大值。

注意到超级钢琴使用了 $S(o,l,r)$，表示起点为 $o$，终点范围为 $[l,r]$，答案的最大值，然后分裂成 $S(o,l,x?1),S(o,x+1,r)$ 两个区间。

这显然在此题不够用，于是我们设 $S(l,r,x,y)$ 表示起点 $\in [l,r]$、终点 $\in [x,y]$ 的答案。但是这么做就不好算出答案。

考虑什么样的区间好计算出答案

1. $[l,r]=[x,y]$，就是 $k=1$ 的做法。
2. $[l,r]\cap [x,y]=?$，答案就是左区间最大值减右区间最小值。

下面分析如何把一个合法区间分裂成若干符合条件区间。（注意分出的区间不能有包含关系，不然就会算重）

1. 第一种区间 $[l,r]=[x,y]$（设 $X,Y$ 表示最大答案在下标 $X,Y$ 取得），将其分裂成：

   起点 $\in [l,X?1]$，终点 $\in [l,X?1](X>l)$
   起点 $\in [l,X?1]$，终点 $\in [X,r](X>l)$
   起点 $\in [X,X]$，终点 $\in [X,X](X\ne Y)$
   起点 $\in [X,X]$，终点 $\in [X+1,Y?1](X<Y?1)$
   起点 $\in [X,X]$，终点 $\in [Y+1,r](Y<r)$
   起点 $\in [X+1,r]$，终点 $\in [X+1,r](X<r)$

2. 第二种区间 $[l,r]\cap [x,y]=?$（设 $X,Y$ 表示最大答案在下标 $X,Y$ 取得），将其分裂成：

   起点 $\in [l,X?1]$，终点 $\in [x,y](X>l)$
   起点 $\in [X,X]$，终点 $\in [x,Y?1](x<Y)$
   起点 $\in [X,X]$，终点 $\in [Y+1,y](Y<y)$
   起点 $\in [X+1,r]$，终点 $\in [x,y](X<r)$

分好区间后，直接用优先队列维护即可。

时间复杂度 $O(m\log n+(\sum k)\log (\sum k))$

具体实现参照代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e18;
const int N=1e5+10;
int n,m;
ll a[N];
struct node
{
    ll Max,Min,ans,la,num1,num2;
    pair<ll,ll> num3;
}tr[N<<2];
struct Node
{
    int l,r,x,y;
    ll aa;
    bool operator<(const Node &a)const{
        return aa<a.aa;
    }
};
void pushup(node &rt,node ls,node rs)
{
    rt.num1=ls.Max>rs.Max?ls.num1:rs.num1;
    rt.Max=max(ls.Max,rs.Max);
    rt.num2=ls.Min<rs.Min?ls.num2:rs.num2;
    rt.Min=min(ls.Min,rs.Min);
    ll x=ls.ans,y=rs.ans,z=ls.Max-rs.Min;
    if(x>=max(y,z)) rt.num3=ls.num3;
    else if(y>=max(x,z)) rt.num3=rs.num3;
    else rt.num3=make_pair(ls.num1,rs.num2);
    rt.ans=max({x,y,z});
}
void pushdown(int rt)
{
    tr[rt<<1].Max+=tr[rt].la;
    tr[rt<<1].Min+=tr[rt].la;
    tr[rt<<1].la+=tr[rt].la;
    tr[rt<<1|1].Max+=tr[rt].la;
    tr[rt<<1|1].Min+=tr[rt].la;
    tr[rt<<1|1].la+=tr[rt].la;
    tr[rt].la=0;
}
void build(int rt,int l,int r)
{
    if(l==r){
        tr[rt].Max=tr[rt].Min=a[l];
        tr[rt].num1=tr[rt].num2=l;
        tr[rt].num3=make_pair(l,l);
        return;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(tr[rt],tr[rt<<1],tr[rt<<1|1]);
}
void update(int rt,int l,int r,int x,int y,ll d)
{
    if(r<x||y<l) return;
    if(x<=l&&r<=y){
        tr[rt].Max+=d;
        tr[rt].Min+=d;
        tr[rt].la+=d;
        return;
    }
    int mid=l+r>>1;
    pushdown(rt);
    update(rt<<1,l,mid,x,y,d);
    update(rt<<1|1,mid+1,r,x,y,d);
    pushup(tr[rt],tr[rt<<1],tr[rt<<1|1]);
}
node query(int rt,int l,int r,int x,int y)
{
    if(r<x||y<l) return {-INF,INF,-INF,0,0,0,make_pair(0,0)};
    if(x<=l&&r<=y) return tr[rt];
    int mid=l+r>>1;
    pushdown(rt);
    node aa=query(rt<<1,l,mid,x,y),bb=query(rt<<1|1,mid+1,r,x,y),ans;
    pushup(ans,aa,bb);
    return ans;
}
int main()
{
    // freopen("smart.in","r",stdin);
    // freopen("smart.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=1,op,L,R,num;i<=m;i++){
        cin>>op>>L>>R>>num;
        if(op==1) update(1,1,n,L,R,num);
        else{
            ll ans=0;
            priority_queue<Node> q;
            q.push({L,R,L,R,query(1,1,n,L,R).ans});
            while(num--){
                Node k=q.top();
                q.pop();
                ans+=k.aa;
                if(k.l==k.x&&k.r==k.y){
                    node aa=query(1,1,n,k.l,k.r);
                    int x=aa.num3.first,y=aa.num3.second;
                    if(x>k.l) q.push({k.l,x-1,k.l,x-1,query(1,1,n,k.l,x-1).ans});
                    if(x>k.l) q.push({k.l,x-1,x,k.r,query(1,1,n,k.l,x-1).Max-query(1,1,n,x,k.r).Min});
                    if(x!=y) q.push({x,x,x,x,query(1,1,n,x,x).ans});
                    if(x<y-1) q.push({x,x,x+1,y-1,query(1,1,n,x,x).Max-query(1,1,n,x+1,y-1).Min});
                    if(y<k.r) q.push({x,x,y+1,k.r,query(1,1,n,x,x).Max-query(1,1,n,y+1,k.r).Min});
                    if(x<k.r) q.push({x+1,k.r,x+1,k.r,query(1,1,n,x+1,k.r).ans});
                }
                else{
                    node aa=query(1,1,n,k.l,k.r),bb=query(1,1,n,k.x,k.y);
                    int x=aa.num1,y=bb.num2;
                    if(x>k.l) q.push({k.l,x-1,k.x,k.y,query(1,1,n,k.l,x-1).Max-query(1,1,n,k.x,k.y).Min});
                    if(k.x<y) q.push({x,x,k.x,y-1,query(1,1,n,x,x).Max-query(1,1,n,k.x,y-1).Min});
                    if(y<k.y) q.push({x,x,y+1,k.y,query(1,1,n,x,x).Max-query(1,1,n,y+1,k.y).Min});
                    if(x<k.r) q.push({x+1,k.r,k.x,k.y,query(1,1,n,x+1,k.r).Max-query(1,1,n,k.x,k.y).Min});
                }
            }
            cout<<ans<<"\n";
        }
    }
}