bzoj1935
2024-10-16 07:02:22
题解:
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 ;
}
最新文章
- 德国W家HIPP 奶粉有货播报:2014.7.8 HIPP 奶粉 1+ 4盒装有货啦!
- Python标准库(1) — itertools模块
- 洛谷P2246 SAC#1 - Hello World(升级版)
- modelbinder机制原理
- Java知识点总结(不定时更新)
- HTML5 manifest离线缓存
- 调整iFrame高度
- 在Visual Studio 的 “一般处理程序 ” .ashx 文件中如何创建Session 对象
- 想买一套arduino玩玩
- 50句高级SQL语句
- Cocos Studio和Cocos2d-x版本对应关系
- Codeforce D. Make a Permutation!
- poj2793 素数和
- Java并发编程之Lock
- Eclipse集成Hadoop插件
- 详解OJ(Online Judge)中PHP代码的提交方法及要点【举例:ZOJ 1001 (A + B Problem)】
- Unity3d外部加载音频,视频,图片等资源 及根据路径获取制定格式的文件
- httpd: apr_sockaddr_info_get() failed for bogon
- git杂记:忽略ssl认证
- Linux的远程连接工具:SSH的安装
热门文章
- CSS3一些常用动画
- FreeRTOS
- 如何在Virtualbox中对Ubuntu系统根分区扩容
- 记一次排查局网内的ARP包 “不存在的” MAC 地址及 “不存在的”IP 所发的ARP包
- 安装EF实体模型框架
- 11月29日 The Rails philosophy 完成rails on guide 的第一章getting started with rails
- p1470 Longest Prefix
- linux基础知识(1)
- 151. Reverse Words in a String(java 注意细节处理)
- https请求排错过程