求优化常数

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=(int)4e18+10;
const int N=1e5+10;
struct mt{
	int n,m;
	int s[4][4];
};
const mt ps={1,4,{0,0,0,0}};
const mt bs={4,4,{
	{0,-inf,-inf,-inf},
	{-inf,0,-inf,-inf},
	{-inf,-inf,0,-inf},
	{-inf,-inf,-inf,0},
}};
mt operator*(const mt &a,const mt &b){
	mt res=mt();
	memset(res.s,-0x3f,sizeof(res.s));
	int n=a.n;
	int k=a.m;
	int m=b.m;
	res.n=n;
	res.m=m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			for(int l=0;l<k;l++){
				res.s[i][j]=max(res.s[i][j],a.s[i][l]+b.s[l][j]);
			}
		}
	}
	return res;
}
mt qp(mt x,int y){
	mt res=bs;
	while(y){
		if(y&1) res=res*x;
		x=x*x;
		y>>=1;
	}
	return res;
}
struct treap{
	struct ms{
		int ls,rs,pr;
		int val,sum;
		mt r,t,s;
	}f[N*3];
	int rt,cnt;
	int nw(mt a,int val){
		int u=++cnt;
		f[u].pr=rand();
		f[u].val=f[u].sum=val;
		f[u].r=a;
		f[u].t=f[u].s=qp(a,val);
		return u;
	}
	void push_up(int u){
		int ls=f[u].ls,rs=f[u].rs;
		f[u].sum=f[ls].sum+f[u].val+f[rs].sum;
		f[u].s=(ls?f[ls].s:bs)*(f[u].t)*(rs?f[rs].s:bs);
	}
	tuple<int,int,int> sp(int u,int k){
		if(!u) return {0,0,0};
		if(k<=f[f[u].ls].sum){
			auto [x,y,z]=sp(f[u].ls,k);
			f[u].ls=z;
			push_up(u);
			return {x,y,u};
		}
		else if(k<f[f[u].ls].sum+f[u].val){
			int ls=f[u].ls,rs=f[u].rs;
			f[u].ls=f[u].rs=0;
			push_up(u);
			return {ls,u,rs};
		}
		else{
			auto [x,y,z]=sp(f[u].rs,k-f[f[u].ls].sum-f[u].val);
			f[u].rs=x;
			push_up(u);
			return {u,y,z};
		}
	}
	int mer(int x,int y){
		if(!x) return y;
		if(!y) return x;
		if(f[x].pr<f[y].pr){
			f[y].ls=mer(x,f[y].ls);
			push_up(y);
			return y;
		}
		else{
			f[x].rs=mer(f[x].rs,y);
			push_up(x);
			return x;
		}
	}
	void ins(int pos,mt a,int val){
		auto [x,y,z]=sp(rt,pos);
		int m=nw(a,val);
		if(!y){
			rt=mer(x,mer(m,z));
			return;
		}
		mt rec=f[y].r;
		int c=pos-f[x].sum;
		int p1=nw(rec,c);
		int p2=nw(rec,f[y].val-c);
		rt=mer(x,mer(p1,mer(m,mer(p2,z))));
	}
	int que(){
		mt res=ps*f[rt].s;
		int ans=0;
		for(int i=0;i<4;i++){
			ans=max(ans,res.s[0][i]);
		}
		return ans;
	}
}t;
int n;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	int las=0;
	for(int i=1;i<=n;i++){
		int p,a,b,c,x;
		cin>>p>>a>>b>>c>>x;
		mt w={4,4,{
			{a,b,c,a},
			{-inf,b,c,a},
			{-inf,-inf,c,a},
			{-inf,-inf,-inf,a},
		}};
		t.ins(p,w,x);
		int res=t.que();
		cout<<res-las<<"\n";
		las=res;
	}
}