题目链接：http://uoj.ac/problem/232
题目大意：
有n-1年，每年有x[i],y[i]表示繁殖系数和每匹卖出收益，求最大的收益。
思考：
这些马最后都会到同一个地方被卖出。
因为最开始只有一匹马，它到每个地方被卖出都是有一个值的。
∏x[i](i<->j)*y[j]
一匹马会不断繁殖，到j时被卖出。
我们总有一个答案是最大的。
所以我们就可以用线段树来维护这个值。
这里我们维护mx为最大的收益，num为数量
为了方便合并，我们把这两个分别再用(log)进行表示，因为(log)相加就是相乘。
ok！
附上代码：
//每个马在每一个地方都一个价值 找最大的一个地方 // ∏x[i](i->j) * y[j] #include "horses.h" #include<bits/stdc++.h> using namespace std; const int maxn=5e5+12; const int mod=1e9+7; int n,x[maxn],y[maxn]; struct Tree { int mx,num; double val,sum; }tree[maxn<<2]; void pushup(int now) { if(tree[now<<1].val>tree[now<<1].sum+tree[now<<1|1].val) { tree[now].val=tree[now<<1].val; tree[now].mx=tree[now<<1].mx; } else { tree[now].val=tree[now<<1].sum+tree[now<<1|1].val; tree[now].mx=1LL*tree[now<<1].num*tree[now<<1|1].mx%mod; } tree[now].num=1LL*tree[now<<1].num*tree[now<<1|1].num%mod; tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; } void build(int l,int r,int now) { if(l==r) { tree[now].mx=1LL*x[l]*y[l]%mod; tree[now].num=x[l]; tree[now].val=log(1.0*x[l]*y[l]); tree[now].sum=log(1.0*x[l]); return ; } int mid=(l+r)>>1; build(l,mid,now<<1);build(mid+1,r,now<<1|1); pushup(now); } void updata(int L,int l,int r,int now) { if(l==r) { tree[now].mx=1LL*x[l]*y[l]%mod; tree[now].num=x[l]; tree[now].val=log(1.0*x[l]*y[l]); tree[now].sum=log(1.0*x[l]);//log相加就是相乘 return ; } int mid=(l+r)>>1; if(L<=mid) updata(L,l,mid,now<<1); else updata(L,mid+1,r,now<<1|1); pushup(now); } int init(int N, int X[], int Y[]) { n=N; for(int i=1;i<=n;i++) x[i]=X[i-1],y[i]=Y[i-1]; build(1,n,1); return tree[1].mx; } int updateX(int pos, int val) { x[pos+1]=val;updata(pos+1,1,n,1); return tree[1].mx; } int updateY(int pos, int val) { y[pos+1]=val;updata(pos+1,1,n,1); return tree[1].mx; }