Codeforces 1787H - Codeforces Scoreboard（平衡树优化 dp）

令 \(c_i=b_i-a_i\)，等价于我们钦定一个排列 \(p\)，最小化 \(\sum \min(p_ik_i,c_i)\)，拿 \(\sum b_i\) 减去之就是答案。

我们钦定一些 \(i\) 满足 \(p_ik_i<c_i\)，根据排序不等式，这些 \(p_i\) 肯定按 \(k\) 从大到小的顺序依次填入 \(1,2,3,\cdots\)。这样就可以 DP 了：将 \(k\) 从大到小排序，然后设 \(dp_{i,j}\) 表示考虑前 \(i\) 道题，钦定了 \(j\) 道的最小代价，有 \(dp_{i,j}=\min(dp_{i-1,j-1}+jk_i,dp_{i-1,j}+c_i)\)。最终答案为 \(\sum b_i-\min dp_{n,i}\)。

考虑优化，记 \(g_{i,j}=f_{i,j}-f_{i,j-1}(1\le j\le i)\)，那么 \(f_{i,0}+\sum\limits_{t=1}^jg_{i,t}=\min(f_{i-1,0}+\sum\limits_{t=1}^{j-1}dp_{i-1,t}+jk_i,f_{i-1,0}+\sum\limits_{t=1}^jdp_{i-1,t}+c_i)\)。考虑前者比后者更小的充要条件——相当于 \(jk_i<g_{i-1,j}+c_i\)，令 \(h_{i,j}=g_{i-1,j}-jk_i+c_i\)，发现 \(h_{i,j}\) 是先负后正的，这是因为 \(k\) 单调不增，导致 \(g_{i-1,j}\) 增长速度比 \(jk_i\) 快。也就是说，对于一段前缀，采用第二种转移，对于一段后缀，采取第一转移，二分找到分界点之后相当于一段后缀加一个数，中间再插入一个数。使用平衡树维护即可。

const int MAXN=2e5;
const ll INF=1e18;
mt19937 rng(114514);
int n;
struct dat{
	int a,b,c,k;
	friend bool operator <(const dat &X,const dat &Y){return X.k>Y.k;}
}a[MAXN+5];
struct node{int ch[2],siz,key;ll val,lz;}s[MAXN+5];
int ncnt,rt;
void pushup(int k){s[k].siz=s[s[k].ch[0]].siz+s[s[k].ch[1]].siz+1;}
int nwnd(ll v){++ncnt;s[ncnt].siz=1;s[ncnt].key=rng();s[ncnt].val=v;return ncnt;}
void tag(int k,int v){if(k)s[k].lz+=v,s[k].val+=v;}
void pushdown(int k){if(s[k].lz)tag(s[k].ch[0],s[k].lz),tag(s[k].ch[1],s[k].lz),s[k].lz=0;}
void split(int k,int K,int C,int sz,int &a,int &b){
	if(!k)return a=b=0,void();pushdown(k);
	if(s[k].val-1ll*(sz+s[s[k].ch[0]].siz+1)*K+C>=0)b=k,split(s[k].ch[0],K,C,sz,a,s[k].ch[0]),pushup(k);
	else a=k,split(s[k].ch[1],K,C,sz+s[s[k].ch[0]].siz+1,s[k].ch[1],b),pushup(k);
}
int merge(int a,int b){
	if(!a||!b)return a+b;pushdown(a);pushdown(b);
	if(s[a].key<s[b].key)return s[a].ch[1]=merge(s[a].ch[1],b),pushup(a),a;
	else return s[b].ch[0]=merge(a,s[b].ch[0]),pushup(b),b;
}
ll cur,mn;
void dfs(int k){
	if(!k)return;pushdown(k);dfs(s[k].ch[0]);
	cur+=s[k].val;chkmin(mn,cur);dfs(s[k].ch[1]);
}
void solve(){
	scanf("%d",&n);ll sumb=0;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&a[i].k,&a[i].b,&a[i].a);
		a[i].c=a[i].b-a[i].a;sumb+=a[i].b;
	}
	sort(a+1,a+n+1);
//	for(int i=1;i<=n;i++)printf("! %d %d\n",a[i].k,a[i].c);
	for(int i=0;i<=ncnt;i++)s[i].ch[0]=s[i].ch[1]=s[i].siz=s[i].key=s[i].val=s[i].lz=0;
	ncnt=rt=0;ll f0=0;
	for(int i=1;i<=n;i++){
		int k1,k2;split(rt,a[i].k,a[i].c,0,k1,k2);tag(k2,a[i].k);
		rt=merge(merge(k1,nwnd(1ll*(s[k1].siz+1)*a[i].k-a[i].c)),k2);
		f0+=a[i].c;
	}cur=f0;mn=f0;dfs(rt);
	printf("%lld\n",sumb-mn);
}
int main(){
	int qu;scanf("%d",&qu);
	while(qu--)solve();
	return 0;
}
/*
1
6
1 8 1
9 29 4
2 14 3
4 13 1
2 19 5
10 12 5
*/