線段樹完全版

2019-11-08 18:51:40
字體：大中小
來源：轉載
供稿：網友
轉載自：NotOnlySuccess的博客【完全版】線段樹很早前寫的那篇線段樹專輯至今一直是本博客閱讀點擊量最大的一片文章,當時覺得挺自豪的,還去pku打廣告,但是現在我自己都不太好意思去看那篇文章了,覺得當時的代碼風格實在是太丑了,很多線段樹的初學者可能就是看著這篇文章來練習的,如果不小心被我培養出了這么糟糕的風格,實在是過意不去,正好過幾天又要給集訓隊講解線段樹,所以決定把這些題目重新寫一遍,順便把近年我接觸到的一些新題更新上去~;并且學習了splay等更高級的數據結構后對線段樹的體會有更深了一層,線段樹的寫法也就比以前飄逸,簡潔且方便多了. 在代碼前先介紹一些我的線段樹風格: maxn是題目給的最大區間,而節點數要開4倍,確切的來說節點數要開大于maxn的最小2x的兩倍lson和rson分辨表示結點的左兒子和右兒子,由于每次傳參數的時候都固定是這幾個變量,所以可以用預定于比較方便的表示以前的寫法是另外開兩個個數組記錄每個結點所表示的區間,其實這個區間不必保存,一邊算一邊傳下去就行,只需要寫函數的時候多兩個參數,結合lson和rson的預定義可以很方便PushUP(int rt)是把當前結點的信息更新到父結點PushDown(int rt)是把當前結點的信息更新給兒子結點rt表示當前子樹的根(root),也就是當前所在的結點整理這些題目后我覺得線段樹的題目整體上可以分成以下四個部分: 單點更新:最最基礎的線段樹,只更新葉子節點,然后把信息用PushUP(int r)這個函數更新上來hdu1166 敵兵布陣題意:O(-1)思路:O(-1)線段樹功能:update:單點增減 query:區間求和
#include <cstdio>   #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1  const int maxn = 55555;  int sum[maxn<<2];  void PushUP(int rt) {         sum[rt] = sum[rt<<1] + sum[rt<<1|1];  }  void build(int l,int r,int rt) {         if (l == r) {                scanf("%d",&sum[rt]);                return ;         }         int m = (l + r) >> 1;         build(lson);         build(rson);         PushUP(rt);  }  void update(int p,int add,int l,int r,int rt) {         if (l == r) {                sum[rt] += add;                return ;         }         int m = (l + r) >> 1;         if (p <= m) update(p , add , lson);         else update(p , add , rson);         PushUP(rt);  }  int query(int L,int R,int l,int r,int rt) {         if (L <= l && r <= R) {                return sum[rt];         }         int m = (l + r) >> 1;         int ret = 0;         if (L <= m) ret += query(L , R , lson);         if (R > m) ret += query(L , R , rson);         return ret;  }  int main() {         int T , n;         scanf("%d",&T);         for (int cas = 1 ; cas <= T ; cas ++) {                PRintf("Case %d:/n",cas);                scanf("%d",&n);                build(1 , n , 1);                char op[10];                while (scanf("%s",op)) {                       if (op[0] == 'E') break;                       int a , b;                       scanf("%d%d",&a,&b);                       if (op[0] == 'Q') printf("%d/n",query(a , b , 1 , n , 1));                       else if (op[0] == 'S') update(a , -b , 1 , n , 1);                       else update(a , b , 1 , n , 1);                }         }         return 0;  }hdu1754 I Hate It題意:O(-1)思路:O(-1)線段樹功能:update:單點替換 query:區間最值#include <cstdio>  #include <algorithm>  using namespace std;     #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1  const int maxn = 222222;  int MAX[maxn<<2];  void PushUP(int rt) {         MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);  }  void build(int l,int r,int rt) {         if (l == r) {                scanf("%d",&MAX[rt]);                return ;         }         int m = (l + r) >> 1;         build(lson);         build(rson);         PushUP(rt);  }  void update(int p,int sc,int l,int r,int rt) {         if (l == r) {                MAX[rt] = sc;                return ;         }         int m = (l + r) >> 1;         if (p <= m) update(p , sc , lson);         else update(p , sc , rson);         PushUP(rt);  }  int query(int L,int R,int l,int r,int rt) {         if (L <= l && r <= R) {                return MAX[rt];         }         int m = (l + r) >> 1;         int ret = 0;         if (L <= m) ret = max(ret , query(L , R , lson));         if (R > m) ret = max(ret , query(L , R , rson));         return ret;  }  int main() {         int n , m;         while (~scanf("%d%d",&n,&m)) {                build(1 , n , 1);                while (m --) {                       char op[2];                       int a , b;                       scanf("%s%d%d",op,&a,&b);                       if (op[0] == 'Q') printf("%d/n",query(a , b , 1 , n , 1));                       else update(a , b , 1 , n , 1);                }         }         return 0;  } hdu1394 Minimum Inversion Number題意:求Inversion后的最小逆序數思路:用O(nlogn)復雜度求出最初逆序數后,就可以用O(1)的復雜度分別遞推出其他解線段樹功能:update:單點增減 query:區間求和#include <cstdio>  #include <algorithm>  using namespace std;     #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1  const int maxn = 5555;  int sum[maxn<<2];  void PushUP(int rt) {         sum[rt] = sum[rt<<1] + sum[rt<<1|1];  }  void build(int l,int r,int rt) {         sum[rt] = 0;         if (l == r) return ;         int m = (l + r) >> 1;         build(lson);         build(rson);  }  void update(int p,int l,int r,int rt) {         if (l == r) {                sum[rt] ++;                return ;         }         int m = (l + r) >> 1;         if (p <= m) update(p , lson);         else update(p , rson);         PushUP(rt);  }  int query(int L,int R,int l,int r,int rt) {         if (L <= l && r <= R) {                return sum[rt];         }         int m = (l + r) >> 1;         int ret = 0;         if (L <= m) ret += query(L , R , lson);         if (R > m) ret += query(L , R , rson);         return ret;  }  int x[maxn];  int main() {         int n;         while (~scanf("%d",&n)) {                build(0 , n - 1 , 1);                int sum = 0;                for (int i = 0 ; i < n ; i ++) {                       scanf("%d",&x[i]);                       sum += query(x[i] , n - 1 , 0 , n - 1 , 1);                       update(x[i] , 0 , n - 1 , 1);                }                int ret = sum;                for (int i = 0 ; i < n ; i ++) {                       sum += n - x[i] - x[i] - 1;                       ret = min(ret , sum);                }                printf("%d/n",ret);         }         return 0;  }hdu2795 Billboard題意:h*w的木板,放進一些1*L的物品,求每次放空間能容納且最上邊的位子思路:每次找到最大值的位子,然后減去L線段樹功能:query:區間求最大值的位子(直接把update的操作在query里做了)#include <cstdio>  #include <algorithm>  using namespace std;     #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1  const int maxn = 222222;  int h , w , n;  int MAX[maxn<<2];  void PushUP(int rt) {         MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);  }  void build(int l,int r,int rt) {         MAX[rt] = w;         if (l == r) return ;         int m = (l + r) >> 1;         build(lson);         build(rson);  }  int query(int x,int l,int r,int rt) {         if (l == r) {                MAX[rt] -= x;                return l;         }         int m = (l + r) >> 1;         int ret = (MAX[rt<<1] >= x) ? query(x , lson) : query(x , rson);         PushUP(rt);         return ret;  }  int main() {         while (~scanf("%d%d%d",&h,&w,&n)) {                if (h > n) h = n;                build(1 , h , 1);                while (n --) {                       int x;                       scanf("%d",&x);                       if (MAX[1] < x) puts("-1");                       else printf("%d/n",query(x , 1 , h , 1));                }         }         return 0;  }練習: poj2828 Buy Ticketspoj2886 Who Gets the Most Candies?/*************************************************************************************************************/成段更新(通常這對初學者來說是一道坎),需要用到延遲標記(或者說懶惰標記),簡單來說就是每次更新的時候不要更新到底,用延遲標記使得更新延遲到下次需要更新or詢問到的時候 hdu1698 Just a Hook題意:O(-1)思路:O(-1)線段樹功能:update:成段替換 (由于只query一次總區間,所以可以直接輸出1結點的信息)#include <cstdio>  #include <algorithm>  using namespace std;     #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1  const int maxn = 111111;  int h , w , n;  int col[maxn<<2];  int sum[maxn<<2];  void PushUp(int rt) {         sum[rt] = sum[rt<<1] + sum[rt<<1|1];  }  void PushDown(int rt,int m) {         if (col[rt]) {                col[rt<<1] = col[rt<<1|1] = col[rt];                sum[rt<<1] = (m - (m >> 1)) * col[rt];                sum[rt<<1|1] = (m >> 1) * col[rt];                col[rt] = 0;         }  }  void build(int l,int r,int rt) {         col[rt] = 0;         sum[rt] = 1;         if (l == r) return ;         int m = (l + r) >> 1;         build(lson);         build(rson);         PushUp(rt);  }  void update(int L,int R,int c,int l,int r,int rt) {         if (L <= l && r <= R) {                col[rt] = c;                sum[rt] = c * (r - l + 1);                return ;         }         PushDown(rt , r - l + 1);         int m = (l + r) >> 1;         if (L <= m) update(L , R , c , lson);         if (R > m) update(L , R , c , rson);         PushUp(rt);  }  int main() {         int T , n , m;         scanf("%d",&T);         for (int cas = 1 ; cas <= T ; cas ++) {                scanf("%d%d",&n,&m);                build(1 , n , 1);                while (m --) {                       int a , b , c;                       scanf("%d%d%d",&a,&b,&c);                       update(a , b , c , 1 , n , 1);                }                printf("Case %d: The total value of the hook is %d./n",cas , sum[1]);         }         return 0;  }poj3468 A Simple Problem with Integers題意:O(-1)思路:O(-1)線段樹功能:update:成段增減 query:區間求和#include <cstdio>  #include <algorithm>  using namespace std;     #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1  #define LL long long  const int maxn = 111111;  LL add[maxn<<2];  LL sum[maxn<<2];  void PushUp(int rt) {         sum[rt] = sum[rt<<1] + sum[rt<<1|1];  }  void PushDown(int rt,int m) {         if (add[rt]) {                add[rt<<1] += add[rt];                add[rt<<1|1] += add[rt];                sum[rt<<1] += add[rt] * (m - (m >> 1));                sum[rt<<1|1] += add[rt] * (m >> 1);                add[rt] = 0;         }  }  void build(int l,int r,int rt) {         add[rt] = 0;         if (l == r) {                scanf("%lld",&sum[rt]);                return ;         }         int m = (l + r) >> 1;         build(lson);         build(rson);         PushUp(rt);  }  void update(int L,int R,int c,int l,int r,int rt) {         if (L <= l && r <= R) {                add[rt] += c;                sum[rt] += (LL)c * (r - l + 1);                return ;         }         PushDown(rt , r - l + 1);         int m = (l + r) >> 1;         if (L <= m) update(L , R , c , lson);         if (m < R) update(L , R , c , rson);         PushUp(rt);  }  LL query(int L,int R,int l,int r,int rt) {         if (L <= l && r <= R) {                return sum[rt];         }         PushDown(rt , r - l + 1);         int m = (l + r) >> 1;         LL ret = 0;         if (L <= m) ret += query(L , R , lson);         if (m < R) ret += query(L , R , rson);         return ret;  }  int main() {         int N , Q;         scanf("%d%d",&N,&Q);         build(1 , N , 1);         while (Q --) {                char op[2];                int a , b , c;                scanf("%s",op);                if (op[0] == 'Q') {                       scanf("%d%d",&a,&b);                       printf("%lld/n",query(a , b , 1 , N , 1));                } else {                       scanf("%d%d%d",&a,&b,&c);                       update(a , b , c , 1 , N , 1);                }         }         return 0;  }  poj2528 Mayor’s posters題意:在墻上貼海報,海報可以互相覆蓋,問最后可以看見幾張海報思路:這題數據范圍很大,直接搞超時+超內存,需要離散化:離散化簡單的來說就是只取我們需要的值來用,比如說區間[1000,2000],[1990,2012] 我們用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]這些值,所以我只需要1000,1990,2000,2012就夠了,將其分別映射到0,1,2,3,在于復雜度就大大的降下來了所以離散化要保存所有需要用到的值,排序后,分別映射到1~n,這樣復雜度就會小很多很多而這題的難點在于每個數字其實表示的是一個單位長度(并且一個點),這樣普通的離散化會造成許多錯誤(包括我以前的代碼,poj這題數據奇弱)給出下面兩個簡單的例子應該能體現普通離散化的缺陷:1-10 1-4 5-101-10 1-4 6-10為了解決這種缺陷,我們可以在排序后的數組上加些處理,比如說[1,2,6,10]如果相鄰數字間距大于1的話,在其中加上任意一個數字,比如加成[1,2,3,6,7,10],然后再做線段樹就好了.線段樹功能:update:成段替換 query:簡單hash#include <cstdio>  #include <cstring>  #include <algorithm>  using namespace std;  #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1     const int maxn = 11111;  bool hash[maxn];  int li[maxn] , ri[maxn];  int X[maxn*3];  int col[maxn<<4];  int cnt;     void PushDown(int rt) {         if (col[rt] != -1) {                col[rt<<1] = col[rt<<1|1] = col[rt];                col[rt] = -1;         }  }  void update(int L,int R,int c,int l,int r,int rt) {         if (L <= l && r <= R) {                col[rt] = c;                return ;         }         PushDown(rt);         int m = (l + r) >> 1;         if (L <= m) update(L , R , c , lson);         if (m < R) update(L , R , c , rson);  }  void query(int l,int r,int rt) {         if (col[rt] != -1) {                if (!hash[col[rt]]) cnt ++;                hash[ col[rt] ] = true;                return ;         }         if (l == r) return ;         int m = (l + r) >> 1;         query(lson);         query(rson);  }  int Bin(int key,int n,int X[]) {         int l = 0 , r = n - 1;         while (l <= r) {                int m = (l + r) >> 1;                if (X[m] == key) return m;                if (X[m] < key) l = m + 1;                else r = m - 1;         }         return -1;  }  int main() {         int T , n;         scanf("%d",&T);         while (T --) {                scanf("%d",&n);                int nn = 0;                for (int i = 0 ; i < n ; i ++) {                       scanf("%d%d",&li[i] , &ri[i]);                       X[nn++] = li[i];                       X[nn++] = ri[i];                }                sort(X , X + nn);                int m = 1;                for (int i = 1 ; i < nn; i ++) {                       if (X[i] != X[i-1]) X[m ++] = X[i];                }                for (int i = m - 1 ; i > 0 ; i --) {                       if (X[i] != X[i-1] + 1) X[m ++] = X[i] + 1;                }                sort(X , X + m);                memset(col , -1 , sizeof(col));                for (int i = 0 ; i < n ; i ++) {                       int l = Bin(li[i] , m , X);                       int r = Bin(ri[i] , m , X);                       update(l , r , i , 0 , m , 1);                }                cnt = 0;                memset(hash , false , sizeof(hash));                query(0 , m , 1);                printf("%d/n",cnt);         }         return 0;  }  poj3225 Help with Intervals題意:區間操作,交,并,補等思路:我們一個一個操作來分析:(用0和1表示是否包含區間,-1表示該區間內既有包含又有不包含)U:把區間[l,r]覆蓋成1I:把[-∞,l)(r,∞]覆蓋成0D:把區間[l,r]覆蓋成0C:把[-∞,l)(r,∞]覆蓋成0 , 且[l,r]區間0/1互換S:[l,r]區間0/1互換 成段覆蓋的操作很簡單,比較特殊的就是區間0/1互換這個操作,我們可以稱之為異或操作很明顯我們可以知道這個性質:當一個區間被覆蓋后,不管之前有沒有異或標記都沒有意義了所以當一個節點得到覆蓋標記時把異或標記清空而當一個節點得到異或標記的時候,先判斷覆蓋標記,如果是0或1,直接改變一下覆蓋標記,不然的話改變異或標記 開區間閉區間只要數字乘以2就可以處理(偶數表示端點,奇數表示兩端點間的區間)線段樹功能:update:成段替換,區間異或 query:簡單hash#include <cstdio>  #include <cstring>  #include <cctype>  #include <algorithm>  using namespace std;  #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1     const int maxn = 131072;  bool hash[maxn];  int cover[maxn<<2];  int XOR[maxn<<2];  void FXOR(int rt) {         if (cover[rt] != -1) cover[rt] ^= 1;         else XOR[rt] ^= 1;  }  void PushDown(int rt) {         if (cover[rt] != -1) {                cover[rt<<1] = cover[rt<<1|1] = cover[rt];                XOR[rt<<1] = XOR[rt<<1|1] = 0;                cover[rt] = -1;         }         if (XOR[rt]) {                FXOR(rt<<1);                FXOR(rt<<1|1);                XOR[rt] = 0;         }  }  void update(char op,int L,int R,int l,int r,int rt) {         if (L <= l && r <= R) {                if (op == 'U') {                       cover[rt] = 1;                       XOR[rt] = 0;                } else if (op == 'D') {                       cover[rt] = 0;                       XOR[rt] = 0;                } else if (op == 'C' || op == 'S') {                       FXOR(rt);                }                return ;         }         PushDown(rt);         int m = (l + r) >> 1;         if (L <= m) update(op , L , R , lson);         else if (op == 'I' || op == 'C') {                XOR[rt<<1] = cover[rt<<1] = 0;         }         if (m < R) update(op , L , R , rson);         else if (op == 'I' || op == 'C') {                XOR[rt<<1|1] = cover[rt<<1|1] = 0;         }  }  void query(int l,int r,int rt) {         if (cover[rt] == 1) {                for (int it = l ; it <= r ; it ++) {                       hash[it] = true;                }                return ;         } else if (cover[rt] == 0) return ;         if (l == r) return ;         PushDown(rt);         int m = (l + r) >> 1;         query(lson);         query(rson);  }  int main() {         cover[1] = XOR[1] = 0;         char op , l , r;         int a , b;         while ( ~scanf("%c %c%d,%d%c/n",&op , &l , &a , &b , &r) ) {                a <<= 1 , b <<= 1;                if (l == '(') a ++;                if (r == ')') b --;                if (a > b) {                       if (op == 'C' || op == 'I') {                              cover[1] = XOR[1] = 0;                       }                } else update(op , a , b , 0 , maxn , 1);         }         query(0 , maxn , 1);         bool flag = false;         int s = -1 , e;         for (int i = 0 ; i <= maxn ; i ++) {                if (hash[i]) {                       if (s == -1) s = i;                       e = i;                } else {                       if (s != -1) {                              if (flag) printf(" ");                              flag = true;                              printf("%c%d,%d%c",s&1?'(':'[' , s>>1 , (e+1)>>1 , e&1?')':']');                              s = -1;                       }                }         }         if (!flag) printf("empty set");         puts("");         return 0;  }  練習: poj1436 Horizontally Visible Segmentspoj2991 CraneAnother LCISBracket Sequence區間合并這類題目會詢問區間中滿足條件的連續最長區間,所以PushUp的時候需要對左右兒子的區間進行合并 poj3667 Hotel題意:1 a:詢問是不是有連續長度為a的空房間,有的話住進最左邊2 a b:將[a,a+b-1]的房間清空思路:記錄區間中最長的空房間線段樹操作:update:區間替換 query:詢問滿足條件的最左斷點#include <cstdio>  #include <cstring>  #include <cctype>  #include <algorithm>  using namespace std;  #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1     const int maxn = 55555;  int lsum[maxn<<2] , rsum[maxn<<2] , msum[maxn<<2];  int cover[maxn<<2];     void PushDown(int rt,int m) {         if (cover[rt] != -1) {                cover[rt<<1] = cover[rt<<1|1] = cover[rt];                msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] ? 0 : m - (m >> 1);                msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] ? 0 : (m >> 1);                cover[rt] = -1;         }  }  void PushUp(int rt,int m) {         lsum[rt] = lsum[rt<<1];         rsum[rt] = rsum[rt<<1|1];         if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1];         if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1];         msum[rt] = max(lsum[rt<<1|1] + rsum[rt<<1] , max(msum[rt<<1] , msum[rt<<1|1]));  }  void build(int l,int r,int rt) {         msum[rt] = lsum[rt] = rsum[rt] = r - l + 1;         cover[rt] = -1;         if (l == r) return ;         int m = (l + r) >> 1;         build(lson);         build(rson);  }  void update(int L,int R,int c,int l,int r,int rt) {         if (L <= l && r <= R) {                msum[rt] = lsum[rt] = rsum[rt] = c ? 0 : r - l + 1;                cover[rt] = c;                return ;         }         PushDown(rt , r - l + 1);         int m = (l + r) >> 1;         if (L <= m) update(L , R , c , lson);         if (m < R) update(L , R , c , rson);         PushUp(rt , r - l + 1);  }  int query(int w,int l,int r,int rt) {         if (l == r) return l;         PushDown(rt , r - l + 1);         int m = (l + r) >> 1;         if (msum[rt<<1] >= w) return query(w , lson);         else if (rsum[rt<<1] + lsum[rt<<1|1] >= w) return m - rsum[rt<<1] + 1;         return query(w , rson);  }  int main() {         int n , m;         scanf("%d%d",&n,&m);         build(1 , n , 1);         while (m --) {                int op , a , b;                scanf("%d",&op);                if (op == 1) {                       scanf("%d",&a);                       if (msum[1] < a) puts("0");                       else {                              int p = query(a , 1 , n , 1);                              printf("%d/n",p);                              update(p , p + a - 1 , 1 , 1 , n , 1);                       }                } else {                       scanf("%d%d",&a,&b);                       update(a , a + b - 1 , 0 , 1 , n , 1);                }         }         return 0;  }練習: hdu3308 LCIShdu3397 Sequence Operationhdu2871 Memory Controlhdu1540 Tunnel WarfareCF46-D Parking Lot掃描線這類題目需要將一些操作排序,然后從左到右用一根掃描線(當然是在我們腦子里)掃過去最典型的就是矩形面積并,周長并等題hdu1542 Atlantis題意:矩形面積并思路:浮點數先要離散化;然后把矩形分成兩條邊,上邊和下邊,對橫軸建樹,然后從下到上掃描上去,用cnt表示該區間下邊比上邊多幾個線段樹操作:update:區間增減 query:直接取根節點的值#include <cstdio>  #include <cstring>  #include <cctype>  #include <algorithm>  using namespace std;  #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1     const int maxn = 2222;  int cnt[maxn << 2];  double sum[maxn << 2];  double X[maxn];  struct Seg {         double h , l , r;         int s;         Seg(){}         Seg(double a,double b,double c,int d) : l(a) , r(b) , h(c) , s(d) {}         bool operator < (const Seg &cmp) const {                return h < cmp.h;         }  }ss[maxn];  void PushUp(int rt,int l,int r) {         if (cnt[rt]) sum[rt] = X[r+1] - X[l];         else if (l == r) sum[rt] = 0;         else sum[rt] = sum[rt<<1] + sum[rt<<1|1];  }  void update(int L,int R,int c,int l,int r,int rt) {         if (L <= l && r <= R) {                cnt[rt] += c;                PushUp(rt , l , r);                return ;         }         int m = (l + r) >> 1;         if (L <= m) update(L , R , c , lson);         if (m < R) update(L , R , c , rson);         PushUp(rt , l , r);  }  int Bin(double key,int n,double X[]) {         int l = 0 , r = n - 1;         while (l <= r) {                int m = (l + r) >> 1;                if (X[m] == key) return m;                if (X[m] < key) l = m + 1;                else r = m - 1;         }         return -1;  }  int main() {         int n , cas = 1;         while (~scanf("%d",&n) && n) {                int m = 0;                while (n --) {                       double a , b , c , d;                       scanf("%lf%lf%lf%lf",&a,&b,&c,&d);                       X[m] = a;                       ss[m++] = Seg(a , c , b , 1);                       X[m] = c;                       ss[m++] = Seg(a , c , d , -1);                }                sort(X , X + m);                sort(ss , ss + m);                int k = 1;                for (int i = 1 ; i < m ; i ++) {                       if (X[i] != X[i-1]) X[k++] = X[i];                }                memset(cnt , 0 , sizeof(cnt));                memset(sum , 0 , sizeof(sum));                double ret = 0;                for (int i = 0 ; i < m - 1 ; i ++) {                       int l = Bin(ss[i].l , k , X);                       int r = Bin(ss[i].r , k , X) - 1;                       if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1);                       ret += sum[1] * (ss[i+1].h - ss[i].h);                }                printf("Test case #%d/nTotal explored area: %.2lf/n/n",cas++ , ret);         }         return 0;  }hdu1828 Picture題意:矩形周長并思路:與面積不同的地方是還要記錄豎的邊有幾個(numseg記錄),并且當邊界重合的時候需要合并(用lbd和rbd表示邊界來輔助)線段樹操作:update:區間增減 query:直接取根節點的值#include <cstdio>  #include <cstring>  #include <cctype>  #include <algorithm>  using namespace std;  #define lson l , m , rt << 1  #define rson m + 1 , r , rt << 1 | 1     const int maxn = 22222;  struct Seg{         int l , r , h , s;         Seg() {}         Seg(int a,int b,int c,int d):l(a) , r(b) , h(c) , s(d) {}         bool operator < (const Seg &cmp) const {                return h < cmp.h;         }  }ss[maxn];  bool lbd[maxn<<2] , rbd[maxn<<2];  int numseg[maxn<<2];  int cnt[maxn<<2];  int len[maxn<<2];  void PushUP(int rt,int l,int r) {         if (cnt[rt]) {                lbd[rt] = rbd[rt] = 1;                len[rt] = r - l + 1;                numseg[rt] = 2;         } else if (l == r) {                len[rt] = numseg[rt] = lbd[rt] = rbd[rt] = 0;         } else {                lbd[rt] = lbd[rt<<1];                rbd[rt] = rbd[rt<<1|1];                len[rt] = len[rt<<1] + len[rt<<1|1];                numseg[rt] = numseg[rt<<1] + numseg[rt<<1|1];                if (lbd[rt<<1|1] && rbd[rt<<1]) numseg[rt] -= 2;//兩條線重合         }  }  void update(int L,int R,int c,int l,int r,int rt) {         if (L <= l && r <= R) {                cnt[rt] += c;                PushUP(rt , l , r);                return ;         }         int m = (l + r) >> 1;         if (L <= m) update(L , R , c , lson);         if (m < R) update(L , R , c , rson);         PushUP(rt , l , r);  }  int main() {         int n;         while (~scanf("%d",&n)) {                int m = 0;                int lbd = 10000, rbd = -10000;                for (int i = 0 ; i < n ; i ++) {                       int a , b , c , d;                       scanf("%d%d%d%d",&a,&b,&c,&d);                       lbd = min(lbd , a);                       rbd = max(rbd , c);                       ss[m++] = Seg(a , c , b , 1);                       ss[m++] = Seg(a , c , d , -1);                }                sort(ss , ss + m);                int ret = 0 , last = 0;                for (int i = 0 ; i < m ; i ++) {                       if (ss[i].l < ss[i].r)                         update(ss[i].l , ss[i].r - 1 , ss[i].s , lbd , rbd - 1 , 1);                       ret += numseg[1] * (ss[i+1].h - ss[i].h);                       ret += abs(len[1] - last);                       last = len[1];                }                printf("%d/n",ret);         }         return 0;  } 練習 hdu3265 Postershdu3642 Get The Treasurypoj2482 Stars in Your Windowpoj2464 Brownie Points IIhdu3255 Farmingural1707 Hypnotoad’s Secretuva11983 Weird Advertisement  線段樹與其他結合練習(歡迎大家補充): hdu3333 Turing Treehdu3874 Necklacehdu3016 Man Downhdu3340 Rain in ACStarzju3511 Cake RobberyUESTC1558 Charitable ExchangeCF85-D Sum of MediansspojGSS2 Can you answer these queries II