luoguP3374 【模板】树状数组 1 cdq

链接

思路

可耐我连cdq都不会，Orz 陈丹琦
代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 7;

int read() {

    int x = 0, f = 1; char s = getchar();

    for (;s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;

    for (;s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';

    return x * f;

}

int ans[N];

struct node {

    int type, id, val;

    node(int a = 0,int b = 0, int c = 0) {

        type = a, id = b, val = c;

    }

    bool operator < (const node &b) const {

        return id == b.id ? type < b.type : id < b.id;

    }

} Q[N<<2], tmp[N<<2];

void cdq(int l, int r){

    if (l == r) return;

    int mid = (l + r) >> 1;

    cdq(l, mid), cdq(mid + 1, r);

    int p = l, q = mid + 1, js = l, sum = 0;

    while (p <= mid && q <= r) {

        if (Q[p] < Q[q]) {

            if (Q[p].type == 1) sum += Q[p].val;

            tmp[js++] = Q[p++];

        } else {

            if (Q[q].type == 2) ans[Q[q].val] -= sum;

            if (Q[q].type == 3) ans[Q[q].val] += sum;

            tmp[js++] = Q[q++];

        }

    }

    while (p <= mid) tmp[js++] = Q[p++];

    while (q <= r) {

        if (Q[q].type == 2) ans[Q[q].val] -= sum;

        if (Q[q].type == 3) ans[Q[q].val] += sum;

        tmp[js++] = Q[q++];

    }

    for (int i = l; i <= r; ++i) Q[i] = tmp[i];

}

int main() {

    int n = read(), m = read(), js = 0, DSR = 0;

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

        int x = read();

        Q[++js] = node(1, i, x);

    }

    for(int i = 1; i <= m; ++i) {

        int opt = read(), x = read(), y = read();

        if (opt == 1) {

            Q[++js] = node(1, x, y);

        } else {

            Q[++js] = node(2, x-1, ++DSR),

            Q[++js] = node(3, y, DSR);

        }

    }

    cdq(1, js);

    for (int i = 1; i <= DSR; ++i) printf("%d\n", ans[i]);

    return 0;

}
巴特西

luoguP3374 【模板】树状数组 1 cdq

链接

思路

代码

最新文章

热门文章
