题面
题解
因为强制在线，所以我们不能$cdq$分治，所以考虑用$KDT$，$KDT$维护一个矩阵，然后询问的时候如果当前矩形在询问区间内，直接记贡献，否则判断当前点是否在矩阵内，然后左右分别递归下去判断就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::nth_element;
typedef long long ll;
template<typename T>
void read(T &x) {
int flag = 1; x = 0; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}
const int N = 200005;
int n, x1, x2, y1, y2, k, ans, rt, WD, top, cnt, rub[N];
struct poi { int x[2], w; } p[N];
struct node { int mi[2], mx[2], sum, lc, rc, siz; poi tp; } t[N];
int operator < (const poi &a, const poi &b) { return a.x[WD] < b.x[WD]; }
inline int newnode() { if(top) return rub[top--]; else return ++cnt; }
void up(int k) {
int l = t[k].lc, r = t[k].rc;
for(int i = 0; i < 2; ++i) {
t[k].mi[i] = t[k].mx[i] = t[k].tp.x[i];
if(l) t[k].mi[i] = min(t[k].mi[i], t[l].mi[i]), t[k].mx[i] = max(t[k].mx[i], t[l].mx[i]);
if(r) t[k].mi[i] = min(t[k].mi[i], t[r].mi[i]), t[k].mx[i] = max(t[k].mx[i], t[r].mx[i]);
}
t[k].sum = t[l].sum + t[r].sum + t[k].tp.w, t[k].siz = t[l].siz + t[r].siz + 1;
}
int build(int l, int r, int wd) {
if(l > r) return 0;
int mid = (l + r) >> 1, k = newnode();
WD = wd, nth_element(p + l, p + mid, p + r + 1), t[k].tp = p[mid];
t[k].lc = build(l, mid - 1, wd ^ 1), t[k].rc = build(mid + 1, r, wd ^ 1);
up(k); return k;
}
void pia(int k, int num) {
if(t[k].lc) pia(t[k].lc, num);
p[t[t[k].lc].siz + num + 1] = t[k].tp, rub[++top] = k;
if(t[k].rc) pia(t[k].rc, num + t[t[k].lc].siz + 1);
}
void check(int &k, int wd) {
if(0.75 * t[k].siz < t[t[k].lc].siz || 0.75 * t[k].siz < t[t[k].rc].siz)
pia(k, 0), k = build(1, t[k].siz, wd);
}
void insert(int &k, poi tmp, int wd) {
if(!k) { k = newnode(), t[k].lc = t[k].rc = 0, t[k].tp = tmp, up(k); return ; }
if(tmp.x[wd] <= t[k].tp.x[wd]) insert(t[k].lc, tmp, wd ^ 1);
else insert(t[k].rc, tmp, wd ^ 1);
up(k), check(k, wd);
}
int in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2) { return (X1>=x1&&X2<=x2&&Y1>=y1&&Y2<=y2); }
int out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2) { return (x1>X2||x2<X1||y1>Y2||y2<Y1); }
int query(int k, int x1, int y1, int x2 ,int y2) {
if(!k) return 0;
int ret = 0;
if(in(x1, y1, x2, y2, t[k].mi[0], t[k].mi[1], t[k].mx[0], t[k].mx[1])) return t[k].sum;
if(out(x1, y1, x2, y2, t[k].mi[0], t[k].mi[1], t[k].mx[0], t[k].mx[1])) return 0;
if(in(x1, y1, x2, y2, t[k].tp.x[0], t[k].tp.x[1], t[k].tp.x[0], t[k].tp.x[1])) ret += t[k].tp.w;
return ret + query(t[k].lc, x1, y1, x2, y2) + query(t[k].rc, x1, y1, x2, y2);
}
int main () {
read(n);
while(true) {
int opt; read(opt);
if(opt == 3) break;
else {
read(x1), read(y1), x1 ^= ans, y1 ^= ans;
if(opt == 1) read(k), insert(rt, (poi){x1, y1, k ^ ans}, 0);
else {
read(x2), read(y2), x2 ^= ans, y2 ^= ans;
ans = query(rt, x1, y1, x2, y2), printf("%d
", ans);
}
}
}
return 0;
}