COJ969 WZJ的数据结构(负三十一)

时间:2023-01-17 16:42:23
WZJ的数据结构(负三十一)
难度级别:D; 运行时间限制:3000ms; 运行空间限制:262144KB; 代码长度限制:2000000B
试题描述
A国有两个主基站,供给全国的资源。定义一个主基站能覆盖的范围为:以该主基站为圆心,半径为r的圆(包括边界)。
如果一个子基站能被一个主基站覆盖,则它是激活的。
有N个事件,事件分两种:
1.新建一个坐标位于(x,y)的子基站。 
2.给出两个主基站的半径:r1、r2。询问处于非激活状态的子基站个数。
输入
第一行是四个正整数:x1、y1、x2、y2。表示两个主基站的坐标是(x1,y1)和(x2,y2)。
第二行是一个正整数N,表示有N个事件。
接下来的N行,每行三个正整数。
如果第一个数为1,则接下来两个数为x,y,表示新建一个坐标为(x,y)的新基站。
如果第一个数为2,则接下来两个数为r1,r2,表示询问当两个主基站的覆盖半径为r1和r2时,处于非激活状态的子基站数。
输出
对于每个询问输出答案。
输入示例
1 10 5 2
10
1 2 6
1 1 9
1 3 8
1 6 7
1 4 12
2 1 1
2 3 2
2 8 2
2 2 2
2 3 2
输出示例
4
3
0
4
3
其他说明
1<=x1,y1,x2,y2,x,y,r1,r2<=10^9
1<=N<=200000

妈妈我会写线段树分治了!

按论文的方法,操作对应一个时间区间,将这个区间打上标记,那么操作的标记数是O(nlogn)的,询问对应一个点,将点所在的区间打上标记,那么询问的标记数也是O(nlogn)的。最后对每一条线段离线做就可以了。

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
ll x0,y0,x1,y1,tmp[maxn];
int n,N,first1[maxn*],next1[maxn*],id1[maxn*],ToT1;
int first2[maxn*],next2[maxn*],id2[maxn*],ToT2;
struct Query {
int tp,id;
ll x,y;
}Q[maxn];
struct Point {
ll x,y;int id;
bool operator < (const Point& a) const {
if(x!=a.x) return x>a.x;
if(y!=a.y) return y>a.y;
}
}A[maxn];
void pre() {
rep(i,,n) tmp[i]=-Q[i].y;
sort(tmp+,tmp+n+);
rep(i,,n) Q[i].y=lower_bound(tmp+,tmp+n+,-Q[i].y)-tmp;
}
int ans[maxn],sumv[maxn];
void add(int x,int v) {for(;x<=n;x+=x&-x) sumv[x]+=v;}
int sum(int x) {int res=;for(;x;x-=x&-x) res+=sumv[x];return res;}
void query1(int o,int l,int r,int ql,int qr,int v) {
if(ql<=l&&r<=qr) {
id1[++ToT1]=v;next1[ToT1]=first1[o];first1[o]=ToT1;
}
else {
int mid=l+r>>,lc=o<<,rc=lc|;
if(ql<=mid) query1(lc,l,mid,ql,qr,v);
if(qr>mid) query1(rc,mid+,r,ql,qr,v);
}
}
void query2(int o,int l,int r,int x,int v) {
id2[++ToT2]=v;next2[ToT2]=first2[o];first2[o]=ToT2;
if(l==r) return;
int mid=l+r>>,lc=o<<,rc=lc|;
if(x<=mid) query2(lc,l,mid,x,v);
else query2(rc,mid+,r,x,v);
}
int main() {
x0=read();y0=read();x1=read();y1=read();
n=read();
rep(i,,n) {
Q[Q[i].id=i].tp=read();
ll x=read(),y=read();
if(Q[i].tp==) {
Q[i].x=(x-x0)*(x-x0)+(y-y0)*(y-y0),Q[i].y=(x-x1)*(x-x1)+(y-y1)*(y-y1);
query1(,,n,i,n,i);
}
else {
Q[i].x=x*x,Q[i].y=y*y;
query2(,,n,i,i);
}
}
pre();
rep(i,,*n) {
int m=;
for(int j=first2[i];j;j=next2[j]) A[++m]=(Point){Q[id2[j]].x,Q[id2[j]].y,Q[id2[j]].id};
for(int j=first1[i];j;j=next1[j]) A[++m]=(Point){Q[id1[j]].x,Q[id1[j]].y,};
sort(A+,A+m+);
rep(j,,m) if(!A[j].id) add(A[j].y,); else ans[A[j].id]+=sum(A[j].y-);
rep(j,,m) if(!A[j].id) add(A[j].y,-);
}
rep(i,,n) if(Q[i].tp==) printf("%d\n",ans[i]);
return ;
}

