E - 秋实大哥与家
Time Limit: 1 Sec Memory Limit: 256 MB
题目连接
http://acm.uestc.edu.cn/#/contest/show/59
Description
秋实大哥是一个顾家的男人，他认为人生就是旅途，不管我们漂到哪，最终还是会回到温暖的地方——家。
所以他买了很多家具。
秋实大哥的家可以看成一个W×H的矩阵，每一件家具可以看成一个矩形，他们放置在秋实大哥的家里，相互之间没有重叠。
现在秋实大哥购置了一个新的大小为1×M的家具，秋实大哥想知道他有多少种方式来安放这个家具。
Input
第一行包含四个整数W，H，n，M，表示秋实大哥家的大小为W×H，现在已有n个家具，新购置的家具大小为1×M。
接下来n行，每行包含4个整数x1，y1，x2，y2，分别表示这个家具左下角的坐标和右上角的坐标。
1≤n，H，W，M≤100000，1≤x1≤x2≤W，1≤y1≤y2≤H。
Output
输出一行包含一个整数，表示有多少种方案可以来放置秋实大哥的新家具，要求不能跟原有的家具重叠，也不能超出家的范围。
Sample Input
3 3 1 2
2 2 2 2
2 2 2 2
Sample Output
8
HINT
题意
题解：
对于每一个矩形，我们都向左边延展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=;
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)/;}
}; map<int,int> imap;
vector<int> y;
vector<Line> line;
int data[N][]; struct Segtree
{
node tree[N*];
void relax(int ind)
{
if(tree[ind].valu>)
tree[ind].sum=y[tree[ind].rht]-y[tree[ind].lft];
else
{
if(tree[ind].lft+==tree[ind].rht) tree[ind].sum=;
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=; tree[ind].valu=;
if(lft+!=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(); y.push_back(h);
line.push_back(Line(max(,w-m),,h,));
line.push_back(Line(w,,h,-));
for(int i=;i<n;i++)
{
int x1=max(,data[i][]-m),y1=data[i][];
int x2=data[i][],y2=data[i][];
line.push_back(Line(x1,y1,y2,));
line.push_back(Line(x2,y1,y2,-));
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=;i<(int)y.size();i++)
imap.insert(make_pair(y[i],i));
sort(line.begin(),line.end()); LL res=;
seg.build(,(int)y.size(),);
for(int i=;i<(int)line.size();i++)
{
if(i!=) res+=(LL)seg.tree[].sum*(line[i].x-line[i-].x);
seg.updata(imap[line[i].y1],imap[line[i].y2],,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=;i<n;i++)
for(int j=;j<;j++)
{
scanf("%d",&data[i][j]);
if(j==||j==) data[i][j]++;
}
LL res1=(LL)w*h-solve(n,w+,h+,m-);
for(int i=;i<n;i++)
{
swap(data[i][],data[i][]);
swap(data[i][],data[i][]);
}
LL res2=(LL)w*h-solve(n,h+,w+,m-);
if(m!=) printf("%lld\n",res1+res2);
else printf("%lld\n",res1);
}
return ;
}