题目链接
BZOJ:https://lydsy.com/JudgeOnline/problem.php?id=4822.
洛谷:https://www.luogu.org/problemnew/show/P3755.
Solution
直接上\(kd\_tree\)就好了。
为啥我觉得bzoj机子比洛谷快些
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
#define ll long long
void print(ll x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(ll x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int maxn = 2e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
int n,Q,rt,D;
struct data {ll sum;int ls,rs,mx[2],mn[2],p[2],val;}a[maxn],t;
void up(int x) {
int ls=a[x].ls,rs=a[x].rs;
if(ls) FOR(i,0,1) {
a[x].mn[i]=min(a[x].mn[i],a[ls].mn[i]);
a[x].mx[i]=max(a[x].mx[i],a[ls].mx[i]);
}
if(rs) FOR(i,0,1) {
a[x].mn[i]=min(a[x].mn[i],a[rs].mn[i]);
a[x].mx[i]=max(a[x].mx[i],a[rs].mx[i]);
}
a[x].sum=a[x].val+a[ls].sum+a[rs].sum;
}
int cmp(data x,data y) {return x.p[D]<y.p[D];}
int build(int d,int l,int r) {
int mid=(l+r)>>1;D=d;nth_element(a+l+1,a+mid+1,a+r+1,cmp);
FOR(i,0,1) a[mid].mn[i]=a[mid].mx[i]=a[mid].p[i];
if(l<mid) a[mid].ls=build(!d,l,mid-1);
if(r>mid) a[mid].rs=build(!d,mid+1,r);
up(mid);return mid;
}
int in(int x) {
FOR(i,0,1) if(a[x].mn[i]<t.mn[i]||a[x].mx[i]>t.mx[i]) return 0;
return 1;
}
int out(int x) {
FOR(i,0,1) if(a[x].mn[i]<t.mx[i]&&a[x].mx[i]>t.mn[i]) return 0;
return 1;
}
int cover(int x) {
FOR(i,0,1) if(a[x].p[i]>t.mx[i]||a[x].p[i]<t.mn[i]) return 0;
return 1;
}
ll query(int x) {
if(!x) return 0;
if(in(x)) return a[x].sum;
if(out(x)) return 0;
int res=0;
if(cover(x)) res+=a[x].val;
return res+query(a[x].ls)+query(a[x].rs);
}
int main() {
read(n),read(Q);FOR(i,1,n) read(a[i].p[0]),read(a[i].p[1]),read(a[i].val);
rt=build(0,1,n);
FOR(i,1,Q) {
read(t.mn[0]),read(t.mn[1]),read(t.mx[0]),read(t.mx[1]);
write(query(rt));
}
return 0;
}