M_sea

洛谷4254 [JSOI2008]Blue Mary开公司
LuoguBZOJ分析对于第 $i$ 个计划,第 $x$ 天的收益为 $s_i+(x-1)p_i$ 。显然是一次函...
扫描右侧二维码阅读全文
12
2019/03

洛谷4254 [JSOI2008]Blue Mary开公司

Luogu

BZOJ

分析

对于第 $i$ 个计划,第 $x$ 天的收益为 $s_i+(x-1)p_i$ 。显然是一次函数的形式。

那么就是李超线段树的板子了。

推荐阅读

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

const int N=500000+10;

int n,m;
int t[N<<2];
double k[N<<1],b[N<<1];

inline double f(int w,int x) { return k[w]*(x-1)+b[w]; }

#define ls (o<<1)
#define rs (o<<1|1)

inline void update(int o,int l,int r,int x) {
    if (l==r) {
        if (f(x,l)>f(t[o],l)) t[o]=x;
        return;
    }
    int mid=(l+r)>>1;
    if (k[t[o]]<k[x]) {
        if (f(x,mid)>f(t[o],mid)) update(ls,l,mid,t[o]),t[o]=x;
        else update(rs,mid+1,r,x);
    } else if (k[t[o]]>k[x]) {
        if (f(x,mid)>f(t[o],mid)) update(rs,mid+1,r,t[o]),t[o]=x;
        else update(ls,l,mid,x);
    }
}

inline double query(int o,int l,int r,int x) {
    if (l==r) return f(t[o],x);
    int mid=(l+r)>>1;
    if (x<=mid) return max(f(t[o],x),query(ls,l,mid,x));
    else return max(f(t[o],x),query(rs,mid+1,r,x));
}

int main() {
    scanf("%d",&n);
    while (n--) {
        char op[10]; scanf("%s",op);
        if (op[0]=='P') {
            ++m; scanf("%lf%lf",&b[m],&k[m]);
            update(1,1,N,m);
        } else {
            int x; scanf("%d",&x);
            printf("%d\n",(int)(query(1,1,N,x)/100));
        }
    }
    return 0;
}
最后修改:2019 年 03 月 12 日 09 : 34 PM

发表评论