HDU1542(Atlantis)

链接：https://vjudge.net/problem/HDU-1542
思路：做了之前矩形面积的覆盖和周长的题目后，这个题就容易多了，十几分钟就写完了，但之所以还要写一份题解是有个地方想要提醒一下。还是从头说起，因为端点是小数所以必须要经过离散化，然后每个区间记录被覆盖的次数和区间覆盖长度总和，因为只用求sum[1]所以只需要把下面的信息向上整合即可，问题在于离散化后端点到底表示的是什么，一开始一直没想清楚理所当然的写，后面细细考虑了一下，对于某个端点l，他表示的是l到l+1这个区间的长度，这样的话叶节点本身也才具有意义，所以我们的每个叶节点应该是保存的某个区间，只是用区间的左边界来代替表示区间罢了，所以更新的时候找出来的右端点要-1，里面查询的时候不用再减即可。（注意输出格式，最近一直吃pe就很难受~）
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+10;
int tag[maxn<<2];
double seg[maxn],sum[maxn<<2];
int n,q;

struct line{//扫描线
    double x1,y1,y2;
    int k;
    bool operator<(const line & r){
        return x1<r.x1||(x1==r.x1&&k>r.k);
    }
}li[maxn];

inline void pushup(int o,int l,int r){
    if(tag[o])sum[o] = seg[r] - seg[l-1];//在外面区间减过了这里就不需要再减了
    else 
    sum[o] = sum[o<<1] + sum[o<<1|1];
}

void build(int o,int l,int r){
  tag[o] = 0;
  sum[o] = 0;
  if(l<r){
    int mid = l+r>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o,l,r);
  }
}

void update(int o,int tl,int tr,int l,int r,int v){
    if(tr<l||r<tl)return;
  if(l<=tl&&tr<=r){
    tag[o]+=v;
    pushup(o,tl,tr);//不要忘记这里需要pushup一次
        return;
  }
  int mid = (tl+tr)>>1;
  update(o<<1,tl,mid,l,r,v);
  update(o<<1|1,mid+1,tr,l,r,v);
  pushup(o,tl,tr);
} 

int main(){
    int kase = 0;
    while(~scanf("%d",&n)&&n){
        int cnt = 0;
        int tt = 0;
        for(int i=0;i<n;i++){
            double a,b,c,d;
            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
            li[cnt].x1 = a;
            li[cnt].y1 = b;
            li[cnt].y2 = d;
            li[cnt++].k = 1;
            li[cnt].x1 = c;
            li[cnt].y1 = b;
            li[cnt].y2 = d;
            li[cnt++].k = -1;
            seg[tt++] = b;
            seg[tt++] = d;
        }
        sort(seg,seg+tt);
        sort(li,li+cnt);
        tt = unique(seg,seg+tt) - seg;
        build(1,1,tt);
        double res = 0;
        for(int i=0;i<cnt;i++){
            int l = lower_bound(seg,seg+tt,li[i].y1)-seg+1;
            int r = lower_bound(seg,seg+tt,li[i].y2)-seg;//右区间需要减1
            update(1,1,tt,l,r,li[i].k);
            if(i!=cnt-1)res+=(li[i+1].x1-li[i].x1)*sum[1];
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",++kase,res);
    }
    return  0;
}