admin管理员组文章数量:1642351
题意:给出N个矩形,求被这些矩形覆盖K次以上的区域面积。
做过hdu 3642 Get The Treasure和hdu 1255 覆盖的面积这道题应该不难才是。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
typedef long long LL;
const int N=60005;
struct Line
{
int x,y1,y2,flag;
Line(){}
Line(int a,int b,int c,int d)
{ x=a;y1=b;y2=c;flag=d; }
bool operator<(const Line&b)const
{ return x<b.x; }
};
struct node
{
int lft,rht;
int len[12],flag;
int mid(){return MID(lft,rht);}
void init(){memset(len,0,sizeof(len));}
};
int n,k;
vector<int> y;
vector<Line> line;
map<int,int> H;
struct Segtree
{
node tree[N*4];
void calu(int ind)
{
if(tree[ind].flag>=k)
{
int tmp=tree[ind].len[0];
tree[ind].init();
tree[ind].len[k]=tree[ind].len[0]=tmp;
}
else if(tree[ind].flag>0)
{
int sum=0,cov=tree[ind].flag;
for(int i=1;i<=k;i++) tree[ind].len[i]=0;
tree[ind].len[cov]=tree[ind].len[0];
if(tree[ind].lft+1==tree[ind].rht) return;
for(int i=1;i<=k;i++)
{
if(i+cov>=k) tree[ind].len[k]+=tree[LL(ind)].len[i]+tree[RR(ind)].len[i];
else tree[ind].len[i+cov]=tree[LL(ind)].len[i]+tree[RR(ind)].len[i];
}
for(int i=cov+1;i<=k;i++) sum+=tree[ind].len[i];
tree[ind].len[cov]-=sum;
}
else
{
for(int i=1;i<=k;i++) tree[ind].len[i]=0;
if(tree[ind].lft+1==tree[ind].rht) return;
for(int i=1;i<=k;i++)
tree[ind].len[i]=tree[LL(ind)].len[i]+tree[RR(ind)].len[i];
}
}
void build(int lft,int rht,int ind)
{
tree[ind].lft=lft; tree[ind].rht=rht;
tree[ind].init(); tree[ind].flag=0;
tree[ind].len[0]=y[rht]-y[lft];
if(lft+1!=rht)
{
int mid=tree[ind].mid();
build(lft,mid,LL(ind));
build(mid,rht,RR(ind));
}
}
void updata(int st,int ed,int ind,int valu)
{
int lft=tree[ind].lft,rht=tree[ind].rht;
if(st<=lft&&rht<=ed) tree[ind].flag+=valu;
else
{
int mid=tree[ind].mid();
if(st<mid) updata(st,ed,LL(ind),valu);
if(ed>mid) updata(st,ed,RR(ind),valu);
}
calu(ind);
}
}seg;
int main()
{
int t,t_cnt=0;
scanf("%d",&t);
while(t--)
{
y.clear(); H.clear(); line.clear();
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x2++;y2++;
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(line.begin(),line.end());
sort(y.begin(),y.end());
y.erase(unique(y.begin(),y.end()),y.end());
for(int i=0;i<(int)y.size();i++) H[y[i]]=i;
seg.build(0,(int)y.size()-1,1);
LL res=0;
for(int i=0;i<(int)line.size();i++)
{
if(i!=0) res+=(LL)(line[i].x-line[i-1].x)*seg.tree[1].len[k];
seg.updata(H[line[i].y1],H[line[i].y2],1,line[i].flag);
}
printf("Case %d: %lld\n",++t_cnt,res);
}
return 0;
}
本文标签: uvaadvertisementWeird
版权声明:本文标题:uva 11983 Weird Advertisement(扫描线) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1729328668a1196095.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论