bzoj 4237 稻草人 CDQ
2024-09-30 23:09:48
稻草人
Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 1433 Solved: 626
[Submit][Status][Discuss]
Description
JOI村有一片荒地,上面竖着N个稻草人,村民们每年多次在稻草人们的周围举行祭典。
有一次,JOI村的村长听到了稻草人们的启示,计划在荒地中开垦一片田地。和启示中的一样,田地需要满足以下条件:
田地的形状是边平行于坐标轴的长方形;
左下角和右上角各有一个稻草人;
田地的内部(不包括边界)没有稻草人。
给出每个稻草人的坐标,请你求出有多少遵从启示的田地的个数
Input
第一行一个正整数N,代表稻草人的个数
接下来N行,第i行(1<=i<=N)包含2个由空格分隔的整数Xi和Yi,表示第i个稻草人的坐标
Output
输出一行一个正整数,代表遵从启示的田地的个数
Sample Input
4
0 0
2 2
3 4
4 3
0 0
2 2
3 4
4 3
Sample Output
3
HINT
所有满足要求的田地由下图所示:
1<=N<=2*10^5
0<=Xi<=10^9(1<=i<=N)
0<=Yi<=10^9(1<=i<=N)
Xi(1<=i<=N)互不相同。
Yi(1<=i<=N)互不相同。
题解:这题就是就是统计问题,经典的CDQ,因为每个x,y都不同,好办得不行
按行分治,然后两边列排序,即可,维护一下,其实可以优化到n log n,外面可以预处理掉。
但是n log ^2n可以过
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = ;
int n,stack[MAXN],top,stack2[MAXN],tail;
LL ans;
struct node{ int x,y; }a[MAXN];
inline bool cmpx(node q,node qq){ return q.x<qq.x; }
inline bool cmpy(node q,node qq){ return q.y<qq.y; }
inline int getint(){
int w=,q=; char c=getchar(); while((c<''||c>'') && c!='-') c=getchar();
if(c=='-') q=,c=getchar(); while (c>=''&&c<='') w=w*+c-'',c=getchar(); return q?-w:w;
} inline void solve(int l,int r){
if(l==r) return ; sort(a+l,a+r+,cmpy); int mid=(l+r)>>;
sort(a+l,a+mid+,cmpx);//down
sort(a+mid+,a+r+,cmpx);//up
top=tail=; int now=l,L,R,pos,mm,cp;
for(int i=mid+;i<=r;i++) {
while(top> && a[stack[top]].y>=a[i].y) top--;
stack[++top]=i; while(now<=mid && a[now].x<a[i].x) {
while(tail> && a[stack2[tail]].y<=a[now].y) tail--;
stack2[++tail]=now;
now++;
} L=; R=tail; pos=-; cp=a[stack[top-]].x;
while(L<=R) {
mm=(L+R)>>;
if(a[stack2[mm]].x>cp) pos=mm,R=mm-;
else L=mm+;
}
if(pos!=-) ans+=tail-pos+;
}
solve(l,mid); solve(mid+,r);
} inline void work(){
n=getint(); for(int i=;i<=n;i++) a[i].x=getint(),a[i].y=getint();
a[].x=a[].y=-;
solve(,n);
printf("%lld",ans);
} int main()
{
work();
return ;
}
最新文章
- EntityFramework 实体拆分和表拆分
- IIS不能下载ini文件
- [SPI&;I2C]I2C和SPI协议介绍
- Javascript浏览器对象模型BoM要点总结
- jQuery Ajax无刷新操作一般处理程序 ashx
- Extjs 学习笔记1
- oracle 卸载
- 屏幕 Dynpro
- Blast使用详解
- 计算机网络相关:应用层协议(二):HTTP
- 常见js特效的思路
- h5页面在ios机上禁止长按复制
- php emoji mysql保存和搜索
- unity-----------------------四元数与欧拉旋转方法
- tflearn 实现DNN 全连接
- UCOS源码剖析 (一)
- List根据某个字段(属性)去重
- 2017年Java学习总结
- Vue 1-- ES6 快速入门、vue的基本语法、vue应用示例,vue基础语法
- 对Java对象的认识与理解