感觉加了点没用的东西居然过了
查看原帖
感觉加了点没用的东西居然过了
307542
yyyhy楼主2024/9/22 17:55

code1:

#include <cstdio>
#include <algorithm>
#define int long long
#define maxn 200000
#define inf 2100000000

struct code {
    int left, x;
} a[maxn + 10], m;

int tree[(maxn << 1) + 10];
void add(int id, int l, int r, int w, int x) {
    if (l == r) {
        tree[id] = x;
        return;
    }
    int mid = l + r >> 1;
    if (w <= mid) add(id << 1, l, mid, w, x);
    else add((id << 1) + 1, mid + 1, r, w, x);
    tree[id] = std :: max(tree[id << 1], tree[(id << 1) + 1]);
    return;
}
void kill(int id, int l, int r, int maxr) {
    if (l == r) {
        tree[id] = -inf;
        return;
    }
    int mid = l + r >> 1;
    if (maxr <= mid) kill(id << 1, l, mid, maxr);
    else tree[id << 1] = -inf, kill((id << 1) + 1, mid + 1, r, maxr);
    tree[id] = std :: max(tree[id << 1], tree[(id << 1) + 1]);
    return;
}

int l = 1, r, n, suml[maxn + 10], del;

signed main(void) {
    int id, Q, p, x; scanf("%lld %lld", &id, &Q);
    n = Q;
    while (Q--) {
        scanf("%lld", &p);
        if (p == 1) {
            scanf("%lld", &x);
            m.left = m.x = x;
            a[++r] = m;
            suml[r] = suml[r - 1] + x;
            add(1, 1, n, r, m.x);
        } else if (p == 2) {
            scanf("%lld", &x);
            del += x;
            while (a[l].left <= x && x) 
                x -= a[l++].left;
            a[l].left -= x;
            kill(1, 1, n, l - 1);
        } else if (p == 3) {
            scanf("%lld", &x);
            int ll = l, rr = r;
            while (ll < rr) {
                int mid = ll + rr >> 1;
                if (suml[mid] < del + x) ll = mid + 1;
                else rr = mid;
            }
            printf("%lld\n", del + x - suml[ll - 1]);
        } else {
            printf("%lld\n", tree[1]);
        }
    }
    
    return 0;
}

code2:

#include <cstdio>
#include <algorithm>
#define int long long
#define maxn 200000
#define inf 2100000000

struct code {
    int left, x;
} a[maxn + 10], m;

int tree[(maxn << 1) + 10];
void add(int id, int l, int r, int w, int x) {
    if (l == r) {
        tree[id] = x;
        return;
    }
    int mid = l + r >> 1;
    if (w <= mid) add(id << 1, l, mid, w, x);
    else add((id << 1) + 1, mid + 1, r, w, x);
    tree[id] = std :: max(tree[id << 1], tree[(id << 1) + 1]);
    return;
}
void kill(int id, int l, int r, int maxr) {
    if (l == r) {
        if (maxr >= r) tree[id] = -inf; // here
        return;
    }
    int mid = l + r >> 1;
    if (maxr <= mid) kill(id << 1, l, mid, maxr);
    else tree[id << 1] = -inf, kill((id << 1) + 1, mid + 1, r, maxr);
    tree[id] = std :: max(tree[id << 1], tree[(id << 1) + 1]);
    return;
}

int l = 1, r, n, suml[maxn + 10], del;

signed main(void) {
    int id, Q, p, x; scanf("%lld %lld", &id, &Q);
    n = Q;
    while (Q--) {
        scanf("%lld", &p);
        if (p == 1) {
            scanf("%lld", &x);
            m.left = m.x = x;
            a[++r] = m;
            suml[r] = suml[r - 1] + x;
            add(1, 1, n, r, m.x);
        } else if (p == 2) {
            scanf("%lld", &x);
            del += x;
            while (a[l].left <= x && x) 
                x -= a[l++].left;
            a[l].left -= x;
            kill(1, 1, n, l - 1);
        } else if (p == 3) {
            scanf("%lld", &x);
            int ll = l, rr = r;
            while (ll < rr) {
                int mid = ll + rr >> 1;
                if (suml[mid] < del + x) ll = mid + 1;
                else rr = mid;
            }
            printf("%lld\n", del + x - suml[ll - 1]);
        } else {
            printf("%lld\n", tree[1]);
        }
    }
    
    return 0;
}

感觉这句话没用因为l==r时maxr>=r应该是必然成立的 但就这样才能过 求解释

2024/9/22 17:55
加载中...