Luogu P3374 【模板】树状数组 1(CDQ分治)

题目描述

https://www.luogu.com.cn/problem/P3374

Solution

我们将时间看做是一维，操作的位置看做是第二维

然后用 $cdq$ 解决一维，两边排序解决第二维

排序用归并排序可以做到 $O(n\log n)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#define cQ const Query
#define maxn 500010
using namespace std;

int n, m;

struct Query { 
    int x, v, id;

    Query() {}
    Query(int _x, int _v, int _id) { x = _x; v = _v; id = _id; }

    friend bool operator < (cQ &u, cQ &v) { return u.x < v.x; } 
} Q[maxn * 3]; int cnt;

int ans[maxn], cans;
void cdq(int l, int r) {
    if (l == r) return ; int m = l + r >> 1, j = l - 1, sum = 0;
    cdq(l, m); cdq(m + 1, r); 
    for (int i = m + 1; i <= r; ++i) {
        int x = Q[i].x, v = Q[i].v, id = Q[i].id;
        if (!id) continue;
        while (j < m && Q[j + 1].x <= x) {
            ++j; if (Q[j].id) continue;
            sum += Q[j].v;
        } ans[id] += v * sum; 
    }
    inplace_merge(Q + l, Q + m + 1, Q + r + 1); 
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x; scanf("%d", &x);
        Q[++cnt] = Query(i, x, 0);
    }
    for (int i = 1; i <= m; ++i) {
        int opt, x, y; scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1) Q[++cnt] = Query(x, y, 0);
        else {
            Q[++cnt] = Query(x - 1, -1, ++cans);
            Q[++cnt] = Query(y, 1, cans);
        }
    } 
    cdq(1, cnt);
    for (int i = 1; i <= cans; ++i) printf("%d\n", ans[i]);
    return 0;
}