Good Inflation SPOJ - GOODG 李超树

题目传送门

题意：刚开始有一个气球体积为空，现在有n个充气点，从1->n遍历这n充气点，每个充气点有vi，di，vi为走到这个充气点之后可以为气球充气vi的体积，di为选择了在这个点充气的时候，每次往后走气球会漏di的气体。

题解：李超线段树裸题。

李超树主要是维护优势线段。

每一个节点存一条线段的信息。

每次更新的时候，如果新的线段完全在原来的下方，直接return，

如果新的线段在原来的直线的上方，这存下新的线段。

否者就是有交点，我们继续往下走，更新一下下面的线段。

注意的就是，每个节点只存一条线段的内容，有2条线段出现在[l,r]这个节点中的时候，我们存下优势长的那一条信息。

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define lch(x) tr[x].son[0]

 #define rch(x) tr[x].son[1]

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 1e6 + ;

 LL treeb[N<<],treek[N<<];

 bool vis[N<<];

 double Intersection(double k1,double b1,double k2,double b2){return 1.0*(b2-b1)/(k1-k2);}

 void update(LL k,LL b,int l,int r,int rt){

     if(!vis[rt]) {

         treek[rt] = k;

         treeb[rt] = b;

         vis[rt] = ;

         return;

     }

     LL l1 = k * l + b, l2 = treek[rt] * l + treeb[rt];

     LL r1 = k * r + b, r2 = treek[rt] * r + treeb[rt];

     if(l1 <= l2 && r1 <= r2) return ;

     if(l1 >= l2 && r1 >= r2) treek[rt] = k, treeb[rt] = b;

     else{

         int m = l + r >> ;

         double crs = Intersection(k, b, treek[rt], treeb[rt]);

         if(l1 >= l2){

             if(crs <= m) update(k,b,lson);

             else{

                 update(treek[rt], treeb[rt], rson);

                 treek[rt] = k; treeb[rt] = b;

             }

         }

         else{

             if(crs > m) update(k, b, rson);

             else{

                 update(treek[rt], treeb[rt], lson);

                 treek[rt] = k; treeb[rt] = b;

             }

         }

     }

 }

 LL query(int x,int l,int r,int rt){

     LL ans=;

     if(vis[rt]) ans=max(ans, x*treek[rt]+treeb[rt]);

     if(l == r) return ans;

     int m = l+r >> ;

     if(m >= x) ans = max(ans, query(x, lson));

     else ans = max(ans, query(x, rson));

     return ans;

 }

 int v[N], d[N];

 int main(){

     int n;

     scanf("%d", &n);

     for(int i = ; i <= n; i++)

         scanf("%d%d", &v[i], &d[i]);

     update(-d[],v[]+d[],,n+,);

     for(int i = ; i <= n; i++){

         LL zz = query(i,,n+,) + v[i];

         update(-d[i],zz+1ll*d[i]*i,,n+,);

     }

     LL ans = query(n+,,n,);

     if(ans < ) ans = ;

     cout << ans << endl;

     return ;

 }

巴特西

Good Inflation SPOJ - GOODG 李超树

最新文章

热门文章