[BZOJ4822] [CQOI2017] 老C的任务
2024-08-31 22:14:59
题目链接
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;
}
最新文章
- MYSQL命令行使用指南
- 0x7c95caa2指令引用的0x00000000内存 该内存不能read
- Guid算法与标识列(自动增长字段)在表中的应用
- WPF外包公司——北京动点飞扬软件:开发企业WPF项目需要掌握些什么
- WordPress HOOK机制原理及代码分析
- Windows下Qt连接MySql数据库
- php的redis 操作类,适用于单台或多台、多组redis服务器操作
- PAT 1017
- 文件正在上传的转圈圈gif图片引出的fixed定位和absolute定位
- 阿里云 centos 部署javaweb 应用
- JS控制文本框中的密码显示/隐藏功能
- HDU 4735 Little Wish~ lyrical step~(DLX , 反复覆盖)
- 在world中批量调整图片的大小
- 57、Bootstrap中文文档
- Android调试工具之ADB
- dubbo搭建
- date(&#39;Y-m-d H:i:s&#39;,time()) 与 date(&#39;Y-m-d h:i:s&#39;,time())区别是什么
- 单元测试系列之七:Sonar 数据库表关系整理一(rule相关)
- string、const char*、 char* 、char[]相互转换
- Python之matplotlib库学习