首页 > 其他分享 >bzoj 4237 稻草人

bzoj 4237 稻草人

时间:2023-04-04 12:04:12浏览次数:62  
标签:田地 int mid top1 稻草人 CDQ 4237 bzoj



4237: 稻草人


Time Limit: 40 Sec   Memory Limit: 256 MB

Submit: 791  

Solved: 353

[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


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)互不相同。




Source


JOI 2013~2014 春季training合宿 竞技3 By PoPoQQQ




【分析】

CDQ分治+单调栈+二分



【代码】

//bzoj 4237 稻草人
#include<bits/stdc++.h>
#define ll long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int mxn=200005;
ll ans;
int n,m,T,top1,top2;
struct node {int x,y;} a[mxn],tmp[mxn],s1[mxn],s2[mxn]; 
inline bool comp(node u,node v)
{
	return u.y<v.y;
}
inline int find(int l,int r,int x)
{
	while(l<r)
	{
		int mid=(l+r>>1)+1;
		if(x>s1[mid].x) l=mid;
		else r=mid-1;
	}
	return l;
}
inline void CDQ(int l,int r)
{
	if(l==r) return;
	int i,j,mid=l+r>>1,l1=l,l2=mid+1;
	CDQ(l,mid),CDQ(mid+1,r);
	top1=top2=0;
	for(l2=mid+1;l2<=r;l2++)
	{
		while(top2 && a[l2].y<s2[top2].y) top2--;
		s2[++top2]=a[l2];
		for(l1;l1<=mid && a[l1].x<a[l2].x;l1++)
		{
			while(top1 && a[l1].y>s1[top1].y) top1--;
			s1[++top1]=a[l1];
		}
		ans+=top1-find(0,top1,s2[top2-1].x);
	}
	l1=l,l2=mid+1;
	fo(i,l,r)
	  tmp[i]=((l1<=mid && a[l1].x<a[l2].x) || l2>r)?a[l1++]:a[l2++];
	fo(i,l,r) a[i]=tmp[i];
}
int main()
{
	int i,j;
	scanf("%d",&n);
	fo(i,1,n)
	  scanf("%d%d",&a[i].x,&a[i].y);
	sort(a+1,a+n+1,comp);
	CDQ(1,n);
	printf("%lld\n",ans);
	return 0;
}



标签:田地,int,mid,top1,稻草人,CDQ,4237,bzoj
From: https://blog.51cto.com/u_15967757/6168365

相关文章

  • bzoj 3622 已经没有什么好害怕的了
    3622:已经没有什么好害怕的了TimeLimit: 10Sec  MemoryLimit: 256MBSubmit: 805  Solved: 377[Submit][Status][Discuss]DescriptionInputOutputSampleInput42535154540201030SampleOutput4HINT输入的2*n个数字保证全不相同。......
  • bzoj1969. [AHOI2005] LANE 航线规划 树链剖分+离线逆向处理删边
    保证了无论怎么破坏航线,图都会是一个连通图也就是说,起码肯定有一棵生成树考虑在生成树上U,V之间加边,会对树上各个点的割边情况产生什么影响对于任意点对(u,v),如果它们之间的最短路径不经过从U到V的树上路径,那是没有影响的否则:关键路径的数目会减少减少了多少?U,V之间树上路径经......
  • [BZOJ3331][BeiJing2013]压力
    #include<iostream>#include<cmath>#include<algorithm>#include<cstring>#include<cstdio>#include<vector>usingnamespacestd;vector<int>temp[5211314],b......
  • bzoj 3669 魔法森林
    3669:[Noi2014]魔法森林TimeLimit: 30Sec  MemoryLimit: 512MBSubmit: 2690  Solved: 1667Submit][Status][Discuss]Description为了得到书法大家......
  • bzoj 2843 极地旅行社
    2843:极地旅行社TimeLimit: 10Sec  MemoryLimit: 256MBSubmit: 771  Solved: 473[Submit][Status][Discuss]Description不久之前,Mirko建立了一......
  • bzoj 2555 SubString
    2555:SubStringTimeLimit: 30Sec  MemoryLimit: 512MBSubmit: 2611  Solved: 784[Submit][Status][Discuss]Description      懒得写背景......
  • bzoj 2157 旅游
    2157:旅游TimeLimit:10Sec  MemoryLimit:259MBSubmit:1649  Solved:725[Submit][Status][Discuss]DescriptionRay乐忠于旅游,这次他来到了T城。......
  • bzoj 2631 tree
    2631:treeTimeLimit: 30Sec  MemoryLimit: 128MBSubmit: 4429  Solved: 1488[Submit][Status][Discuss]Description一棵n个点的树,每个点的初始......
  • bzoj 2049 [Sdoi2008]Cave 洞穴勘测
    2049:[Sdoi2008]Cave洞穴勘测TimeLimit: 10Sec  MemoryLimit: 259MBSubmit: 8714  Solved: 4143[Submit][Status][Discuss]Description辉辉热衷......
  • bzoj 2806 [Ctsc2012]Cheat
    2806:[Ctsc2012]CheatTimeLimit: 20Sec  MemoryLimit: 256MBSubmit: 1324  Solved: 676[Submit][Status][Discuss]DescriptionInput第一行两个......