轉載自：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 Tickets
poj2886 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-10
1-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]覆蓋成1
I:把[-∞,l)(r,∞]覆蓋成0
D:把區間[l,r]覆蓋成0
C:把[-∞,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 Segments
poj2991 Crane
Another LCIS
Bracket 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 LCIS
hdu3397 Sequence operation
hdu2871 Memory Control
hdu1540 Tunnel Warfare
CF46-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 Posters
hdu3642 Get The Treasury
poj2482 Stars in Your Window
poj2464 Brownie Points II
hdu3255 Farming
ural1707 Hypnotoad’s Secret
uva11983 Weird Advertisement
?
?
線段樹與其他結合練習(歡迎大家補充):
?
hdu3333 Turing Tree
hdu3874 Necklace
hdu3016 Man Down
hdu3340 Rain in ACStar
zju3511 Cake Robbery
UESTC1558 Charitable Exchange
CF85-D Sum of Medians
spojGSS2 Can you answer these queries II
- 前言
- 1608 - Non-boring sequences（折半遞歸。。暫且這么叫吧）
- 11491 - Erasing and Winning（貪心）
- 1619 - Feel Good（高效算法-利用數據結構優化-優先隊列）
- hdu-4127 Flood-it!（IDA*算法）
- UESTC 1132 醬神賞花 （用數據結構優化DP）
- HDU 2874 Connections between cities（LCA離線算法）
- Codeforces Round #317 A. Lengthening Sticks（組合+容斥）
- HDU 3085 Nightmare Ⅱ（雙向BFS）
- HDU 5592 ZYB&#39;s Premutation（二分+樹狀數組）
- Codeforces Round #320 (Div. 1) C. Weakness and Poorness（三分）
- HDU 5212 Code（容斥）
- HDU 5596 GTW likes gt（multiset）
- FZU 2159 WuYou（貪心）
- HDU 3450 Counting Sequences（DP + 樹狀數組）
- HDU 5493 Queue（二分+樹狀數組）
- HDU 1166 敵兵布陣（線段樹版）
- HDU 1394 Minimum Inversion Number（樹狀數組||線段樹）
- HDU 2795 Billboard（線段樹）
- POJ 2828 Buy Tickets（樹狀數組）
- 《完全版線段樹》- NotOnlySuccess
- POJ 2886 Who Gets the Most Candies?（樹狀數組+二分）
- HDU 1698 Just a Hook（線段樹區間修改）
- POJ 3468 A Simple Problem with Integers（線段樹|區間加減&amp;&amp;區間求和）
- POJ 2528 Mayor&#39;s posters（線段樹區間修改+離散化）
- HDU 5606 tree（并查集）
- POJ 3734 Blocks（矩陣優化+DP）
- POJ 3233 Matrix Power Series（矩陣優化）
- HDU 5607 graph（矩陣優化+概率DP）
- POJ 2777 Count Color（線段樹區間修改+位運算）
- POJ 1436 Horizontally Visible Segments（線段樹區間修改）
- UVA 1513 - Movie collection（樹狀數組）
- UVA 1232 - SKYLINE（線段樹區間更新）
- 11525 - Permutation（二分+樹狀數組）
- 11402 - Ahoy, Pirates!（線段樹區間更新（標記重疊的處理））
- Educational Codeforces Round 6 E. New Year Tree（DFS序+線段樹）