简单题
题目链接：ybt金牌导航4-2-4 / luogu P4148
题目大意
给你一个矩阵，要你支持两个操作：
在一个地方加一个数，询问一个子矩阵中所有数的和。
强制在线，矩阵大小最大 50000*50000。
思路
一看到题目：这不是树状数组套树状数组 ** 题吗？
再一看时间，8s，乱玩都玩的过去。
由于这是 K-D tree 专题，我还退出去看了几次真的是 K-D tree 专题。
然后一看范围：(nleq 5 imes10^5)，笑容直接消失。
然后就发现它询问（插入点）的次数不超过 (2 imes 10^5)，就发现很多位置没有用，就考虑不把图弄出来。
然后就想到了 K-D tree 的做法。
大概就是一个点代表一个矩阵（以及一个里面的点），那如果这个矩阵完全在询问矩阵里面，就是这个矩阵里面所有数字的和。（这个可以搞一个变量维护一下）
那如果不是的话，我们再来讨论。
首先，如果这个树上点代表的途中点在询问矩阵中，就加进去。
然后看树上点的两个儿子，当然它们要可能有贡献的前提是它们代表的矩阵和询问矩阵有相交，那判断一下，如果是就递归下去。
然后大概就是这样，由于它会不断插入点，所以我们要的是能实现拍扁重构的 K-D tree。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define alph (0.76)
using namespace std;
struct zb {
int w[2], val;
}x, y, a[200001];
struct KDtree {
zb a;
int l, r, ma[2], mi[2], valsum, size;
}tree[200001];
int n, lastans, op, WD, root;
int rebuild[200001], tot;
int get_new() {
if (rebuild[0]) return rebuild[rebuild[0]--];
return ++tot;
}
void up(int now) {
for (int i = 0; i < 2; i++) {
tree[now].ma[i] = tree[now].mi[i] = tree[now].a.w[i];
if (tree[now].l) {
tree[now].ma[i] = max(tree[now].ma[i], tree[tree[now].l].ma[i]);
tree[now].mi[i] = min(tree[now].mi[i], tree[tree[now].l].mi[i]);
}
if (tree[now].r) {
tree[now].ma[i] = max(tree[now].ma[i], tree[tree[now].r].ma[i]);
tree[now].mi[i] = min(tree[now].mi[i], tree[tree[now].r].mi[i]);
}
}
tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
tree[now].valsum = tree[tree[now].l].valsum + tree[tree[now].r].valsum + tree[now].a.val;
}
void do_again(int root, int num) {
if (tree[root].l) do_again(tree[root].l, num);
a[num + tree[tree[root].l].size + 1] = tree[root].a;
rebuild[++rebuild[0]] = root;
if (tree[root].r) do_again(tree[root].r, num + tree[tree[root].l].size + 1);
}
bool cmp(zb x, zb y) {
return x.w[WD] < y.w[WD];
}
int build(int l, int r, int wd) {
if (l > r) return 0;
int mid = (l + r) >> 1;
int now = get_new();
WD = wd;
nth_element(a + l, a + mid, a + r + 1, cmp);
tree[now].a = a[mid];
tree[now].l = build(l, mid - 1, wd ^ 1);
tree[now].r = build(mid + 1, r, wd ^ 1);
up(now);
return now;
}
void check(int &root, int wd) {
if (alph * tree[root].size < tree[tree[root].l].size || alph * tree[root].size < tree[tree[root].r].size) {
do_again(root, 0);
root = build(1, tree[root].size, wd);
}
}
void insert(zb x, int &root, int wd) {
if (!root) {
root = get_new();
tree[root].a = x;
tree[root].l = tree[root].r = 0;
up(root);
return ;
}
if (x.w[wd] > tree[root].a.w[wd]) {
insert(x, tree[root].r, wd ^ 1);
}
else insert(x, tree[root].l, wd ^ 1);
up(root);
check(root, wd);
}
bool inside_blog_blog(zb x, zb y, KDtree z) {//判断当前点对应矩阵是否完全包含在询问矩阵中
for (int i = 0; i < 2; i++) {
if (z.mi[i] < x.w[i]) return 0;
if (z.ma[i] > y.w[i]) return 0;
}
return 1;
}
bool inside_blog_point(zb x, zb y, zb z) {//判断这个点是否在询问矩阵中
for (int i = 0; i < 2; i++) {
if (z.w[i] < x.w[i]) return 0;
if (z.w[i] > y.w[i]) return 0;
}
return 1;
}
bool touch_blog_blog(zb x, zb y, KDtree z) {//判断这个点对应矩阵和询问矩阵是否有交点（这样就可能里面有点在询问矩阵中）
for (int i = 0; i < 2; i++) {
if (z.mi[i] > y.w[i]) return 0;
if (z.ma[i] < x.w[i]) return 0;
}
return 1;
}
int query(zb x, zb y, int root) {
if (inside_blog_blog(x, y, tree[root])) {//整个矩阵都在里面，它里面所有点的权值直接加
return tree[root].valsum;
}
int re = 0;
if (inside_blog_point(x, y, tree[root].a)) re += tree[root].a.val;//这个点在，加上这个点权值
if (touch_blog_blog(x, y, tree[tree[root].l])) re += query(x, y, tree[root].l);//看左右两个儿子
if (touch_blog_blog(x, y, tree[tree[root].r])) re += query(x, y, tree[root].r);
return re;
}
int main() {
scanf("%d", &n);
scanf("%d", &op);
while (op != 3) {
scanf("%d %d", &x.w[0], &x.w[1]);
x.w[0] ^= lastans;
x.w[1] ^= lastans;
if (op == 1) {
scanf("%d", &x.val);
x.val ^= lastans;
insert(x, root, 0);
}
else {
scanf("%d %d", &y.w[0], &y.w[1]);
y.w[0] ^= lastans;
y.w[1] ^= lastans;
lastans = query(x, y, root);
printf("%d
", lastans);
}
scanf("%d", &op);
}
return 0;
}