四维偏序。。

就是给你一个四维集合。再给你一些询问,请你求出a[i].x1<=ask.x1&&a[i].x2<=ask.x2&&a[i].x3<=ask.x3&&a[i].x4<=ask.x4的个数。。

集合大小<=30000

询问个数<=30000

然后怎么做呢??

其实很简单只要排序+cdq+树状数组套平衡树什么的就行了

qnmd老子不会。。

这时!

神器来了!

那就是bitset!

众所周知,bitset能存一堆二进制位每一位的状态,而且,bitset和bitset之间是可以进行&操作的

也就是说,我们每次可以对第i位排个序,在判断第i个集合是否满足询问条件,bitset&一下就好了!

放上代码

#include<cmath>
#include<cstdio>
#include<bitset>
#include<algorithm>
#define N 40000
#define eps 1e-8
using namespace std;
int i,j,k,n,m,x,y,t;
struct data{double x1,x2,x3,x4;int id,p;}p[N],q[N],pq[N+N];
bitset<N> ans[N],w;
bool same(double a,double b){return fabs(a-b)<eps;}
bool cmp1(const data&a,const data&b){return same(a.x1,b.x1)?a.p>b.p:a.x1<b.x1-eps;}
bool cmp2(const data&a,const data&b){return same(a.x2,b.x2)?a.p>b.p:a.x2<b.x2-eps;}
bool cmp3(const data&a,const data&b){return same(a.x3,b.x3)?a.p>b.p:a.x3<b.x3-eps;}
bool cmp4(const data&a,const data&b){return same(a.x4,b.x4)?a.p>b.p:a.x4<b.x4-eps;}
int main(){
scanf("%d",&n);
for (i=;i<=n;i++){scanf("%lf%lf%lf%lf",&p[i].x1,&p[i].x2,&p[i].x3,&p[i].x4);p[i].id=i;p[i].p=;}
scanf("%d",&m);
for (i=;i<=m;i++){scanf("%lf%lf%lf%lf",&q[i].x1,&q[i].x2,&q[i].x3,&q[i].x4);q[i].id=i;q[i].p=;}
for (i=;i<=m;i++)ans[i].set();
//-----------------------------------------------------------------
for (i=;i<=n;i++)pq[i]=p[i];
for (i=;i<=m;i++)pq[n+i]=q[i];
sort(pq+,pq++n+m,cmp1);
w.reset();
for (i=;i<=n+m;i++)if (pq[i].p)w[pq[i].id]=;else ans[pq[i].id]&=w;
//-----------------------------------------------------------------
for (i=;i<=n;i++)pq[i]=p[i];
for (i=;i<=m;i++)pq[n+i]=q[i];
sort(pq+,pq++n+m,cmp2);
w.reset();
for (i=;i<=n+m;i++)if (pq[i].p)w[pq[i].id]=;else ans[pq[i].id]&=w;
//-----------------------------------------------------------------
for (i=;i<=n;i++)pq[i]=p[i];
for (i=;i<=m;i++)pq[n+i]=q[i];
sort(pq+,pq++n+m,cmp3);
w.reset();
for (i=;i<=n+m;i++)if (pq[i].p)w[pq[i].id]=;else ans[pq[i].id]&=w;
//-----------------------------------------------------------------
for (i=;i<=n;i++)pq[i]=p[i];
for (i=;i<=m;i++)pq[n+i]=q[i];
sort(pq+,pq++n+m,cmp4);
w.reset();
for (i=;i<=n+m;i++)if (pq[i].p)w[pq[i].id]=;else ans[pq[i].id]&=w;
for (i=;i<=m;i++)printf("%d\n",ans[i].count());
return ;
}

分隔符是为了分开四次排序。。

复杂度是O(n*m/32)....

尽管看上去很慢但是。。

最新文章

  1. 擦掉STM32F429芯片上的数据的一个方法
  2. 关于Linux x64 Oracle JDK7u60 64-bit HotSpot VM 线程栈默认大小问题的整理
  3. javascript url几种编码方式
  4. 用VB实现点名程序
  5. [转]A plain english introduction to cap theorem
  6. iOS开发环境C语言基础
  7. STL之迭代器
  8. 【boost】使用lambda表达式和generate_n生成顺序序列
  9. cocos2d-x学习笔记------动画人物跑起来吧!
  10. (转)MVC语法-@helpers和@functions(Razor内定义函数)
  11. Django__WSGI
  12. unity2d开发windows phone游戏按钮问题
  13. Git应用--04遇到冲突解决办法git stash(转载)
  14. H5自适应屏幕分辨率大小
  15. Google 翻译(中英,英中)
  16. luogu1351 [NOIp2014]联合权值 (dfs)
  17. 【CF884D】Boxes And Balls 哈夫曼树
  18. win7 任务计划运行批处理,不能正常运行,需用绝对路径
  19. alpha发布评论
  20. SD卡路径问题以及如何获取SDCard 内存

热门文章

  1. 【LeetCode206】Reverse Linked List★
  2. Windows Server2003 IIS服务器安全配置整理
  3. 2017-2018-2 『网络对抗技术』Exp3:免杀原理与实践
  4. EZ 2018 04 21 NOIP2018 模拟赛(九)
  5. 【第七课】Nginx反向代理和负载均衡
  6. Yii2 软删除
  7. 使用fddb的测试工具测试自己的检测器
  8. idea 设置格式化代码 快捷键
  9. python中eval函数作用
  10. 不再迷惑,无值和NULL值