hdu 6012 Lotus and Horticulture 打标记

http://acm.hdu.edu.cn/showproblem.php?pid=6012

我们希望能够快速算出，对于每一个温度，都能够算出它在这n颗植物中，能得到多少价值。

那么，对于第i科植物，在[0, L[i] - 1]这些温度中，得到的价值是低温那个价值，同理在[L[i], R[i]]中，和[R[i], mx]中，

那么可以用O(1)打标记的思路去完成。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

map<int, LL>book;

void work() {

    book.clear();

    int n;

    scanf("%d", &n);

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

        int L, R, a, b, c;

        scanf("%d%d%d%d%d", &L, &R, &a, &b, &c);

        book[] += c;

        book[L << ] += a - c;

        book[(R << ) + ] += b - a;

    }

    LL ans = ;

    LL tans = ;

    for (map<int, LL> :: iterator it = book.begin(); it != book.end(); ++it) {

        tans += it->second;

        ans = max(ans, tans);

    }

    printf("%I64d\n", ans);

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

同样可以用线段树完成，就是先把坐标离散了，然后区间更新和上面一样的东西。

线段树维护最大值，seg[cur]表示这课树覆盖的区间，其中某个温度能取得的最大值。

但是我一直wa，不知为何。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

#define lson L, mid, cur << 1

#define rson mid + 1, R, cur << 1 | 1

#define root 1, mx, 1

const int maxn =  + ;

int L[maxn], R[maxn];

LL a[maxn], b[maxn], c[maxn];

LL add[maxn << ], seg[maxn << ];

vector<int>da;

void pushDown(int cur) {

    if (add[cur]) {

        add[cur << ] += add[cur];

        add[cur <<  | ] += add[cur];

        seg[cur <<  | ] += add[cur];

        seg[cur << ] += add[cur];

        add[cur] = ;

    }

}

void pushUp(int cur) {

    seg[cur] = max(seg[cur << ], seg[cur <<  | ]);

    assert(seg[cur] >= );

}

void build(int L, int R, int cur) {

    seg[cur] = add[cur] = ;

    if (L == R) {

        return;

    }

    int mid = (L + R) >> ;

    build(lson);

    build(rson);

    pushUp(cur);

}

void upDate(int be, int en, LL val, int L, int R, int cur) {

    if (L >= be && R <= en) {

        seg[cur] += val;

        add[cur] += val;

        return;

    }

    pushDown(cur);

    int mid = (L + R) >> ;

    if (be <= mid) upDate(be, en, val, lson);

    if (en > mid) upDate(be, en, val, rson);

    pushUp(cur);

}

LL query(int be, int en, int L, int R, int cur) {

    if (L >= be && R <= en) return seg[cur];

    pushDown(cur);

    LL ans = ;

    int mid = (L + R) >> ;

    if (be <= mid) ans += query(be, en, lson);

    if (en > mid) ans += query(be, en, rson);

    return ans;

}

void work() {

    da.clear();

    int n;

    scanf("%d", &n);

    da.push_back(-inf);

    da.push_back(-inf);

    da.push_back(-inf);

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

        scanf("%d%d%I64d%I64d%I64d", &L[i], &R[i], &a[i], &b[i], &c[i]);

        assert(L[i] <= R[i]);

        if (L[i] > R[i]) swap(L[i], R[i]);

        L[i] *= ;

        R[i] *= ;

        da.push_back(L[i]);

        da.push_back(R[i]);

    }

    sort(da.begin(), da.end());

    int gg = da.size();

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

        if (da[i] - da[i - ] == ) {

            da.push_back(da[i] - );

        }

    }

    sort(da.begin(), da.end());

    int mx = ;

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

        L[i] = lower_bound(da.begin(), da.end(), L[i]) - da.begin();

        R[i] = lower_bound(da.begin(), da.end(), R[i]) - da.begin();

//        cout << L[i] << " " << R[i] << endl;

        mx = max(mx, R[i] + );

    }

//    cout << endl;

    build(root);

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

        upDate(, L[i] - , c[i], root);

        upDate(L[i], R[i], a[i], root);

        upDate(R[i] + , mx, b[i], root);

    }

    cout << query(, mx, root) << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

原来是我离散化错了

一开始的时候，认为[70, 73] [74, 76]这样，73和74相邻，那么乘以2后，变成146 148，那么相隔2的时候才添加些元素进去，比如添加147进去隔着，这样离散化。

这样有bug（还没想到有什么bug）

现在的思路是：乘以2后，把L[i] + 1和R[i] + 1也放进去，这样就不会有挨着了

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

#define lson L, mid, cur << 1

#define rson mid + 1, R, cur << 1 | 1

#define root 1, mx, 1

const int maxn =  + ;

int L[maxn], R[maxn];

int a[maxn], b[maxn], c[maxn];

LL add[maxn << ], seg[maxn << ];

vector<int>da;

void pushDown(int cur) {

    if (add[cur]) {

        add[cur << ] += add[cur];

        add[cur <<  | ] += add[cur];

        seg[cur <<  | ] += add[cur];

        seg[cur << ] += add[cur];

        add[cur] = ;

    }

}

void pushUp(int cur) {

    seg[cur] = max(seg[cur << ], seg[cur <<  | ]);

}

void build(int L, int R, int cur) {

    seg[cur] = add[cur] = ;

    if (L == R) {

        return;

    }

    int mid = (L + R) >> ;

    build(lson);

    build(rson);

    pushUp(cur);

}

void upDate(int be, int en, LL val, int L, int R, int cur) {

    if (L >= be && R <= en) {

        seg[cur] += val;

        add[cur] += val;

        return;

    }

    pushDown(cur);

    int mid = (L + R) >> ;

    if (be <= mid) upDate(be, en, val, lson);

    if (en > mid) upDate(be, en, val, rson);

    pushUp(cur);

}

void work() {

    da.clear();

    int n;

    scanf("%d", &n);

    da.push_back(-inf);

    da.push_back(-inf);

    da.push_back(-inf);

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

        scanf("%d%d%d%d%d", &L[i], &R[i], &a[i], &b[i], &c[i]);

        L[i] *= ;

        R[i] *= ;

        da.push_back(L[i]);

        da.push_back(L[i] + );

        da.push_back(R[i] + );

        da.push_back(R[i]);

    }

    sort(da.begin(), da.end());

    int mx = ;

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

        L[i] = lower_bound(da.begin(), da.end(), L[i]) - da.begin();

        R[i] = lower_bound(da.begin(), da.end(), R[i]) - da.begin();

//        cout << L[i] << " " << R[i] << endl;

        mx = max(mx, R[i] + );

    }

//    cout << endl;

    build(root);

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

        upDate(, L[i] - , c[i], root);

        upDate(L[i], R[i], a[i], root);

        upDate(R[i] + , mx, b[i], root);

    }

    printf("%I64d\n", seg[]);

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

现在的方法是直接

巴特西

hdu 6012 Lotus and Horticulture 打标记

最新文章

热门文章