题目描述：
题解：
线段树模拟费用流。
想法和种树有点类似。
每次取区间内权值和最大的一段，然后整体乘$-1$，代表再次选中时会去掉之前的影响。
线段树维护一堆东西……
小白逛公园双倍快乐。乘$-1$时交换正反。
[滑稽]
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = ;
template<typename T>
inline void read(T&x)
{
T f = ,c = ;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}
x = f*c;
}
int n,m;
int chg[][];
struct n_8
{
int w,wl,wr,wu,pl,pr,pll,prr;
n_8(){}
n_8(int w,int wl,int wr,int wu,int pl,int pr,int pll,int prr):w(w),wl(wl),wr(wr),wu(wu),pl(pl),pr(pr),pll(pll),prr(prr){}
};
void chkmax(int&a,int&b,int c,int d,int e,int f)
{
if(c>e)a=c,b=d;
else a=e,b=f;
}
void chkmax(int&a,int&b,int&c,int d,int e,int f,int g,int h,int i)
{
if(d>g)a=d,b=e,c=f;
else a=g,b=h,c=i;
}
void chkmin(int&a,int&b,int c,int d,int e,int f)
{
if(c<e)a=c,b=d;
else a=e,b=f;
}
void chkmin(int&a,int&b,int&c,int d,int e,int f,int g,int h,int i)
{
if(d<g)a=d,b=e,c=f;
else a=g,b=h,c=i;
}
void Swap(int&a,int&b)
{
swap(a,b);
a=-a,b=-b;
}
n_8 operator + (n_8 a,n_8 b)
{
n_8 c;
c.w = a.w+b.w;
chkmax(c.wl,c.pll,a.wl,a.pll,a.w+b.wl,b.pll);
chkmax(c.wr,c.prr,b.wr,b.prr,b.w+a.wr,a.prr);
chkmax(c.wu,c.pl,c.pr,a.wu,a.pl,a.pr,b.wu,b.pl,b.pr);
chkmax(c.wu,c.pl,c.pr,c.wu,c.pl,c.pr,a.wr+b.wl,a.prr,b.pll);
return c;
}
struct segtree
{
int w[N<<],wl[N<<],wr[N<<],wu[N<<],pl[N<<],pr[N<<],pll[N<<],prr[N<<];
int _wl[N<<],_wr[N<<],_wu[N<<],_pl[N<<],_pr[N<<],_pll[N<<],_prr[N<<];
bool res[N<<];
void update(int u)
{
w[u] = w[u<<]+w[u<<|];
chkmax(wl[u],pll[u],wl[u<<],pll[u<<],w[u<<]+wl[u<<|],pll[u<<|]);
chkmax(wr[u],prr[u],wr[u<<|],prr[u<<|],w[u<<|]+wr[u<<],prr[u<<]);
chkmin(_wl[u],_pll[u],_wl[u<<],_pll[u<<],w[u<<]+_wl[u<<|],_pll[u<<|]);
chkmin(_wr[u],_prr[u],_wr[u<<|],_prr[u<<|],w[u<<|]+_wr[u<<],_prr[u<<]);
chkmax(wu[u],pl[u],pr[u],wu[u<<],pl[u<<],pr[u<<],wu[u<<|],pl[u<<|],pr[u<<|]);
chkmax(wu[u],pl[u],pr[u],wu[u],pl[u],pr[u],wr[u<<]+wl[u<<|],prr[u<<],pll[u<<|]);
chkmin(_wu[u],_pl[u],_pr[u],_wu[u<<],_pl[u<<],_pr[u<<],_wu[u<<|],_pl[u<<|],_pr[u<<|]);
chkmin(_wu[u],_pl[u],_pr[u],_wu[u],_pl[u],_pr[u],_wr[u<<]+_wl[u<<|],_prr[u<<],_pll[u<<|]);
}
void reser(int u)
{
res[u]^=;
w[u] = -w[u];
Swap(wl[u],_wl[u]);Swap(wr[u],_wr[u]);Swap(wu[u],_wu[u]);
swap(pl[u],_pl[u]);swap(pr[u],_pr[u]);
swap(pll[u],_pll[u]);swap(prr[u],_prr[u]);
}
void pushdown(int u)
{
if(res[u])
{
reser(u<<);
reser(u<<|);
res[u] = ;
}
}
void build(int l,int r,int u)
{
if(l==r)
{
int x;read(x);
w[u] = wu[u] = _wu[u] = wl[u] = _wl[u] = wr[u] = _wr[u] = x;
pl[u]=pr[u]=pll[u]=prr[u]=_pl[u]=_pr[u]=_pll[u]=_prr[u]=l;
return ;
}
int mid = (l+r)>>;
build(l,mid,u<<);
build(mid+,r,u<<|);
update(u);
}
void insert(int l,int r,int u,int qx,int d)
{
if(l==r)
{
w[u] = wu[u] = _wu[u] = wl[u] = _wl[u] = wr[u] = _wr[u] = d;
return ;
}
pushdown(u);
int mid = (l+r)>>;
if(qx<=mid)insert(l,mid,u<<,qx,d);
else insert(mid+,r,u<<|,qx,d);
update(u);
}
void erase(int l,int r,int u,int ql,int qr)
{
if(l==ql&&r==qr)
{
reser(u);
return ;
}
pushdown(u);
int mid = (l+r)>>;
if(qr<=mid)erase(l,mid,u<<,ql,qr);
else if(ql>mid)erase(mid+,r,u<<|,ql,qr);
else erase(l,mid,u<<,ql,mid),erase(mid+,r,u<<|,mid+,qr);
update(u);
}
n_8 query(int l,int r,int u,int ql,int qr)
{
if(l==ql&&r==qr)return n_8(w[u],wl[u],wr[u],wu[u],pl[u],pr[u],pll[u],prr[u]);
pushdown(u);
int mid = (l+r)>>;
if(qr<=mid)return query(l,mid,u<<,ql,qr);
else if(ql>mid)return query(mid+,r,u<<|,ql,qr);
else return query(l,mid,u<<,ql,mid)+query(mid+,r,u<<|,mid+,qr);
}
}tr;
int main()
{
read(n);
tr.build(,n,);
read(m);
int op,x,y,w;
for(int i=;i<=m;i++)
{
read(op),read(x),read(y);
if(!op)tr.insert(,n,,x,y);
else
{
read(w);
n_8 tmp = tr.query(,n,,x,y);
int ans = ;
for(int j=;j<=w;j++)
{
if(tmp.wu>)
{
ans+=tmp.wu;
chg[j][]=tmp.pl,chg[j][]=tmp.pr;
tr.erase(,n,,tmp.pl,tmp.pr);
tmp = tr.query(,n,,x,y);
}else
{
w = j-;
break;
}
}
printf("%d\n",ans);
for(int j=;j<=w;j++)
tr.erase(,n,,chg[j][],chg[j][]);
}
}
return ;
}
压行大法好。