【特集】線分ツリー(完全版)

23356 ワード
データ構造 c query ヤフー Intervals
セグメントツリーは、セグメントツリーに似た二叉検索ツリーで、1つの区間をいくつかのユニット区間に分割し、各ユニット区間はセグメントツリーのリーフノードに対応します.セグメントツリー内の各非葉ノード[a,b]について,その左息子が示す区間は[a,(a+b)/2]、右息子が示す区間は[(a+b)/2+1,b]である.したがって,セグメントツリーは平衡二叉木であり,最後のサブノード数はN,すなわちセグメント区間全体の長さである.
セグメントツリーを使用すると、あるノードが複数のセグメントに現れる回数をすばやく検索できます.時間的複雑度はO(logn)です.最適化されていない空間的複雑度は2 Nなので、離散化して空間を圧縮する必要がある場合があります.
以下は、私が大牛を転載したブログです.
コードの前に、私のセグメントツリースタイルをいくつか紹介します.
maxnはテーマが与える最大区間であり、ノード数は4倍、正確にはノード数はmaxnの最小2 xの2倍より大きい.
lsonとrsonはノードを表す左の息子と右の息子を分解し,パラメータを伝達するたびにこれらの変数に固定されるため,比較的便利な表示に用いることができる.
以前の書き方では各ノードが示す区間を別の2つの配列で記録していましたが、実はこの区間は保存する必要はなく、計算しながら伝えればいいので、関数を書くときに2つのパラメータを多く書くだけで、lsonとrsonの事前定義に合わせて便利ですPushUP(int rt)は、現在のノードの情報を親ノードに更新する.
PushDown(int rt)は、現在のノードの情報を息子ノードに更新する.
rtは、現在のサブツリーのルート、すなわち現在位置するノードを表す.
これらの問題を整理した後、線分樹の問題は全体的に以下の4つの部分に分けることができると思います.
単点更新:最も基本的な線分木で、葉ノードのみを更新し、PushUP(int r)という関数で情報を更新します.
hdu 1166敵兵布陣題意: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:
",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
",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
",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
",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
",query(x , 1 , h , 1));
		}
	}
	return 0;
}
練習poj2828 Buy Tickets poj2886 Who Gets the Most Candies?

セグメント更新(通常は初心者にとってはハードル)は、遅延マーク(または怠惰マーク)を使用する必要があります.簡単に言えば、更新するたびに最後まで更新しないで、遅延マークで更新を次回の更新or問い合わせが必要なときに遅延させます.
hdu 1698 Just a Hook題意:O(-1)構想:O(-1)線分ツリー機能:update:セグメント置換(query 1回の総区間のみのため、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.
",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
",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
标题:壁にポスターを贴って、ポスターは互いに覆うことができて、最后にいくつかのポスターの考え方を见ることができます:この问题のデータの范囲はとても大きくて、直接タイムアウト+メモリを超えて、離散化する必要があります:離散化は简単に言えば私达の必要な値だけを取って使うことができて、例えば区间[10002012],[199902012]私达は[-∞,999][10011999][1991999][20012011][2013,+∞]これらの値を使うことができなくて、だから私は100019902002012だけで十分で、それをそれぞれ0,1,2,3にマッピングして、複雑度が大きく下がったので離散化してすべての必要な値を保存して、並べ替えた後に、それぞれ1~nにマッピングして、このように複雑度はずっと小さくて、この問題の難点は数字ごとに実は1つの単位の長さ(1つの点ではありません)を表していることにあります.このような一般的な離散化は多くの誤り(私の以前のコード、pojという問題のデータが非常に弱いことを含む)をもたらす次の2つの簡単な例は一般的な離散化の欠陥を体現できるはずである:例1:1-10 1-45-10例2:1-10-4-10一般的な離散化後、[1,4][1,2][3,4]線分2が[1,2]、線分3が[3,4]をカバーし、では、線分1は完全に覆われていますか?例1は完全に覆われているが、例2は覆われていないこの欠陥を解決するために、並べ替え後の配列に処理を加えることができる.例えば[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] + 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
",cnt);
	}
	return 0;
}
poj 3225 Help with Intervals 标题:区間操作、渡し、そして、補等構想:我々は1つの操作で分析する:(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を交換する操作であり、私たちは異種または操作と呼ぶことができる.私たちはこの性質を知ることができる:1つの区間がオーバーライドされた後、以前に異種マークがあるかどうかにかかわらず意味がないので、1つのノードがオーバーライドマークを得たときに異種マークをクリアし、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
",&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の場合は左右の息子の区間を統合する必要がある.
poj 3667 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
",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

スキャンラインのような問題はいくつかの操作を並べ替えて、左から右にスキャンライン(もちろん私たちの頭の中で)でスキャンして、最も典型的なのは矩形の面積と、周長となどの問題です.
hdu 1542 Atlantis題意:矩形面積と構想:浮動小数点数はまず離散化しなければならない.それから矩形を2つの辺に分けて、上辺と下辺に分けて、横軸に対して木を建てて、それから下から上までスキャンして、cntでこの区間の下辺が上辺よりいくつか多いことを表して、sumはこの区間内で覆われた線分の長さの総和を代表して、ここの線分の木の1つの結点は線分の1つの端点ではありませんて、この端点と次の端点の間の線分で、だからテーマの中でr+1、r-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 = 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
Total explored area: %.2lf

",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 {
		if (h == cmp.h) return s > cmp.s;
		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
",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

ピットを占拠して、N本の最後まで更新する線分の木2012/7/10を書く暇があります



線分ツリーとその他の結合練習(補足を歓迎):
hdu3954 Level up
hdu4027 Can you answer these queries?
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
Popularity: 100% [?]
【Ruby】簡単なAPIを叩いてみる（郵便番号検索API）
グラフィックエディタ