CDQ分治常数比较小:

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
ll x0,y0,x1,y1,tmp[maxn];
struct Query {
int tp,id;
ll x,y;
}Q[maxn];
struct Point {
ll x,y;int id;
bool operator < (const Point& a) const {
if(x!=a.x) return x>a.x;
if(y!=a.y) return y>a.y;
}
}A[maxn];
int n,ans[maxn],sumv[maxn];
void add(int x,int v) {for(;x<=n;x+=x&-x) sumv[x]+=v;}
int sum(int x) {int res=;for(;x;x-=x&-x) res+=sumv[x];return res;}
void solve(int L,int R) {
if(L>=R) return;
int mid=L+R>>,m0=,m=;
solve(L,mid);solve(mid+,R);
rep(i,L,mid) if(Q[i].tp==) A[++m0]=(Point){Q[i].x,Q[i].y,};
if(!m0) return;m=m0;
rep(i,mid+,R) if(Q[i].tp==) A[++m0]=(Point){Q[i].x,Q[i].y,Q[i].id};
if(m0==m) return;m=m0;
sort(A+,A+m+);
rep(i,,m) if(!A[i].id) add(A[i].y,); else ans[A[i].id]+=sum(A[i].y-);
rep(i,,m) if(!A[i].id) add(A[i].y,-);
}
void pre() {
rep(i,,n) tmp[i]=-Q[i].y;
sort(tmp+,tmp+n+);
rep(i,,n) Q[i].y=lower_bound(tmp+,tmp+n+,-Q[i].y)-tmp;
}
int main() {
x0=read();y0=read();x1=read();y1=read();
n=read();
rep(i,,n) {
Q[Q[i].id=i].tp=read();
ll x=read(),y=read();
if(Q[i].tp==) Q[i].x=(x-x0)*(x-x0)+(y-y0)*(y-y0),Q[i].y=(x-x1)*(x-x1)+(y-y1)*(y-y1);
else Q[i].x=x*x,Q[i].y=y*y;
}
pre();solve(,n);
rep(i,,n) if(Q[i].tp==) printf("%d\n",ans[i]);
return ;
}

COJ969 WZJ的数据结构(负三十一)的更多相关文章

  1. COJ 1003 WZJ的数据结构(三)ST表

    WZJ的数据结构(三) 难度级别:B: 运行时间限制:3000ms: 运行空间限制:51200KB: 代码长度限制:2000000B 试题描述 请你设计一个数据结构,完成以下功能: 给定一个大小为N的 ...

  2. COJ 0979 WZJ的数据结构(负二十一)

    WZJ的数据结构(负二十一) 难度级别:C: 运行时间限制:5000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 请你实现一个数据结构,完成这样的功能: 给你一个 ...

  3. &lbrack;COJ0989&rsqb;WZJ的数据结构(负十一)

    [COJ0989]WZJ的数据结构(负十一) 试题描述 给出以下定义: 1.若子序列[L,R]的极差(最大值-最小值)<=M,则子序列[L,R]为一个均匀序列. 2.均匀序列[L,R]的权值为S ...

  4. COJ966 WZJ的数据结构(负三十四)

    WZJ的数据结构(负三十四) 难度级别:C: 运行时间限制:20000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 给一棵n个节点的树,请对于形如"u  ...

  5. COJ967 WZJ的数据结构(负三十三)

    WZJ的数据结构(负三十三) 难度级别:C: 运行时间限制:7000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 请你设计一个数据结构,完成以下功能: 给定一个大 ...

  6. COJ970 WZJ的数据结构(负三十)

    WZJ的数据结构(负三十) 难度级别:D: 运行时间限制:1000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 给你一棵N个点的无根树,点和边上均有权值.请你设计 ...

  7. COJ968 WZJ的数据结构(负三十二)

    WZJ的数据结构(负三十二) 难度级别:D: 运行时间限制:5000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 给你一棵N个点的无根树,边上均有权值,每个点上有 ...

  8. COJ 0967 WZJ的数据结构(负三十三)

    WZJ的数据结构(负三十三) 难度级别:E: 运行时间限制:7000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 请你设计一个数据结构,完成以下功能: 给定一个大 ...

  9. COJ 0970 WZJ的数据结构(负三十)树分治

    WZJ的数据结构(负三十) 难度级别:D: 运行时间限制:1000ms: 运行空间限制:262144KB: 代码长度限制:2000000B 试题描述 给你一棵N个点的无根树,点和边上均有权值.请你设计 ...

随机推荐

  1. 部署Redis for Windows服务

    一.环境 Redis Windows 版本:2.8.2104 二.植入Windows服务    > redis-server.exe --service-install redis.window ...

  2. mongodb目录

    1. mongodb 数据库操作--备份 还原 导出 导入 2. ubuntu下mongodb启动脚本 3. mongodb实现远程连接 4. 用java在客户端读取mongodb中的数据并发送至服务 ...

  3. android146 360 病毒查杀

    <?xml version="1.0" encoding="utf-8"?> <LinearLayout xmlns:android=&quo ...

  4. OC5&lowbar;NSFileManger

    // // main.m // OC5_NSFileManger // // Created by zhangxueming on 15/6/19. // Copyright (c) 2015年 zh ...

  5. linux系统目录介绍

    目录/文件 用途 来源 / /处于Linux文件系统树形结构的最顶端,它是Linux文件系统的入口,所有的目录.文件.设备都在/之下. - /bin 该目录存放着系统最常用的最重要的命令,相当于DOS ...

  6. paip&period;c&plus;&plus; qt messagebox用法

    paip.c++ qt messagebox用法 作者Attilax ,  EMAIL:1466519819@qq.com  来源:attilax的专栏 地址:http://blog.csdn.net ...

  7. java学习之网络编程之echo程序

    服务端的实现 package com.gh.echo; import java.io.*; import java.net.*; /** * echo服务器程序 * 实现 不断接收字符串 ,然后返回一 ...

  8. 几个可用于数据挖掘和统计分析的java库

    http://itindex.net/blog/2015/01/09/1420751820000.html WEKA:WEKA是一个可用于数据挖掘任务的机器学习算法集合.该算法可以直接应用到数据集或从 ...

  9. MVC 视图-模型,动态更新

    <!DOCTYPE html> <html> <head> <title>Binding</title> <script src=&q ...

  10. 实验十一 团队作业7---团队项目设计完善&amp&semi;编码测试

    团队软件项目设计完善: 任务1:根据OOD详细设计工作要点,修改完善团队项目系统设计说明书和详细设计说明. <软件设计方案说明书>:https://github.com/cy0325/Te ...