给你一堆线段,求:一个区间内包含的本质不同线段种类数(只要线段有一部分在区间中就算是包含)

考虑容斥:总线段数-被那些没有询问的区间完全覆盖的数量.

用离线+树状数组数点或者 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;
}

  

最新文章

  1. 从零自学Hadoop(16):Hive数据导入导出,集群数据迁移上
  2. ListView的属性及方法详解
  3. python flask应用部署
  4. Linux设备模型(总线、设备、驱动程序和类)
  5. C++primer 阅读点滴记录(一)
  6. Linux 系统中用户切换(su user与 su - user 的区别)
  7. js一些方法的扩展
  8. Live555 Streaming from a live source
  9. Log4J使用笔记(转)
  10. 框架开发(三)---smarty整合
  11. docker !veth
  12. Android开发中的OpenCV霍夫直线检测(Imgproc.HoughLines()&amp;Imgproc.HoughLinesP())
  13. Python 编程规范
  14. Android 混淆那些事儿
  15. 关于Oracle数据库故障诊断基础架构
  16. eclipse maven引入第三方jar包后如何下载源代码(sources)
  17. Python-HTML CSS题目
  18. 【转】Android Service创建USB HOST通信
  19. js中的数据类型及判断方法
  20. linux内核数据包转发流程(二):中断

热门文章

  1. Python进阶: Decorator 装饰器你太美
  2. nginx与php配置用户问题
  3. Bad owner or permissions on .ssh/config win10问题解决
  4. Vue Prop属性(父to子)
  5. vue实现简单的点击切换颜色
  6. 关于Windows下的访问控制模型
  7. 笔记 - C#从头开始构建编译器 - 1
  8. vue.js+DRF跨域访问图片
  9. [转]github 上传project代码
  10. CVE-2019-11517 CSRF in Wampserver 3.1.4-3.1.8