[BZOJ4822] [CQOI2017] 老C的任务

题目链接

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;

}