题解:

x升序排序

y离散化+树状数组

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,tot,que,disc[N*],x[N],y[N],a[N],b[N],c[N],d[N],t[*N],ans[N][];
struct data{int x,y,id,f;}q[*N];
int operator<(data a,data b)
{
return a.x<b.x||(a.x==b.x&&a.f<b.f);
}
void add(int x,int y)
{
for (int i=x;i<=tot;i+=i&-i)t[i]+=y;
}
int query(int x)
{
int sum=;
for (int i=x;i;i-=i&-i)sum+=t[i];
return sum;
}
int find(int x)
{
int l=,r=tot;
while (l<=r)
{
int mid=(l+r)>>;
if (disc[mid]==x)return mid;
else if(disc[mid]<x)l=mid+;
else r=mid-;
}
}
void solve()
{
sort(q+,q+que+);
for (int i=;i<=que;i++)
{
if (!q[i].f)add(q[i].y,);
else
{
int t=query(q[i].y);
ans[q[i].id][q[i].f]=t;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
{
scanf("%d%d",&x[i],&y[i]);
disc[++tot]=y[i];
}
for (int i=;i<=m;i++)
{
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
disc[++tot]=b[i];disc[++tot]=d[i];
}
sort(disc,disc+tot+);
for (int i=;i<=n;i++)
{
y[i]=find(y[i]);
q[++que].x=x[i];q[que].y=y[i];
}
for (int i=;i<=m;i++)
{
b[i]=find(b[i]);d[i]=find(d[i]);
q[++que].x=c[i];q[que].y=d[i];q[que].id=i;q[que].f=;
q[++que].x=a[i]-;q[que].y=d[i];q[que].id=i;q[que].f=;
q[++que].x=c[i];q[que].y=b[i]-;q[que].id=i;q[que].f=;
q[++que].x=a[i]-;q[que].y=b[i]-;q[que].id=i;q[que].f=;
}
solve();
for (int i=;i<=m;i++)
{
int t=ans[i][]+ans[i][]-ans[i][]-ans[i][];
printf("%d\n",t);
}
return ;
}

最新文章

  1. 德国W家HIPP 奶粉有货播报:2014.7.8 HIPP 奶粉 1+ 4盒装有货啦!
  2. Python标准库(1) — itertools模块
  3. 洛谷P2246 SAC#1 - Hello World(升级版)
  4. modelbinder机制原理
  5. Java知识点总结(不定时更新)
  6. HTML5 manifest离线缓存
  7. 调整iFrame高度
  8. 在Visual Studio 的 “一般处理程序 ” .ashx 文件中如何创建Session 对象
  9. 想买一套arduino玩玩
  10. 50句高级SQL语句
  11. Cocos Studio和Cocos2d-x版本对应关系
  12. Codeforce D. Make a Permutation!
  13. poj2793 素数和
  14. Java并发编程之Lock
  15. Eclipse集成Hadoop插件
  16. 详解OJ(Online Judge)中PHP代码的提交方法及要点【举例:ZOJ 1001 (A + B Problem)】
  17. Unity3d外部加载音频,视频,图片等资源 及根据路径获取制定格式的文件
  18. httpd: apr_sockaddr_info_get() failed for bogon
  19. git杂记:忽略ssl认证
  20. Linux的远程连接工具:SSH的安装

热门文章

  1. CSS3一些常用动画
  2. FreeRTOS
  3. 如何在Virtualbox中对Ubuntu系统根分区扩容
  4. 记一次排查局网内的ARP包 “不存在的” MAC 地址及 “不存在的”IP 所发的ARP包
  5. 安装EF实体模型框架
  6. 11月29日 The Rails philosophy 完成rails on guide 的第一章getting started with rails
  7. p1470 Longest Prefix
  8. linux基础知识(1)
  9. 151. Reverse Words in a String(java 注意细节处理)
  10. https请求排错过程