?
一道挺简单的题，让我折腾了许久。主要卡在了更新节点后维护父亲节点上。后来思路明确了就很容易了。
节点信息：
l,r：区间端点
cnt:区间被覆盖的次数,cnt = 0说明没有被完全覆盖。
len1:区间被覆盖的长度
len2:区间至少被两条线段覆盖的长度。
只要找到父亲节点与子节点在len1，len2，cnt的关系就简单了。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 1010; double x[maxn*2]; struct Line { double x1,x2,y; int tag; bool operator < (const struct Line &tmp)const { return y < tmp.y; } }line[maxn*2]; struct node { int l,r,cnt; double len1,len2; }tree[maxn*8]; int Binsearch(int l, int r, double key) { int low = l, high = r; while(high >= low) { int mid = (low + high) >> 1; if(x[mid] == key) return mid; if(x[mid] > key) high = mid-1; else low = mid+1; } return -1; } void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; tree[v].cnt = 0; tree[v].len1 = tree[v].len2 = 0; if(l == r) return; int mid = (l+r) >> 1; build(v*2,l,mid); build(v*2+1,mid+1,r); } /*重点。 若该节点的cnt >= 2,说明被至少两条线段覆盖，那么len1=len2=区间长度。 若该节点的cnt == 1，说明该区间被一条线段覆盖，len1=区间长度，只要左右节点的len1有值， 那么那些长度一定是至少被覆盖两次的，因此len2为左右节点的len1之和。 若该节点的cnt = 0，说明没被完全覆盖，直接用其左右节点更新。 还要注意特判叶子节点。 */ void maintain(int v) { if(tree[v].cnt >= 2) { tree[v].len1 = tree[v].len2 = x[tree[v].r+1] - x[tree[v].l]; return; } if(tree[v].cnt == 1) { tree[v].len1 = x[tree[v].r+1] - x[tree[v].l]; if(tree[v].l == tree[v].r) tree[v].len2 = 0; else tree[v].len2 = tree[v*2].len1 + tree[v*2+1].len1; return; } if(tree[v].cnt == 0) { if(tree[v].l == tree[v].r) tree[v].len2 = tree[v].len1 = 0; else { tree[v].len1 = tree[v*2].len1 + tree[v*2+1].len1; tree[v].len2 = tree[v*2].len2 + tree[v*2+1].len2; } return; } } void update(int v, int l, int r, int tag) { if(tree[v].l == l && tree[v].r == r) { tree[v].cnt += tag; maintain(v); return; } int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) update(v*2,l,r,tag); else if(l > mid) update(v*2+1,l,r,tag); else { update(v*2,l,mid,tag); update(v*2+1,mid+1,r,tag); } maintain(v); return; } int main() { int test,n; double x1,y1,x2,y2; int cnt,k; scanf(%d,&test); while(test--) { scanf(%d,&n); cnt = 0; memset(x,0,sizeof(x)); for(int i = 1; i <= n; i++) { scanf(%lf %lf %lf %lf,&x1,&y1,&x2,&y2); line[++cnt] = (struct Line){x1,x2,y1,1}; x[cnt] = x1; line[++cnt] = (struct Line){x1,x2,y2,-1}; x[cnt] = x2; } sort(x+1,x+1+cnt); sort(line+1,line+1+cnt); k = 1; for(int i = 2; i <= cnt; i++) { if(x[i] != x[i-1]) x[++k] = x[i]; } build(1,1,k); double ans = 0; for(int i = 1; i < cnt; i++) { int l = Binsearch(1,k,line[i].x1); int r = Binsearch(1,k,line[i].x2)-1; update(1,l,r,line[i].tag); ans += (line[i+1].y - line[i].y) * tree[1].len2; } printf(%.2lf ,ans); } return 0; }