CF369E Valera and Queries kdtree
2024-10-06 07:06:17
给你一堆线段,求:一个区间内包含的本质不同线段种类数(只要线段有一部分在区间中就算是包含)
考虑容斥:总线段数-被那些没有询问的区间完全覆盖的数量.
用离线+树状数组数点或者 KDtree 数点即可.
#include <bits/stdc++.h>
#define N 300005
using namespace std;
void setIO(string s)
{
string in=s+".in";
string out=s+".out";
freopen(in.c_str(),"r",stdin);
// freopen(out.c_str(),"w",stdout);
}
namespace kd
{
int d;
struct node
{
int ch[2],p[2],minv[2],maxv[2],sum,w;
}t[N];
bool cmp(node a,node b)
{
return a.p[d]==b.p[d]?a.p[d^1]<b.p[d^1]:a.p[d]<b.p[d];
}
int isin(int p,int x1,int y1,int x2,int y2)
{
return t[p].minv[0]>=x1&&t[p].maxv[0]<=x2&&t[p].minv[1]>=y1&&t[p].maxv[1]<=y2;
}
int isout(int p,int x1,int y1,int x2,int y2)
{
return t[p].maxv[0]<x1||t[p].minv[0]>x2||t[p].maxv[1]<y1||t[p].minv[1]>y2;
}
void pushup(int x,int y)
{
t[x].sum+=t[y].sum;
for(int i=0;i<2;++i)
{
t[x].minv[i]=min(t[x].minv[i],t[y].minv[i]);
t[x].maxv[i]=max(t[x].maxv[i],t[y].maxv[i]);
}
}
int build(int l,int r,int o)
{
d=o;
int mid=(l+r)>>1;
nth_element(t+l,t+mid,t+1+r,cmp);
for(int i=0;i<2;++i) t[mid].minv[i]=t[mid].maxv[i]=t[mid].p[i];
t[mid].sum=1;
t[mid].ch[0]=t[mid].ch[1]=0;
if(mid>l) t[mid].ch[0]=build(l,mid-1,o^1),pushup(mid,t[mid].ch[0]);
if(r>mid) t[mid].ch[1]=build(mid+1,r,o^1),pushup(mid,t[mid].ch[1]);
return mid;
}
int query(int p,int x1,int y1,int x2,int y2)
{
if(isin(p,x1,y1,x2,y2)) return t[p].sum;
if(isout(p,x1,y1,x2,y2)) return 0;
int re=(t[p].p[0]>=x1&&t[p].p[0]<=x2&&t[p].p[1]>=y1&&t[p].p[1]<=y2);
if(t[p].ch[0]) re+=query(t[p].ch[0],x1,y1,x2,y2);
if(t[p].ch[1]) re+=query(t[p].ch[1],x1,y1,x2,y2);
return re;
}
};
namespace IO
{
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {int x=0; char c=nc(); while(c<48) c=nc(); while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x;}
};
int arr[N];
int main()
{
// setIO("input");
int n,m,i,j,root;
n=IO::rd(),m=IO::rd();
for(i=1;i<=n;++i)
kd::t[i].p[0]=IO::rd(),kd::t[i].p[1]=IO::rd();
// scanf("%d%d",&kd::t[i].p[0],&kd::t[i].p[1]);
root=kd::build(1,n,0);
for(i=1;i<=m;++i)
{
int k=IO::rd(),re=0;
// scanf("%d",&k);
for(j=1;j<=k;++j) arr[j]=IO::rd();
arr[0]=0,arr[k+1]=1000002;
for(j=0;j<=k;++j)
{
if(arr[j+1]>arr[j]+1)
{
re+=kd::query(root,arr[j]+1,arr[j]+1,arr[j+1]-1,arr[j+1]-1);
}
}
printf("%d\n",n-re);
}
return 0;
}
最新文章
- 从零自学Hadoop(16):Hive数据导入导出,集群数据迁移上
- ListView的属性及方法详解
- python flask应用部署
- Linux设备模型(总线、设备、驱动程序和类)
- C++primer 阅读点滴记录(一)
- Linux 系统中用户切换(su user与 su - user 的区别)
- js一些方法的扩展
- Live555 Streaming from a live source
- Log4J使用笔记(转)
- 框架开发(三)---smarty整合
- docker !veth
- Android开发中的OpenCV霍夫直线检测(Imgproc.HoughLines()&;Imgproc.HoughLinesP())
- Python 编程规范
- Android 混淆那些事儿
- 关于Oracle数据库故障诊断基础架构
- eclipse maven引入第三方jar包后如何下载源代码(sources)
- Python-HTML CSS题目
- 【转】Android Service创建USB HOST通信
- js中的数据类型及判断方法
- linux内核数据包转发流程(二):中断
热门文章
- Python进阶: Decorator 装饰器你太美
- nginx与php配置用户问题
- Bad owner or permissions on .ssh/config win10问题解决
- Vue Prop属性(父to子)
- vue实现简单的点击切换颜色
- 关于Windows下的访问控制模型
- 笔记 - C#从头开始构建编译器 - 1
- vue.js+DRF跨域访问图片
- [转]github 上传project代码
- CVE-2019-11517 CSRF in Wampserver 3.1.4-3.1.8