CF1842E Tenzing and Triangle - 线段树优化 dp -

题目链接：https://codeforces.com/contest/1842/problem/E

题解：
首先，如果两个等腰三角形相交了，那答案肯定不会更优。因此不会相交。
先考虑一个 \(n^2\) 的 dp：
设 \(dp_i\) 表示考虑到 \(x=i\) 时的最小代价，首先可以先都加一个 \(\sum c_i\)，这样只需要考虑三角形覆盖范围内的 \(c_i\) 减去即可。
\(dp_i \leftarrow dp_j - cost(j+1,i) + A\times (i-j)\)，其中 \(cost(j+1,i)\) 表示这两个坐标所确定的等腰直角三角形内部的 \(c_i\) 之和，减是因为最后要加一个 \(\sum c_i\)
转移的时候，可以每次更新一下 \(j\) 的 \(cost\)

如何优化？首先，为了方便，令 \(y := k-y\)，具体是将后缀和转化为前缀和，详细见后。这样，覆盖所需要的等腰三角形就变成了

修改一下 dp 的定义：令 \(dp_i\) 表示考虑覆盖到 \(y=i\) 时的最小代价
考虑一下一个点 \((x,i)\) 会对哪些 dp 值产生贡献？显然是 \(1..x\)（也就是说，当 \(i\) 由 \(1..x\) 转移过来时，\(cost\) 都要加上 \((x,i)\) 点的贡献）
理解的话可以回到 \(y\) 的含义没有变的时候
这就是一个前缀加。利用线段树维护一下 \(dp_i-i\times A\)，然后就是前缀和，区间 min。注意线段树下标要从 0 开始。
最后加上 \(\sum c_i\) 即可

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

int n,k,coef;
vector<pii>p[maxn];
ll f[maxn];

struct segm{
	ll mn,lazy;
}se[maxn << 2];

void build(int l,int r,int num){
	se[num].mn = 1e18;
	se[num].lazy = 0;
	if(l == r){
		return ; 
	}
	int mid=l+r>>1;
	build(l,mid,num << 1);build(mid+1,r,num<<1|1);
}

void pushdown(int num,int l,int r){
	if(!se[num].lazy)return ;
	int mid=r-l+1;
	ll lz = se[num].lazy;
	se[num << 1].mn += lz, se[num << 1|1].mn += lz;
	se[num << 1].lazy += lz, se[num << 1|1].lazy += lz;
	se[num].lazy = 0;
}

void update(int l,int r,int x,ll to,int num){
	if(r <= x){
		se[num].mn += to;
		se[num].lazy += to;
		return ;
	}
	pushdown(num,l,r);
	int mid = l+r>>1;
	if(x <= mid)update(l,mid,x,to,num << 1);
	else update(l,mid,x,to,num << 1), update(mid+1,r,x,to,num << 1|1);
	se[num].mn = min(se[num << 1].mn, se[num << 1|1].mn);
}

void upd(int l,int r,int x,ll to,int num){
	if(l == r){
		se[num].mn = to;
		return ;
	}
	pushdown(num,l,r);
	int mid = l+r>>1;
	if(x <= mid)upd(l,mid,x,to,num << 1);
	else upd(mid+1,r,x,to,num << 1|1);
	se[num].mn = min(se[num << 1].mn, se[num << 1|1].mn);
}

ll query(int l,int r,int x,int y,int num){
	if(x <=l && r<=y)return se[num].mn;
	int mid = l+r>>1;
	pushdown(num,l,r);
	if(y<=mid)return query(l,mid,x,y,num<<1);
	else if(x>mid)return query(mid+1,r,x,y,num<<1|1);
	else return min(query(l,mid,x,y,num<<1),query(mid+1,r,x,y,num<<1|1));
}

signed main(){
	scanf("%d%d%d",&n,&k,&coef);
	ll bs = 0;
	for(int i=1;i<=n;i++){
		int x,y,c;scanf("%d%d%d",&x,&y,&c);
		y = k-y;
		p[y].pb(mpr(x, c));
		bs += c;
	}
	build(0,k,1);
	upd(0,k,0,0,1);
	for(int i=1;i<=k;i++){
		for(auto it : p[i]){
			int y = it.first;
			ll c = it.second;
			update(0,k,y,-c,1);
		}
		f[i] = min(query(0,k,0,i-1,1) + 1ll*i*coef, f[i-1]);
		upd(0,k,i,f[i]-1ll*i*coef,1);
	}
	printf("%lld\n",f[k] + bs);

	return 0;
}