Luogu P4148 简单题

题目描述

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

简要题意：给定一个 $n\times n$ 的网格图，初始时每个位置都为 $0$，现在有 $m$ 次操作，操作有两种，第一种操作给定 $(x,y)$ 和 $v$，将 $(x,y)$ 加上 $v$；第二种操作给定矩形的左上角和右下角 $(x_1,y_1)$ 和 $(x_2,y_2)$，求矩形和

$n\le 5\times 10^5$，强制在线

Solution

单点加，矩阵求和

我们将单点加看成插入，众所周知 $KD~~Tree$ 是不能插入的

所以我们考虑一种根号分治，即插入超过 $O(\sqrt n)$ 个节点就进行重构，这样时间复杂度为 $O(n\sqrt n\log n)$

我们可以将阙值微调到 $O(\sqrt {n\log n})$，这样的时间复杂度就是 $O(n\sqrt {n\log n})$

#include <iostream>
#include <algorithm>
#include <cmath>
#define maxn 500010
using namespace std;

int n, m, B;

struct Point {
    int x, y, v;
} a[maxn]; int al, ar;
inline bool cmpx(const Point &u, const Point &v) {
    if (u.x == v.x) return u.y < v.y;
    return u.x < v.x;
}

inline bool cmpy(const Point &u, const Point &v) {
    if (u.y == v.y) return u.x < v.x;
    return u.y < v.y;
}

#define lc i << 1
#define rc i << 1 | 1
struct KDtree {
    int v, xl, xr, yl, yr; 
} T[maxn * 4];
inline void maintain(int i) {
    T[i].v = T[lc].v + T[rc].v;
    T[i].xl = min(T[lc].xl, T[rc].xl);
    T[i].xr = max(T[lc].xr, T[rc].xr);
    T[i].yl = min(T[lc].yl, T[rc].yl);
    T[i].yr = max(T[lc].yr, T[rc].yr);
}

void build(int i, int l, int r, int d) {
    if (l == r) return T[i] = { a[l].v, a[l].x, a[l].x, a[l].y, a[l].y }, void();
    int m = l + r >> 1; nth_element(a + l + 1, a + m, a + r + 1, d ? cmpy : cmpx); 
    build(lc, l, m, d ^ 1); build(rc, m + 1, r, d ^ 1);
    maintain(i); 
}

int query(int i, int xl, int xr, int yl, int yr) {
    if (max(T[i].xl, xl) > min(T[i].xr, xr) || max(T[i].yl, yl) > min(T[i].yr, yr)) return 0;
    if (xl <= T[i].xl && T[i].xr <= xr && yl <= T[i].yl && T[i].yr <= yr) return T[i].v;
    return query(lc, xl, xr, yl, yr) + query(rc, xl, xr, yl, yr); 
}

int lans;
inline void solve_1() {
    int x, y, v; cin >> x >> y >> v;
    x ^= lans; y ^= lans; v ^= lans;
    a[++ar] = { x, y, v };
    if ((ar - al) * (ar - al) > ar * 40) build(1, 1, al = ar, 0); 
}

inline void solve_2() {
    int xl, yl, xr, yr, ans; cin >> xl >> yl >> xr >> yr;
    xl ^= lans; yl ^= lans; xr ^= lans; yr ^= lans;
    ans = query(1, xl, xr, yl, yr);
    for (int i = al + 1; i <= ar; ++i)
        if (xl <= a[i].x && a[i].x <= xr && yl <= a[i].y && a[i].y <= yr)
            ans += a[i].v;
    cout << (lans = ans) << "\n"; 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; int lans = 0; 
    while (1) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else if (opt == 2) solve_2();
        else break; 
    } 
    return 0;
}