样例过了全wa求助

Tibrella @ 2023-01-29 22:31:30

#include <iostream>

using namespace std;

#define int long long
#define N 1000150

struct Node {
    int u;
    int v;
    Node *lc, *rc;
    int l, r, mid;
    int lazy;  // 懒标记
    void init(int L, int R) {
        l = L;
        r = R;
        mid = l + r >> 1;
    }
} tr[N * 4];

int n, m;
int x, y, k;
int ori[N];
char beh;
int t1, t2, t3;
Node* tail = tr;

void push_up(Node* nod) {
    nod->v = nod->lc->v + nod->rc->v;
}

void build(Node* nod, int L, int R) {
    nod->init(L, R);
    if (L == R) {
        nod->v = ori[L];
        nod->lc = nod->rc = tr;
        return;
    }
    nod->lc = (++tail);
    build(tail, L, nod->mid);
    nod->rc = (++tail);
    build(tail, nod->mid + 1, R);
    push_up(nod);
}

void push_down(Node* nod) {
    nod->lc->lazy += nod->lazy;
    nod->rc->lazy += nod->lazy;
    nod->lc->v += (nod->mid - nod->l + 1) * nod->lazy;
    nod->rc->v += (nod->r - nod->mid) * nod->lazy;
    nod->lazy = 0;
}

void modify(Node* nod, int L, int R, int v) {
    if (L <= nod->l && R >= nod->r) {
        nod->lazy += v;
        nod->v += (nod->r - nod->l + 1) * v;
    } else {
        push_down(nod);
        if (nod->mid < R) {
            modify(nod->rc, nod->mid + 1, R, v);
        }
        if (nod->mid >= L) {
            modify(nod->lc, L, nod->mid, v);
        }
        push_up(nod);
    }
}

int query(Node* nod, int L, int R) {
    if (nod->r == R && nod->l == L) {
        return nod->v;
    }
    push_down(nod);
    if (nod->mid >= R) {
        return query(nod->lc, L, nod->mid);
    } else if (nod->mid < L) {
        return query(nod->rc, nod->mid + 1, R);
    } else {
        return query(nod->lc, L, nod->mid) + query(nod->rc, nod->mid + 1, R);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> ori[i];
    }
    build(++tail, 1, n);
    while (m--) {
        cin >> beh;
        if (beh == '1') {
            cin >> t1 >> t2 >> t3;
            modify(tr + 1, t1, t2, t3);
        } else {
            cin >> t1 >> t2;
            cout << query(tr + 1, t1, t2) << endl;
        }
    }

    return 0;
}

by Tibrella @ 2023-01-29 23:59:28

这是向题解学习之后改的

#include <iostream>

using namespace std;

#define int long long
#define N 1000150

struct Node {
    int u;
    int v;
    Node *lc, *rc;
    int l, r, mid;
    int lazy;  // 懒标记
    void init(int L, int R) {
        l = L;
        r = R;
        mid = l + r >> 1;
    }
} tr[N * 4];

int n, m;
int x, y, k;
int ori[N];
char beh;
int t1, t2, t3;
int cnt=1;
Node* tail = tr;

void push_up(Node* nod) {
    nod->v = nod->lc->v + nod->rc->v;
}

void build(Node* nod, int L, int R) {
    nod->init(L, R);
    if (L == R) {
        nod->v = ori[L];
        nod->lc = nod->rc = tr;
        return;
    }
    nod->lc = &tr[++cnt];
    nod->rc = &tr[++cnt];
    build(nod->lc, L, nod->mid);

    build(nod->rc, nod->mid + 1, R);
    push_up(nod);
}

void push_down(Node* nod) {
    if (nod->lazy==0) return;
    if (nod->lc) nod->lc->lazy += nod->lazy;
    if (nod->rc) nod->rc->lazy += nod->lazy;
    nod->lc->v += (nod->mid - nod->l + 1) * nod->lazy;
    nod->rc->v += (nod->r - nod->mid) * nod->lazy;
    nod->lazy = 0;
}

void modify(Node* nod, int L, int R, int v) {
    if (L == nod->l && R == nod->r) {
        nod->lazy += v;
        nod->v += (nod->r - nod->l + 1) * v;
    } else {
        push_down(nod);
        if (nod->lc->r >= R) {
            modify(nod->lc, L, R, v);
        }
        else if (nod->rc->l <= L) {
            modify(nod->rc, L, R, v);
        } else {
            modify(nod->lc, L, nod->lc->r,v);
            modify(nod->rc,nod->rc->l,R,v);
        }
        push_down(nod);
        push_up(nod);
    }
}

int query(Node* nod, int L, int R) {
    push_down(nod);
    if (nod->r == R && nod->l == L) {
        return nod->v;
    }

    if (nod->lc->r >= R) {
        return query(nod->lc, L, R);
    } else if (nod->rc->l <= L) {
        return query(nod->rc, L, R);
    } else {
        return query(nod->lc, L, nod->lc->r) + query(nod->rc, nod->rc->l, R);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> ori[i];
    }
    build(++tail, 1, n);
    while (m--) {
        cin >> beh;
        if (beh == '1') {
            cin >> t1 >> t2 >> t3;
            modify(tr + 1, t1, t2, t3);
        } else {
            cin >> t1 >> t2;
            cout << query(tr + 1, t1, t2) << endl;
        }
    }

    return 0;
}

明天早上继续研究） 如果有佬发现了欢迎指出来原来的错）

by cjwdxfblzs @ 2023-01-30 07:19:25

为啥用指针写 我一直觉得指针这东西写起来可乱了（

by cjwdxfblzs @ 2023-01-30 07:22:20

噢 你的查询函数和修改函数有问题

by cjwdxfblzs @ 2023-01-30 07:24:51

你的查询函数往左右儿子递归的时候 传出来的参数L,R不能变 但是你改成了,(mid+1,R)和（l,mid)

by Tibrella @ 2023-01-30 07:37:13

1. modify() 需要判断三种情况
2. query() 判断之后查询如果不包含中间就需要依然用原来区间往下查

@OPTIM Orz

此贴完结

by _GrainRain_ @ 2023-01-30 14:05:01

@PingHigh