一个二维偏序的问题,学过了三维偏序cdq分治之后觉得这个题非常的水。只需按一维排序之后再用树状数组操作即可。——by VANE

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+;
struct qry
{
int x,y,id;
}q[N<<];
struct tree
{
int x,y;
}t[N];
int s[N*],n,m,tmp[N*],num,vis_tim,ans[N*];
bool cmp(qry a,qry b)
{
return a.x<b.x;
}
bool cmpp(tree a,tree b)
{
return a.x<b.x;
}
void add(int x)
{
for(;x<=num;x+=x&-x)
s[x]++;
}
int query(int x)
{
int res=;
for(;x;x-=x&-x)
res+=s[x];
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)
scanf("%d%d",&t[i].x,&t[i].y);
for(int i=;i<=m;++i)
{
int x,y,xx,yy;scanf("%d%d%d%d",&x,&y,&xx,&yy);
int pos=(i-)*;
q[pos+].x=xx;q[pos+].y=yy;q[pos+].id=pos+;
q[pos+].x=x-;q[pos+].y=y-;q[pos+].id=pos+;
q[pos+].x=xx;q[pos+].y=y-;q[pos+].id=pos+;
q[pos+].x=x-;q[pos+].y=yy;q[pos+].id=pos+;
}
for(int i=;i<=n;++i)
tmp[i]=t[i].y;
for(int i=;i<=m*;++i)
tmp[i+n]=q[i].y;
sort(tmp+,tmp++n+m*);
num=unique(tmp+,tmp++n+*m)-tmp-;
for(int i=;i<=n;++i) t[i].y=lower_bound(tmp+,tmp++num,t[i].y)-tmp;
for(int i=;i<=m*;++i) q[i].y=lower_bound(tmp+,tmp++num,q[i].y)-tmp;
sort(q+,q++*m,cmp);
sort(t+,t++n,cmpp);
int i=,j=;
while(j<=*m)
{
int h=q[j].x;
while(t[i].x<=h&&i<=n) add(t[i].y),++i;
while(j<=*m&&q[j].x==h)
{
ans[q[j].id]+=query(q[j].y);
++j;
}
}
for(int i=;i<=*m;i+=)
printf("%d\n",ans[i]+ans[i+]-ans[i+]-ans[i+]);
}

二维偏序用cdq我是不是有病,我就是要写cdq 15000ms卡过去了

By:大奕哥

 #include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y,w,id,f;
bool operator <(const node &b)const
{
return x==b.x?y<b.y:x<b.x;
}
}q[];
int cnt,maxr,tim;
int t[],v[],ans[],pos[];
inline int lowbit(int x){return x&(-x);}
void add(int x,int w)
{
for(;x<=maxr;x+=lowbit(x))
{
if(v[x]!=tim)
{
v[x]=tim;t[x]=w;
}
else t[x]+=w;
}
}
int query(int x)
{
int an=;
for(;x;x-=lowbit(x))
if(v[x]==tim)
an+=t[x];
return an;
}
void cdq(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>;
cdq(l,mid);cdq(mid+,r);
sort(q+l,q+mid+);sort(q+mid+,q+r+);
tim++;
int i=l,j=mid+;
while(j<=r)
{
while(q[i].f==&&i<=mid)++i;
while(q[j].f==&&j<=r)++j;
if(q[i].x<=q[j].x&&i<=mid)add(q[i].y,q[i].w),++i;
else if(j<=r)ans[q[j].id]+=query(q[j].y),++j;
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)
{
int x,y;
scanf("%d%d",&x,&y);x++;y++;
q[++cnt].f=;q[cnt].x=x;q[cnt].y=y;q[cnt].w=;q[cnt].id=cnt;maxr=max(maxr,y);
}
for(int i=;i<=m;++i)
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1++;x2++;y1++;y2++;
pos[i]=cnt;maxr=max(maxr,max(y1,y2));
q[++cnt].f=;q[cnt].x=x2;q[cnt].y=y2;q[cnt].id=cnt;
q[++cnt].f=;q[cnt].x=x1-;q[cnt].y=y1-;q[cnt].id=cnt;
q[++cnt].f=;q[cnt].x=x1-;q[cnt].y=y2;q[cnt].id=cnt;
q[++cnt].f=;q[cnt].x=x2;q[cnt].y=y1-;q[cnt].id=cnt;
}
cdq(,cnt);
for(int i=;i<=m;++i)
printf("%d\n",ans[pos[i]+]+ans[pos[i]+]-ans[pos[i]+]-ans[pos[i]+]);
return ;
}

最新文章

  1. 楼盘信息sq
  2. 学习SVG系列(1):SVG基础
  3. java.util.concurrent.RejectedExecutionException: Task java.util.concurrent.FutureTask@1f303192 rejected from java.util.concurrent.ThreadPoolExecutor@11f7cc04[Terminated, pool size = 0, active threads
  4. Android 系统ID介绍
  5. 二叉树系列 - 二叉搜索树 - 线性时间内把有序链表转化为BST
  6. easyui_动态添加隐藏toolbar按钮
  7. java解析xml文件四种方式
  8. loadrunner java 缺少必要的导入包报错
  9. Tomcat服务器的常用配置
  10. ASP.NET之页面传值
  11. pg数据库查询表大小
  12. IO 流读取文件时候出现乱码 文件编码格式问题 怎么转换解决方法
  13. Go版GTK:环境搭建(windows)
  14. oc中的oop基础及类的基本介绍
  15. win10间歇性的找不到usb设备
  16. How to make MySQL handle UTF-8 properly
  17. J2EE规范 - 13种规范
  18. Python中的__init__.py的作用
  19. spring mvc + velocity 搭建实例程序maven版本并且使用的是tomcat容器而不是jetty(step by step)
  20. Sublime Text 3 web 开发常用配置

热门文章

  1. linux平台 PHP 实现 word转pdf的艰难历程...
  2. NYOJ 141 Squares (数学)
  3. mysql-front导入数据失败:“在多字节的目标代码页中,没有此 Unicode 字符可以映射到的字符”
  4. css3旋转、过渡、动画属性
  5. OSCP考试回顾
  6. supervisor之启动rabbitmq报错原因
  7. 【Python学习】request库
  8. 在Linux(CentOS)中安装.netcore SDK
  9. WPF之模拟打开或关闭Windows功能
  10. 设计模式之笔记--命令模式(Command)