发布时间：2025-05-02

李超线段树

模板

cpp

struct LichaoTree{
	struct Node{
		int l,r,id=0;
	};
	struct Line{
		double k,b;
		double f(double x){
			return k*x+b;
		}
	};
	const double eps=1e-9;
	int cmp(double a,double b){
		if(fabs(a-b)<eps)return 0;
		if(a<b)return -1;
		return 1;
	}
	vector<Node> t;
	vector<Line> line;
	void init(int n){
		t.assign(n<<2,Node());
		line.push_back({0,-INF});
	}
	void build(int p,int l,int r){
		t[p]={l,r,0};
		if(l==r)return;
		int mid=l+r>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
	}
	void modify(int p,int l,int r,int id){
		int mid=t[p].l+t[p].r>>1;
		if(l<=t[p].l&&r>=t[p].r){
			int tid=t[p].id;
			if(cmp(line[id].f(mid),line[t[p].id].f(mid))>0)swap(t[p].id,id);
			else if(cmp(line[id].f(mid),line[t[p].id].f(mid))==0&&t[p].id>id)swap(t[p].id,id);
			if(t[p].l==t[p].r)return;
			if(cmp(line[id].f(l),line[t[p].id].f(l))>=0)modify(p<<1,l,r,id);
			if(cmp(line[id].f(r),line[t[p].id].f(r))>=0)modify(p<<1|1,l,r,id);
			return;
		}
		if(l<=mid)modify(p<<1,l,r,id);
		if(r>mid)modify(p<<1|1,l,r,id);
	}
	pair<double,int> query(int p,int x){
		double res=line[t[p].id].f(x);
		int id=t[p].id;
		if(t[p].l==t[p].r)return {res,id};
		int mid=t[p].l+t[p].r>>1;
		if(x<=mid){
			auto tmp=query(p<<1,x);
			if(cmp(tmp.first,res)>0)res=tmp.first,id=tmp.second;
			else if(cmp(tmp.first,res)==0&&id>tmp.second)id=tmp.second;
		}
		else{
			auto tmp=query(p<<1|1,x);
			if(cmp(tmp.first,res)>0)res=tmp.first,id=tmp.second;
			else if(cmp(tmp.first,res)==0&&id>tmp.second)id=tmp.second;
		}
		return {res,id};
	}
	void add(int x0,int y0,int x1,int y1){
		if(x0>x1)swap(x0,x1),swap(y0,y1);
		double k,b;
		if(x0!=x1){
			k=1.0*(y1-y0)/(x1-x0);
			b=y0-k*x0;
		}
		else{
			k=0;
			b=max(y0,y1);
		}
		line.push_back({k,b});
		modify(1,x0,x1,line.size()-1);
	}
};

P4027 [NOI2007] 货币兑换

小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A 纪念券（以下简称 A 券）和 B 纪念券（以下简称 B 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。

每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 A 券和 B 券的价值分别为 $A_K$ 和 $B_K$ （元/单位金券）。

为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。

比例交易法分为两个方面：

a) 卖出金券：顾客提供一个 $[0, 100]$ 内的实数 $OP$ 作为卖出比例，其意义为：将 $OP\%$ 的 A 券和 $OP\%$ 的 B 券以当时的价值兑换为人民币；

b) 买入金券：顾客支付 $IP$ 元人民币，交易所将会兑换给用户总价值为 $IP$ 的金券，并且，满足提供给顾客的 A 券和 B 券的比例在第 $K$ 天恰好为 $\mathrm{Rate}_ K$ ；

例如，假定接下来 $3$ 天内的 $A_K,B_K,\mathrm{Rate}_ K$ 的变化分别为：

时间	$A_K$	$B_K$	$\mathrm{Rate}_ K$
第一天	$1$	$1$	$1$
第二天	$1$	$2$	$2$
第三天	$2$	$2$	$3$

假定在第一天时，用户手中有 $100$ 元人民币但是没有任何金券。

用户可以执行以下的操作：

时间	用户操作	人民币(元)	A 券的数量	B 券的数量
开户	无	$100$	$0$	$0$
第一天	买入 $100$ 元	$0$	$50$	$50$
第二天	卖出 $50\%$	$75$	$25$	$25$
第二天	买入 $60$ 元	$15$	$55$	$40$
第三天	卖出 $100\%$	$205$	$0$	$0$

注意到，同一天内可以进行多次操作。

小 Y 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 $N$ 天内的 A 券和 B 券的价值以及 $\mathrm{Rate}$ 。他还希望能够计算出来，如果开始时拥有 $S$ 元钱，那么 $N$ 天后最多能够获得多少元钱。

思路：

trick:肯定是全部买进再全部卖出
假设 $f_i$ 为那天最大的钱数
那么可以求得买进的A,B为 $x_i=\frac{f_iRate_i}{a_iRate_i+b_i},y_i=\frac{f_i}{a_iRate_i+b_i}$
对于第 $i$ 天不卖，则为 $f_i=f_{i-1}$
否则， $f_i=max a_ix_j+b_iy_j,f_i=b_i max x_j \frac{a_i}{b_i}+y_j$
后面是一个直线
可以李超线段树，因为查询的 $x$ 是实数，因此需要离散化

