一道挺簡單的題，讓我折騰了許久。主要卡在了更新節點後維護父親節點上。後來思路明確了就很容易了。
節點信息：
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; }
杭電 HDU 1033 Edge Edge Time L
淺談程序優化，淺談優化 當初在學校實驗室的時候，常常寫一個
引言 由於Windows 操作系統在很大程度上
原題： n sprinklers are instal
在C++中，引用就是一個變量的別名，它需要用另一個變量或對
在說明什麼是友元之前，我們先說明一下為什麼需要友元與
