首页 > ACM题库 > HDU-杭电 > HDU 4052-Adding New Machine-线段树-[解题报告]HOJ
2015
04-16

HDU 4052-Adding New Machine-线段树-[解题报告]HOJ

Adding New Machine

问题描述 :

Incredible Crazily Progressing Company (ICPC) suffered a lot with the low speed of procedure. After investigation, they found that the bottleneck was at Absolutely Crowded Manufactory (ACM). In oder to accelerate the procedure, they bought a new machine for ACM. But a new problem comes, how to place the new machine into ACM?

ACM is a rectangular factor and can be divided into W * H cells. There are N retangular old machines in ACM and the new machine can not occupy any cell where there is old machines. The new machine needs M consecutive cells. Consecutive cells means some adjacent cells in a line. You are asked to calculate the number of ways to choose the place for the new machine.

输入:

There are multiple test cases (no more than 50). The first line of each test case contains 4 integers W, H, N, M (1 ≤ W, H ≤ 107, 0 ≤ N ≤ 50000, 1 ≤ M ≤ 1000), indicating the width and the length of the room, the number of old machines and the size of the new machine. Then N lines follow, each of which contains 4 integers Xi1, Yi1, Xi2 and Yi2 (1 ≤ Xi1 ≤ Xi2 ≤ W, 1 ≤ Yi1 ≤ Yi2 ≤ H), indicating the coordinates of the i-th old machine. It is guarantees that no cell is occupied by two old machines.

输出:

There are multiple test cases (no more than 50). The first line of each test case contains 4 integers W, H, N, M (1 ≤ W, H ≤ 107, 0 ≤ N ≤ 50000, 1 ≤ M ≤ 1000), indicating the width and the length of the room, the number of old machines and the size of the new machine. Then N lines follow, each of which contains 4 integers Xi1, Yi1, Xi2 and Yi2 (1 ≤ Xi1 ≤ Xi2 ≤ W, 1 ≤ Yi1 ≤ Yi2 ≤ H), indicating the coordinates of the i-th old machine. It is guarantees that no cell is occupied by two old machines.

样例输入:

3 3 1 2
2 2 2 2
3 3 1 3
2 2 2 2
2 3 2 2
1 1 1 1
2 3 2 3

样例输出:

8
4
3

题意:给你W*H大小的矩形,其中有N个地区不能使用(给出了这个地区的两个顶点的坐标即(x1,y1)和(x2,y2)),问能下多少个1*M的矩形。

分别统计1*M的矩形横着放能放多少个,竖着放能放多少个。可以转化成统计哪些位置可以放这矩形的第一个方格。比如说,当我们统计横着能放多少个的时候,问题转化成找出有多少个这样的方格(i,j),使得(i,j+1),(i,j+2)……(i,j+m-1)都是可以被使用的。易得,(x1,y1-m+1)到(x2,y2)这个区域内的方格都是不满足要求的。把不满足条件的方格抠掉,剩下就是满足条件的方格了,问题就变成用扫描线求矩形的面积了。要注意M=1的情况,并且边界上也有一些方格不满足条件,也要抠掉。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
typedef long long LL;
const int N=100005;
struct Line
{
	int x,y1,y2,valu;
	Line(){}
	Line(int a,int b,int c,int d){x=a;y1=b;y2=c;valu=d;}
	bool operator<(const Line &b)const
	{
		return x<b.x;
	}
};
struct node
{
	int lft,rht,sum,valu;
	int mid(){return lft+(rht-lft)/2;}
};

map<int,int> imap;
vector<int> y;
vector<Line> line;
int data[N][4];

struct Segtree
{
	node tree[N*4];
	void relax(int ind)
	{
		if(tree[ind].valu>0) 
			tree[ind].sum=y[tree[ind].rht]-y[tree[ind].lft];
		else 
		{
			if(tree[ind].lft+1==tree[ind].rht) tree[ind].sum=0;
			else tree[ind].sum=tree[LL(ind)].sum+tree[RR(ind)].sum;
		}
	}
	void build(int lft,int rht,int ind)
	{
		tree[ind].lft=lft;	tree[ind].rht=rht;
		tree[ind].sum=0;	tree[ind].valu=0;
		if(lft+1!=rht)
		{
			int mid=tree[ind].mid();
			build(lft,mid,LL(ind));
			build(mid,rht,RR(ind));
		}
	}
	void updata(int be,int end,int ind,int valu)
	{
		int lft=tree[ind].lft,rht=tree[ind].rht;
		if(be<=lft&&rht<=end) 
		{
			tree[ind].valu+=valu;
			relax(ind);
		}
		else 
		{
			int mid=tree[ind].mid();
			if(be<mid) updata(be,end,LL(ind),valu);
			if(end>mid) updata(be,end,RR(ind),valu);
			relax(ind);
		}
	}
}seg;

LL solve(int n,int w,int h,int m)
{
	y.clear();	line.clear(); imap.clear();
	y.push_back(1);	y.push_back(h);
	line.push_back(Line(max(1,w-m),1,h,1));	
	line.push_back(Line(w,1,h,-1));
	for(int i=0;i<n;i++) 
	{
		int x1=max(1,data[i][0]-m),y1=data[i][1];
		int x2=data[i][2],y2=data[i][3];
		line.push_back(Line(x1,y1,y2,1));
		line.push_back(Line(x2,y1,y2,-1));
		y.push_back(y1);y.push_back(y2);
	}
	sort(y.begin(),y.end());
	y.erase(unique(y.begin(),y.end()),y.end());
	for(int i=0;i<(int)y.size();i++) 
		imap.insert(make_pair(y[i],i));
	sort(line.begin(),line.end());

	LL res=0;
	seg.build(0,(int)y.size(),1);
	for(int i=0;i<(int)line.size();i++)
	{
		if(i!=0) res+=(LL)seg.tree[1].sum*(line[i].x-line[i-1].x);
		seg.updata(imap[line[i].y1],imap[line[i].y2],1,line[i].valu);
	}
	return res;
}
int main()
{
	int w,h,n,m;
	while(scanf("%d%d%d%d",&w,&h,&n,&m)!=EOF)
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<4;j++)
			{
				scanf("%d",&data[i][j]);
				if(j==2||j==3) data[i][j]++;
			}
		LL res1=(LL)w*h-solve(n,w+1,h+1,m-1);
		for(int i=0;i<n;i++) 
		{
			swap(data[i][0],data[i][1]);
			swap(data[i][2],data[i][3]);
		}
		LL res2=(LL)w*h-solve(n,h+1,w+1,m-1);
		if(m!=1) printf("%I64d\n",res1+res2);
		else printf("%I64d\n",res1);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/shiqi_614/article/details/7983508


  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish