nth_element(b + l, b + mid, b + r + 1,
[dep](int x, int y) { return tr[x].x[dep] < tr[y].x[dep]; });
和
nth_element(b + l, b + p, b + r + 1,
[dep](int x, int y) { return tr[x].x[dep] < tr[y].x[dep]; });
这一段代码一样(mid和p只是变量名不同),但是我在编译前一个的时候出现了问题,求问为什么
全部代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5, LG = 20;
struct node {
int x[2], val, sum;
int xl[2], xr[2], l, r;
node() {
}
node(int X, int Y, int v) {
x[0] = X, x[1] = Y, val = sum = v;
xr[0] = xl[0] = X, xl[1] = xr[1] = Y;
l = r = 0;
}
};
struct KDT {
node tr[maxn];
int tot, rt[maxn];
void pushup(int t) {
tr[t].sum = tr[tr[t].l].sum + tr[tr[t].r].sum + tr[t].val;
for (int k = 0; k <= 1; k++) {
tr[t].xl[k] = tr[t].xr[k] = tr[t].x[k];
if(tr[t].l) {
tr[t].xl[k] = min(tr[t].xl[k], tr[tr[t].l].xl[k]);
tr[t].xr[k] = max(tr[t].xr[k], tr[tr[t].l].xr[k]);
}
if(tr[t].r) {
tr[t].xl[k] = min(tr[t].xl[k], tr[tr[t].r].xl[k]);
tr[t].xr[k] = max(tr[t].xr[k], tr[tr[t].r].xr[k]);
}
}
}
int b[maxn], cnt;
int build(int l, int r, int dep) {
int mid = l + r >> 1;
nth_element(b + l, b + mid, b + r + 1,
[dep](int x, int y) { return tr[x].x[dep] < tr[y].x[dep]; });
int x = b[mid];
if(l < mid)
tr[x].l = build(l, mid - 1, dep ^ 1);
if(mid < r)
tr[x].r = build(mid + 1, r, dep ^ 1);
pushup(x);
return x;
}
void assign(int &p) {
if(!p)
return ;
b[++cnt] = p;
assign(tr[p].l);
assign(tr[p].r);
p = 0;
}
node ql, qr;
int query(int p) {
if(!p)
return 0;
bool f = 0;
for (int k = 0; k <= 1; k++)
f &= (!(ql.x[k] <= tr[p].xl[k] && tr[p].xr[k] <= qr.x[k]));
if(!f)
return tr[p].sum;
for (int k = 0; k <= 1; k++)
if(tr[p].xr[k] < ql.x[k] || tr[p].xl[k] > qr.x[k])
return 0;
int ans = 0;
f = 0;
for (int k = 0; k <= 1; k++)
f &= (!(ql.x[k] <= tr[p].x[k] && tr[p].x[k] <= qr.x[k]));
if(!f)
ans = tr[p].val;
return ans + query(tr[p].l) + query(tr[p].r);
}
void add(int x, int y, int val) {
tr[++tot] = node(x, y, val);
b[cnt = 1] = tot;
for (int sz = 0; ; sz++) {
if(!rt[sz]) {
rt[sz] = build(1, cnt, 0);
break;
}
assign(rt[sz]);
}
}
int query(int fx, int fy, int ex, int ey) {
ql.x[0] = fx, ql.x[1] = fy;
qr.x[0] = ex, qr.x[1] = ey;
int ans = 0;
for (int i = 0; i <= LG; i++)
ans += query(rt[i]);
return ans;
}
} tree;
int n;
int main() {
cin >> n;
int lst = 0;
while(1) {
int op;
cin >> op;
if(op == 1) {
int x, y, v;
cin >> x >> y >> v;
x ^= lst, y ^= lst, v ^= lst;
tree.add(x, y, v);
}
else if(op == 2) {
int fx, fy, ex, ey;
cin >> fx >> fy >> ex >> ey;
fx ^= lst, ex ^= lst;
fy ^= lst, ey ^= lst;
cout << (lst = tree.query(fx, fy, ex, ey)) << endl;
}
else
break;
}
return 0;
}
正确代码:
#include <bits/stdc++.h>
using namespace std;
constexpr int N(2e5), LG{18};
struct pt {
int x[2];
int v, sum;
int l, r;
int L[2], R[2];
} tr[N + 5], l, h;
int rt[LG];
int b[N + 5], cnt;
void upd(int p) {
tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum + tr[p].v;
for (int k : {0, 1}) {
tr[p].L[k] = tr[p].R[k] = tr[p].x[k];
if (tr[p].l) {
tr[p].L[k] = min(tr[p].L[k], tr[tr[p].l].L[k]);
tr[p].R[k] = max(tr[p].R[k], tr[tr[p].l].R[k]);
}
if (tr[p].r) {
tr[p].L[k] = min(tr[p].L[k], tr[tr[p].r].L[k]);
tr[p].R[k] = max(tr[p].R[k], tr[tr[p].r].R[k]);
}
}
}
int build(int l, int r, int dep = 0) {
int p{l + r >> 1};
nth_element(b + l, b + p, b + r + 1,
[dep](int x, int y) { return tr[x].x[dep] < tr[y].x[dep]; });
int x{b[p]};
if (l < p) tr[x].l = build(l, p - 1, dep ^ 1);
if (p < r) tr[x].r = build(p + 1, r, dep ^ 1);
upd(x);
return x;
}
void append(int &p) {
if (!p) return;
b[++cnt] = p;
append(tr[p].l);
append(tr[p].r);
p = 0;
}
int query(int p) {
if (!p) return 0;
bool flag{false};
for (int k : {0, 1}) flag |= (!(l.x[k] <= tr[p].L[k] && tr[p].R[k] <= h.x[k]));
if (!flag) return tr[p].sum;
for (int k : {0, 1})
if (tr[p].R[k] < l.x[k] || h.x[k] < tr[p].L[k]) return 0;
int ans{0};
flag = false;
for (int k : {0, 1}) flag |= (!(l.x[k] <= tr[p].x[k] && tr[p].x[k] <= h.x[k]));
if (!flag) ans = tr[p].v;
return ans += query(tr[p].l) + query(tr[p].r);
}
int main() {
int n;
cin >> n;
int lst{0};
n = 0;
while (true) {
int op;
cin >> op;
if (op == 1) {
int x, y, A;
cin >> x >> y >> A;
x ^= lst;
y ^= lst;
A ^= lst;
tr[++n] = {{x, y}, A};
b[cnt = 1] = n;
for (int sz{0};; ++sz)
if (!rt[sz]) {
rt[sz] = build(1, cnt);
break;
} else
append(rt[sz]);
} else if (op == 2) {
cin >> l.x[0] >> l.x[1] >> h.x[0] >> h.x[1];
l.x[0] ^= lst;
l.x[1] ^= lst;
h.x[0] ^= lst;
h.x[1] ^= lst;
lst = 0;
for (int i{0}; i < LG; ++i) lst += query(rt[i]);
cout << lst << "\n";
} else
break;
}
return 0;
}
编译信息错误为 'this' was not captured for this lambda function