当前位置：首页 > news >正文

Good Inflation SPOJ - GOODG 李超树

news 来源：原创 2024/5/3 23:54:15

题目传送门

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

题解：李超线段树裸题。

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

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

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

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

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

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
 4 #define LL long long
 5 #define ULL unsigned LL
 6 #define fi first
 7 #define se second
 8 #define pb push_back
 9 #define lson l,m,rt<<1
10 #define rson m+1,r,rt<<1|1
11 #define lch(x) tr[x].son[0]
12 #define rch(x) tr[x].son[1]
13 #define max3(a,b,c) max(a,max(b,c))
14 #define min3(a,b,c) min(a,min(b,c))
15 typedef pair<int,int> pll;
16 const int inf = 0x3f3f3f3f;
17 const LL INF = 0x3f3f3f3f3f3f3f3f;
18 const LL mod =  (int)1e9+7;
19 const int N = 1e6 + 100;
20 LL treeb[N<<2],treek[N<<2];
21 bool vis[N<<2];
22 double Intersection(double k1,double b1,double k2,double b2){return 1.0*(b2-b1)/(k1-k2);}
23 void update(LL k,LL b,int l,int r,int rt){
24     if(!vis[rt]) {
25         treek[rt] = k;
26         treeb[rt] = b;
27         vis[rt] = 1;
28         return;
29     }
30     LL l1 = k * l + b, l2 = treek[rt] * l + treeb[rt];
31     LL r1 = k * r + b, r2 = treek[rt] * r + treeb[rt];
32     if(l1 <= l2 && r1 <= r2) return ;
33     if(l1 >= l2 && r1 >= r2) treek[rt] = k, treeb[rt] = b;
34     else{
35         int m = l + r >> 1;
36         double crs = Intersection(k, b, treek[rt], treeb[rt]);
37         if(l1 >= l2){
38             if(crs <= m) update(k,b,lson);
39             else{
40                 update(treek[rt], treeb[rt], rson);
41                 treek[rt] = k; treeb[rt] = b;
42             }
43         }
44         else{
45             if(crs > m) update(k, b, rson);
46             else{
47                 update(treek[rt], treeb[rt], lson);
48                 treek[rt] = k; treeb[rt] = b;
49             }
50         }
51     }
52 }
53 
54 
55 
56 
57 LL query(int x,int l,int r,int rt){
58     LL ans=0;
59     if(vis[rt]) ans=max(ans, x*treek[rt]+treeb[rt]);
60     if(l == r) return ans;
61     int m = l+r >> 1;
62     if(m >= x) ans = max(ans, query(x, lson));
63     else ans = max(ans, query(x, rson));
64     return ans;
65 }
66 int v[N], d[N];
67 int main(){
68     int n;
69     scanf("%d", &n);
70     for(int i = 1; i <= n; i++)
71         scanf("%d%d", &v[i], &d[i]);
72     update(-d[1],v[1]+d[1],0,n+1,1);
73     for(int i = 2; i <= n; i++){
74         LL zz = query(i,0,n+1,1) + v[i];
75         update(-d[i],zz+1ll*d[i]*i,0,n+1,1);
76     }
77     LL ans = query(n+1,1,n,1);
78     if(ans < 0) ans = 0;
79     cout << ans << endl;
80     return 0;
81 }