【洛谷P4148】简单题（kd-tree）

题意：

给出一个\(n*n\)的棋盘，现在有两种操作：一种是某个格子里的数字加上\(A\)，另一种是询问矩阵和。

空间限制：\(20MB\)，强制在线。

思路：

直接\(kd-tree\)来搞，复杂度是\(O(n\sqrt{n})\)的。

但这个题丧心病狂，卡空间不说，还卡时间。

我就是因为一开始结构体里面的构造函数多写了几条语句，卡了我整整几个小时，难受。

感觉\(kd-tree\)就这样了，本质是一种玄学暴力，只有矩阵查询复杂度稳定一点（直接上cdq分治啊）。刷不动了，这种码量大的数据结果还是有点恶心。

/*

 * Author:  heyuhhh

 * Created Time:  2019/11/26 10:29:18

 */

#include <iostream>

#include <algorithm>

#include <vector>

#include <cmath>

#include <set>

#include <map>

#include <iomanip>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

#define INF 0x3f3f3f3f

#define Local

#ifdef Local

  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

  void err() { std::cout << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 2e5 + 5;

int n;

int D;

struct Point {

    int d[2], val;

}tmp[N], T;

//取消了构造函数，另写一个结构体。

struct Node {

    int mn[2], mx[2];

    int l, r, sumv, sz;

    Point t;

}tr[N];

bool operator < (const Point &A, const Point &B) {

    return A.d[D] < B.d[D];

}

int rt;

int rub[N], top, tot;

struct kdtree {

    const double E = 0.75;

    int ans;

    int new_node() {

        if(top) return rub[top--];

        return ++tot;

    }

    void push_up(int o) {

        int ls = tr[o].l, rs = tr[o].r;

        for(int i = 0; i < 2; i++) {

            tr[o].mn[i] = tr[o].mx[i] = tr[o].t.d[i];

            if(ls) {

                tr[o].mn[i] = min(tr[o].mn[i], tr[ls].mn[i]);

                tr[o].mx[i] = max(tr[o].mx[i], tr[ls].mx[i]);

            }

            if(rs) {

                tr[o].mn[i] = min(tr[o].mn[i], tr[rs].mn[i]);

                tr[o].mx[i] = max(tr[o].mx[i], tr[rs].mx[i]);

            }

        }

        tr[o].sumv = tr[ls].sumv + tr[rs].sumv + tr[o].t.val;

        tr[o].sz = 1 + tr[ls].sz + tr[rs].sz;

    }

    void pia(int o, int num) {

        int ls = tr[o].l, rs = tr[o].r;

        if(ls) pia(ls, num);

        tmp[tr[ls].sz + num + 1] = Point{tr[o].t.d[0], tr[o].t.d[1], tr[o].t.val};

        rub[++top] = o;

        if(rs) pia(rs, tr[ls].sz + num + 1);

    }

    int rebuild(int l, int r, int now) {

        if(l > r) return 0;

        D = now;

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

        nth_element(tmp + l, tmp + mid, tmp + r + 1);

        int node = new_node();

        tr[node].t = tmp[mid];

        tr[node].l = rebuild(l, mid - 1, now ^ 1);

        tr[node].r = rebuild(mid + 1, r, now ^ 1);

        push_up(node);

        return node;

    }

    void chk(int &o, int now) {

        if(tr[o].sz * E <= tr[tr[o].l].sz || tr[o].sz * E <= tr[tr[o].r].sz) {

            pia(o, 0);

            o = rebuild(1, tr[o].sz, now);

        }

    }

    void insert(int &o, int now) {

        if(!o) {

            tr[o = new_node()].t = T;

            tr[o].l = tr[o].r = 0;

            push_up(o);

            return;

        }

        D = now;

        if(tr[o].t.d[D] < T.d[D]) insert(tr[o].r, now ^ 1);

        else insert(tr[o].l, now ^ 1);

        push_up(o);

        chk(o, now);

    }

    bool in(int x, int y, int x1, int y1, int x2, int y2) {

        return x >= x1 && x <= x2 && y >= y1 && y <= y2;

    }

    void query(int o, int x1, int y1, int x2, int y2) {

        if(o == 0) return;

        if(tr[o].mn[0] >= x1 && tr[o].mx[0] <= x2 && tr[o].mn[1] >= y1 && tr[o].mx[1] <= y2) {

            ans += tr[o].sumv;

            return;

        }

        if(tr[o].mn[0] > x2 || tr[o].mx[0] < x1 || tr[o].mn[1] > y2 || tr[o].mx[1] < y1) return;

        if(in(tr[o].t.d[0], tr[o].t.d[1], x1, y1, x2, y2)) ans += tr[o].t.val;

        query(tr[o].l, x1, y1, x2, y2);

        query(tr[o].r, x1, y1, x2, y2);

    }

}kd;

void run(){

    int ans = 0;

    while(true) {

        int op; cin >> op;

        if(op == 3) return;

        if(op == 1) {

            int x, y, A; cin >> x >> y >> A;

            x ^= ans;

            y ^= ans;

            A ^= ans;

            T = Point {x, y, A};

            kd.insert(rt, 0);

        } else {

            int x1, x2, y1, y2;

            cin >> x1 >> y1 >> x2 >> y2;

            x1 ^= ans;

            y1 ^= ans;

            x2 ^= ans;

            y2 ^= ans;

            kd.ans = 0;

            kd.query(rt, x1, y1, x2, y2);

            ans = kd.ans;

            cout << ans << '\n';

        }

    }

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    while(cin >> n) run();

    return 0;

}

巴特西

【洛谷P4148】简单题（kd-tree）

最新文章

热门文章