CDQ 维护斜率优化DP

Building Bridges

code:

#include
#include
#include
using namespace std;
#define int long long
const int MAXN=2e5+5;
int n,h[MAXN],w[MAXN],dp[MAXN],s[MAXN],q[MAXN];
int POW(int x){return x*x;
}
struct ren{
	int id,x,y,k;
}a[MAXN],t[MAXN];
bool cmp(ren x,ren y){return x.k>1;
	int t1=l,t2=mid+1;
	for(int i=l;i<=r;i++){
		if(a[i].id<=mid) t[t1++]=a[i];
		else t[t2++]=a[i];
	}
	for(int i=l;i<=r;i++) a[i]=t[i];
	cdq(l,mid);
	int he=1,ti=0;
	for(int i=l;i<=mid;i++){
		if(i!=l&&a[i].x==a[i-1].x) continue;
		while(he