@[5k_sync_closer](/user/388651)
by Nt_Tsumiki @ 2024-02-20 22:16:27
@[5k_sync_closer](/user/388651)
by Blue_Poison @ 2024-02-20 22:22:35
我与洛谷有不共戴天之仇
by yanyanghu @ 2024-02-20 22:44:51
目前调出来一个错，是判断当前矩形是否与询问矩形有交的 check 锅了
最新版 code：
```cpp
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,block;
struct KD_tree {
#define N 200001
struct Point;
struct Tree;
const double A=0.75;
int tcnt,flatcnt,rt,rubcnt,rub[N];
struct Point {
int c[2],val;
int operator[](int x) { return c[x]; }
void operator=(Tree tr) { c[0]=tr[0],c[1]=tr[1],val=tr.val; }
}p[N];
struct Tree {
int l,r,val,sum,c[2],maxn[2],minn[2],siz;
int operator[](int x) { return c[x]; }
void operator=(Point poi) { val=poi.val,c[0]=poi[0],c[1]=poi[1],l=r=sum=maxn[0]=maxn[1]=minn[0]=minn[1]=siz=0; }
}t[N];
void upd(int x) {
t[x].sum=(t[x].l?t[t[x].l].sum:0)+(t[x].r?t[t[x].r].sum:0)+t[x].val;
t[x].siz=(t[x].l?t[t[x].l].siz:0)+(t[x].r?t[t[x].r].siz:0)+1;
t[x].maxn[0]=t[x].minn[0]=t[x][0],t[x].maxn[1]=t[x].minn[1]=t[x][1];
for (int i:{0,1}) {
if (t[x].l) t[x].maxn[i]=max(t[x].maxn[i],t[t[x].l].maxn[i]),
t[x].minn[i]=min(t[x].minn[i],t[t[x].l].minn[i]);
if (t[x].r) t[x].maxn[i]=max(t[x].maxn[i],t[t[x].r].maxn[i]),
t[x].minn[i]=min(t[x].minn[i],t[t[x].r].minn[i]);
}
}
void build(int &x,int l,int r,int d) {
int mid=(l+r)>>1; x=rub[rubcnt--];
nth_element(p+l,p+mid,p+r+1,[d](Point p1,Point p2){ return p1[d]<p2[d]; });
t[x]=p[mid];
if (l<mid) build(t[x].l,l,mid-1,d^1);
if (r>mid) build(t[x].r,mid+1,r,d^1);
upd(x);
}
bool check_poi_cap_squ(int x,Point poi) {
if (poi[0]>=t[x].minn[0] and poi[1]>=t[x].minn[1]) return 1;
return 0;
}
bool check_squ_in_poi(int x,Point poi) {
if (poi[0]>=t[x].maxn[0] and poi[1]>=t[x].maxn[1]) return 1;
return 0;
}
int ask(int x,Point poi) {
if (!x) return 0;
if (check_squ_in_poi(x,poi)) return t[x].sum;
int res=0;
if (check_poi_cap_squ(t[x].l,poi)) res+=ask(t[x].l,poi);
if (check_poi_cap_squ(t[x].r,poi)) res+=ask(t[x].r,poi);
return res;
}
void flat(int x) {
p[++flatcnt]=t[x],rub[++rubcnt]=x;
if (t[x].l) flat(t[x].l);
if (t[x].r) flat(t[x].r);
}
void ins(int &x,Point poi,int d) {
if (!x) {
t[x=rub[rubcnt--]]=poi;
upd(x);
return;
}
if (poi[d]<=t[x][d]) ins(t[x].l,poi,d^1);
else ins(t[x].r,poi,d^1);
upd(x);
if (A*t[x].siz<(double)t[t[x].l].siz or A*t[x].siz<(double)t[t[x].r].siz) {
flatcnt=0;
flat(t[x].siz); build(x,1,flatcnt,0);
}
}
void ins(int x,int y,int k) { ins(rt,Point{{x,y},k},0); }
int ask(int x,int y) { return ask(rt,Point{{x,y},0}); }
void init() { for (int i=1;i<N;i++) rub[++rubcnt]=i; }
#undef N
}t;
int main() {
scanf("%d",&n); block=sqrt(n);
t.init();
int op,x1,y1,x2,y2,k,las=0;
while (1) {
scanf("%d",&op);
if (op==1) {
scanf("%d%d%d",&x1,&y1,&k);
x1^=las,y1^=las,k^=las;
t.ins(x1,y1,k);
} else if (op==2) {
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1^=las,y1^=las,x2^=las,y2^=las;
printf("%d\n",las=t.ask(x2,y2)-t.ask(x1-1,y2)-t.ask(x2,y1-1)+t.ask(x1-1,y1-1));
} else break;
}
return 0;
}
```
by Nt_Tsumiki @ 2024-02-21 06:20:37
@[Nt_Tsumiki](/user/420129)
1. ask 中要考虑自己的贡献
```cpp
int ask(int x, Point poi)
{
if (!x)
return 0;
if (check_squ_in_poi(x, poi))
return t[x].sum;
int res = 0;
if (t[x].c[0] <= poi.c[0] && t[x].c[1] <= poi.c[1])
res += t[x].val; //加上这句
if (check_poi_cap_squ(t[x].l, poi))
res += ask(t[x].l, poi);
if (check_poi_cap_squ(t[x].r, poi))
res += ask(t[x].r, poi);
return res;
}
```
2. 唐氏错误，88 行 `flat(t[x].siz);` 应为 `flat(x);`
by 5k_sync_closer @ 2024-02-21 08:55:25
@[5k_sync_closer](/user/388651) 这下糖完了
by Nt_Tsumiki @ 2024-02-21 08:56:32