kkogoro

BZOJ 1568
李超线段树模板题#include <iostream> #include <cstdio>...
扫描右侧二维码阅读全文
14
2019/01

BZOJ 1568

李超线段树模板题

#include <iostream>
#include <cstdio>
 
 
const int MAXN = 100007;
const int MAXX = 50007;
 
struct Line {
    double k, b;
} line[MAXN];
int tot_line;
 
 
namespace LiChaoSegmentTree {
#define L(x) (x << 1)
#define R(x) (x << 1 | 1)
    int node[MAXX << 2], cntNode;
    inline bool check(int line1, int line2, int x) {
        --x;
        return line[line1].k * x + line[line1].b > line[line2].k * x + line[line2].b;
    }
    void insert(int cur, int l, int r, int nowline) {
        if (l == r) {
            if (check(nowline, node[cur], l)) node[cur] = nowline;
            return;
        }
        int mid = (l + r) >> 1;
        if (line[nowline].k > line[ node[cur] ].k) {
            if (check(nowline, node[cur], mid)) insert(L(cur), l, mid, node[cur]), node[cur] = nowline;
            else insert(R(cur), mid + 1, r, nowline);
        }
        else {
            if (check(nowline, node[cur], mid)) insert(R(cur), mid + 1, r, node[cur]), node[cur] = nowline;
            else insert(L(cur), l, mid, nowline);
        }
        return;
    }
    void query(double &ans, int cur, int l, int r, int x) {
        ans = std::max(ans, line[ node[cur] ].k * (x - 1) + line[ node[cur] ].b);
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) query(ans, L(cur), l, mid, x);
        else query(ans, R(cur), mid + 1, r, x);
        return;
    }
#undef L
#undef R
}
 
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        char opt[8];
        scanf("%s", opt);
        if (opt[0] == 'P') {
            ++tot_line;
            scanf("%lf%lf", &line[tot_line].b, &line[tot_line].k);
            LiChaoSegmentTree::insert(1, 1, MAXX - 1, tot_line);
        }
        else {
            int x;
            scanf("%d", &x);
            double ans = 0;
            LiChaoSegmentTree::query(ans, 1, 1, MAXX - 1, x);
            printf("%d\n", (int)(ans / 100));
        }
    }
    return 0;
}
Last modification:January 14th, 2019 at 03:58 pm

Leave a Comment