原题链接
考察:线段树(扫描线)
通过本题终于稍微弄懂点扫描线了.
思路:
之前的HDU 1542 Atlantis.因为只要在修改前出现过一次就会被计入长度.且区间总是成对出现,也就是不用处理新的区间.
本题只有出现次数>1才会被记录有效长度,此时在修改前需要处理新出现的cnt>1的区间.即需要将父节点覆盖次数传给子节点.
这时的操作实际等同于区间修改cnt的值,需要设置懒标记tag.记录子节点待处理的操作.
push_up操作与Atlantis基本一致.而push_down操作修改子节点的cnt与tag值即可.
修改完后,存在懒标记还未传递到子节点的情况,因此需要询问一遍.
时间复杂度O(2*n*(4*n+log2N))
时限是5000ms,所以不会超时.
Code
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1010;
struct Segment{
double x,y1,y2;
int k;
bool operator<(const Segment& s){
return this->x<s.x;
}
}seg[N<<1];
struct Node{
int l,r,cnt,tag;
double len;//cnt>1的len
}tr[N<<3];
int n;
vector<double> v;
int get(double x)
{
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
double rget(int x)
{
return v[x-1];
}
void build(int u,int l,int r)
{
tr[u].l = l,tr[u].r =r,tr[u].cnt =0,tr[u].len = 0;
tr[u].tag = 0;
if(l==r) return;
int mid = l+r>>1;
build(u<<1,l,mid); build(u<<1|1,mid+1,r);
}
void push_down(int u)
{
if(!tr[u].tag) return;
tr[u<<1].cnt+=tr[u].tag;
tr[u<<1|1].cnt+=tr[u].tag;
tr[u<<1].tag+=tr[u].tag;
tr[u<<1|1].tag+=tr[u].tag;
tr[u].tag = 0;
}
void push_up(int u)
{
if(tr[u].cnt>1) tr[u].len = rget(tr[u].r+1)-rget(tr[u].l);
else if(tr[u].l!=tr[u].r) tr[u].len = tr[u<<1].len+tr[u<<1|1].len;
else tr[u].len = 0;
}
void modify(int u,int l,int r,int w)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
tr[u].cnt+=w;
tr[u].tag+=w;//懒标记
push_up(u);
return;
}
push_down(u);
int mid = tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,w);
if(mid<r) modify(u<<1|1,l,r,w);
push_up(u);
}
void query(int u)
{
if(tr[u].l==tr[u].r)
{
push_up(u);
return;
}
push_down(u);
query(u<<1);
query(u<<1|1);
push_up(u);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
v.clear();
memset(seg,0,sizeof seg);
for(int i=1,j=0;i<=n;i++)
{
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
seg[++j] = {x1,y1,y2,1};
seg[++j] = {x2,y1,y2,-1};
v.push_back(y1),v.push_back(y2);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
sort(seg+1,seg+2*n+1);
build(1,1,v.size());
double res = 0;
for(int i=1;i<=2*n;i++)
{
query(1);
int a = get(seg[i].y1),b = get(seg[i].y2);
res+=(seg[i].x-seg[i-1].x)*tr[1].len;
modify(1,a,b-1,seg[i].k);
}
printf("%.2lf\n",res);
}
}