cpp

const double eps=1e-9;
int cmp(double a,double b){
    if(fabs(a-b)<eps)return 0;
    if(a<b)return -1;
    return 1;
}
vector<double> c;
   
struct LichaoTree{
	struct Line{
        double k,b;
		double f(double x){
            return k*c[x]+b;
		}
	};
	vector<int> t;
	vector<Line> line;
    int n;
	void init(int n){
        t.assign(n+1<<2,0);
		line.push_back({0,-INF});
        this->n=n;
    }
	void modify(int p,int l,int r,int ql,int qr,int id){
        int mid=l+r>>1;
		if(ql<=l&&qr>=r){
			if(cmp(line[id].f(mid),line[t[p]].f(mid))>0)swap(t[p],id);
			if(l==r)return;
			if(cmp(line[id].f(l),line[t[p]].f(l))>=0)modify(p<<1,l,mid,ql,qr,id);
			if(cmp(line[id].f(r),line[t[p]].f(r))>=0)modify(p<<1|1,mid+1,r,ql,qr,id);
			return;
		}
		if(ql<=mid)modify(p<<1,l,mid,ql,qr,id);
		if(qr>mid)modify(p<<1|1,l,mid,ql,qr,id);
	}
	double query(int p,int l,int r,int x){
        double res=line[t[p]].f(x);
		int id=t[p];
		if(l==r)return res;
		int mid=l+r>>1;
        auto tmp=x<=mid?query(p<<1,l,mid,x):query(p<<1|1,mid+1,r,x);
        if(cmp(tmp,res)>0)res=tmp;
		return res;
	}
    double query(int x){
        return query(1,1,n,x);
    }
    void add(double k,double b){
        line.push_back({k,b});
        modify(1,1,n,1,n,line.size()-1);
    }
} t;
void solve(){
    int n;
    double s;
    cin>>n>>s;
    vector<double> a(n+1),b(n+1),rate(n+1);
    c=vector<double>(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>rate[i];
        c[i]=a[i]/b[i];
    }
    sort(c.begin()+1,c.end());
    t.init(n);
    vector<double> f(n+1);
    f[0]=s;
    cout<<fixed<<setprecision(3);
    for(int i=1;i<=n;i++){
        f[i]=f[i-1];
        auto j=lower_bound(c.begin()+1,c.end(),a[i]/b[i])-c.begin();
        double tmp=t.query(j)*b[i];
        if(cmp(tmp,f[i])>0)f[i]=tmp;
        double x=f[i]*rate[i]/(a[i]*rate[i]+b[i]),y=f[i]/(a[i]*rate[i]+b[i]);
        t.add(x,y);
    }
    cout<<f[n]<<"\n";
}

优化

斜率优化插入的一般为一条直线，因此插入直线可以优化成 $\log n$

cpp

struct LichaoTree{
	struct Line{
        double k,b;
		double f(double x){
            return k*c[x]+b;
		}
	};
	vector<int> t;
	vector<Line> line;
    int n;
	void init(int n){
        t.assign(n+1<<2,0);
		line.push_back({0,-INF});
        this->n=n;
    }
	void modify(int p,int l,int r,int id){
        int mid=l+r>>1;
        if(line[id].f(mid)>line[t[p]].f(mid))swap(t[p],id);
        if(l==r)return;
        line[id].f(l)>line[t[p]].f(l)?modify(p<<1,l,mid,id):modify(p<<1|1,mid+1,r,id);
	}
	double query(int p,int l,int r,int x){
        double res=line[t[p]].f(x);
		if(l==r)return res;
		int mid=l+r>>1;
        auto tmp=x<=mid?query(p<<1,l,mid,x):query(p<<1|1,mid+1,r,x);
		return max(res,tmp);
	}
    double query(int x){
        return query(1,1,n,x);
    }
    void add(double k,double b){
        line.push_back({k,b});
        modify(1,1,n,line.size()-1);
    }
} t;
void solve(){
    int n;
    double s;
    cin>>n>>s;
    vector<double> a(n+1),b(n+1),rate(n+1);
    c=vector<double>(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>rate[i];
        c[i]=a[i]/b[i];
    }
    sort(c.begin()+1,c.end());
    t.init(n);
    vector<double> f(n+1);
    f[0]=s;
    cout<<fixed<<setprecision(3);
    for(int i=1;i<=n;i++){
        f[i]=f[i-1];
        auto j=lower_bound(c.begin()+1,c.end(),a[i]/b[i])-c.begin();
        double tmp=t.query(j)*b[i];
        if(cmp(tmp,f[i])>0)f[i]=tmp;
        double x=f[i]*rate[i]/(a[i]*rate[i]+b[i]),y=f[i]/(a[i]*rate[i]+b[i]);
        t.add(x,y);
    }
    cout<<f[n]<<"\n";
}

李超线段树 ​

模板 ​

P4027 [NOI2007] 货币兑换 ​

优化 ​

李超线段树

模板

P4027 [NOI2007] 货币兑换

优化