HDU - 1255 扫描线+离散化进阶
这道题最开始我以为和HDU - 1542 那道题一样，只需要把cover次数改成2次即可，但是后面仔细一想，我们需要求的是覆盖次数大于等于2次的，这样的话，我们需要维护两个长度，HDU-1542 由于求的是覆盖次数大于等于一次的，我们只需要维护一个覆盖次数大于等于1的长度的len1就行，但是这道题我们要求的是覆盖两次以及两次以上的长度，这样乘以高度差，才是面积。
现在我们来想如何维护这个值？
给线段树打个标记cover，代表这个区间被完全覆盖的次数。
我们先来看看，维护覆盖一次及其以上的，应该怎么实现，我们可以从中得到启示。
- cover不为0 那么这个区间被完全覆盖。我们把整个区间长度给len1，但是我们由于经过离散化。表达式为：tree[root].len1=pos[r+1]-pos[l]
- L==R 代表跑到了叶子节点，不会有节点信息往上传，因此赋0
- 不满足上述两者，我们就可以认为，父节点的信息，又两个儿子节点的提供。
那么覆盖两次的呢？同样的分情况讨论
- cover>1 那么这个区间内被完全覆盖至少2次，值等于区间长度。
- L==R 同样的信息不能由子节点提供，赋0。
- Cover==1 那么这个区间被完全覆盖至少一，子节点覆盖次数大于等于1的次数往上pushup后，变成至少两次。
- 反之节点信息由两个子节点提供
#include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> using namespace std; inline int L(int r) { return r<<1; }; inline int R(int r) { return r<<1|1; }; inline int MID(int l,int r) { return (l+r)>>1; }; const int maxx = 2015; struct Line { double l,r,h; int f; }line[maxx*2]; struct node { int l,r,cover; double len1,len2; } tree[maxx<<2]; double pos[maxx]; bool cmp(Line a,Line b){ return a.h<b.h; } void buildtree(int root,int l,int r)//建树 { tree[root].l=l; tree[root].r=r; tree[root].len1=0; tree[root].len2=0; tree[root].cover=0; if (l==r) { return; } int mid = MID(l,r); buildtree(L(root),l,mid); buildtree(R(root),mid+1,r); } int bin(double key,int low,int high) { while(low<=high) { int mid = (low+high)>>1; if (pos[mid] == key) return mid; else if (pos[mid] < key) low = mid+1; else high = mid-1; } return -1; } void pushup(int root) { int l=tree[root].l; int r=tree[root].r; if (tree[root].cover)tree[root].len1=pos[r+1]-pos[l]; else if (l==r)tree[root].len1=0; else tree[root].len1=tree[L(root)].len1+tree[R(root)].len1; if (tree[root].cover>1)tree[root].len2=tree[root].len1; else if (l==r)tree[root].len2=0; else if (tree[root].cover==1)tree[root].len2=tree[L(root)].len1+tree[R(root)].len1; else tree[root].len2=tree[L(root)].len2+tree[R(root)].len2; } void update(int root,int ul,int ur,int c) { int l=tree[root].l; int r=tree[root].r; if (ul<=l && r<=ur) { tree[root].cover+=c; pushup(root); return; } int mid=MID(l,r); if (ur<=mid)update(L(root),ul,ur,c); else if (ul>mid)update(R(root),ul,ur,c); else { update(L(root),ul,mid,c); update(R(root),mid+1,ur,c); } pushup(root); } int main() { int t; scanf("%d",&t); int n; while(t--){ int nums=0; scanf("%d",&n); for (int i=0;i<n;i++){ double x1,x2,y1,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[nums].l=x1; line[nums].r=x2; line[nums].h=y1; line[nums].f=1; pos[nums++]=x1; line[nums].l=x1; line[nums].r=x2; line[nums].h=y2; line[nums].f=-1; pos[nums++]=x2; } sort(pos,pos+nums); sort(line,line+nums,cmp); int m=1; for (int i=1;i<nums;i++)//去重 if (pos[i]!=pos[i-1]) pos[m++]=pos[i]; buildtree(1,0,m-1); double ans=0; for (int i=0;i<nums;i++) { int l=bin(line[i].l,0,m-1); int r=bin(line[i].r,0,m-1)-1; update(1,l,r,line[i].f); ans+=tree[1].len2*(line[i+1].h-line[i].h); } printf("%.2lf\n",ans); } return 0; }
