太难了
2025-09-13 16:39:09
发布于:四川
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct pt{
int x,y,t;
};
struct node{
int x,y,t,minx,maxx,miny,maxy,mint,maxt,sz;
bool vis;
node *l,*r;
node(pt p){
x = p.x;
y = p.y;
t = p.t;
minx = maxx = x;
miny = maxy = y;
mint = maxt = t;
sz = 1;
vis = 0;
l = r = NULL;
}
void change(){
if(vis){
minx = miny = mint = 0x3f3f3f3f;
maxx = maxy = maxt = -0x3f3f3f3f;
sz = 0;
}else{
minx = maxx = x;
miny = maxy = y;
mint = maxt = t;
sz = 1;
}
if(l && l -> sz > 0){
minx = min(minx,l -> minx);
maxx = max(maxx,l -> maxx);
miny = min(miny,l -> miny);
maxy = max(maxy,l -> maxy);
mint = min(mint,l -> mint);
maxt = max(maxt,l -> maxt);
sz += l -> sz;
}
if(r && r -> sz > 0){
minx = min(minx,r -> minx);
maxx = max(maxx,r -> maxx);
miny = min(miny,r -> miny);
maxy = max(maxy,r -> maxy);
mint = min(mint,r -> mint);
maxt = max(maxt,r -> maxt);
sz += r -> sz;
}
}
};
node *upd(node *nd,pt p,int dep = 0){
if(nd == NULL) return new node(p);
if(dep % 2 == 0){
if(p.x < nd -> x) nd -> l = upd(nd -> l,p,dep + 1);
else nd -> r = upd(nd -> r,p,dep + 1);
}else{
if(p.y < nd -> y) nd -> l = upd(nd -> l,p,dep + 1);
else nd -> r = upd(nd -> r,p,dep + 1);
}
nd -> change();
return nd;
}
int query(node *nd,int x1,int x2,int y1,int y2,int cur){
if(nd == NULL || nd -> sz == 0) return 0;
if(nd -> maxx < x1 || nd -> minx > x2 || nd -> maxy < y1 || nd -> miny > y2) return 0;
if(nd -> mint > cur) return 0;
int cnt = 0;
if(!nd -> vis){
if(nd -> x >= x1 && nd -> x <= x2 && nd -> y >= y1 && nd -> y <= y2 && nd -> t <= cur){
cnt++;
nd -> vis = 1;
}
}
cnt += query(nd -> l,x1,x2,y1,y2,cur);
cnt += query(nd -> r,x1,x2,y1,y2,cur);
nd -> change();
return cnt;
}
signed main(){
int n,m,q; cin >> n >> m >> q;
node *root = NULL;
for(int i = 1;i <= q;i++){
int op; cin >> op;
if(op == 1){
int x,y,k; cin >> x >> y >> k;
root = upd(root,{x,y,i + k});
}else{
int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
cout << query(root,x1,x2,y1,y2,i) << "\n";
}
}
return 0;
}
这里空空如也
有帮助,赞一个