poj 2528 Mayor's posters(離散化+線分ツリー)

http://poj.org/problem?id=2528
タイトル:
市長選挙では、市長一人一人が壁にポスターを貼り、ポスターの間を覆うことができ、貼り付けの順序とポスターの起点と終点を与え、最後にどれだけのポスターが見えるかを聞いた.
離散化に触れたばかりで、まず本人の理解を書きます.
元のデータが大きすぎると、ツリーがメモリを超えます.したがって、これらの数をソートしてから、ソート後のシーケンス番号にマッピングできます.例えば、この問題では、[1,4],[2,6],[8,10],[3,4],[7,10];これらの区間の端点を先に重み付けして(離散化はこの点に注意して、空間を節約することができます)並べ替えた後に 1,2,3,4,6,7,8,10 ;では、これらの数を対応する番号にマッピングできます.
1        2        3        4        6        7         8        10
1        2        3        4        5        6         7         8
原区間は[1,4],[2,5],[7,8],[3,4],[6,8];このようにツリーを作成するには8の空間しか必要とせず,区間端点数値でツリーを作成するには10の空間が必要である.データが大きい場合は、離散化によりスペースが大幅に節約されます.
考え方:
wallは最大1000 0000なので、線分端点座標で直接ツリーを作成すると必ずメモリがオーバーします.だから上記のように離散化してから木を建てます.その後、1枚目から貼り始め、1枚ごとに該当区間のkind値を更新します.最後に再帰統計はいくつの異なるkind値があればよい.

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define C 240
#define S 20
using namespace std;

const int maxn = 100010;

int n;
int np;

struct node
{
	int l,r;
	int val;
}post[10010],tree[80010];

int tmp[100010];
int f[10000010]; //    
int vis[20010]; //        
int cnt;

void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	tree[v].val = -1;
	if(l == r)
		return;
	int mid = (l+r) >> 1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
}

void update(int v, int l, int r, int val)
{
	if(tree[v].l == l && tree[v].r == r)
	{
		tree[v].val = val;
		return;
	}

	if(tree[v].val != -1)
	{
		int mid = (tree[v].l + tree[v].r) >> 1;
		update(v*2,tree[v].l,mid,tree[v].val);
		update(v*2+1,mid+1,tree[v].r,tree[v].val);
		tree[v].val = -1;
	}

	int mid = (tree[v].l + tree[v].r)>>1;
	if(r <= mid)
		update(v*2,l,r,val);
	else if(l > mid)
		update(v*2+1,l,r,val);
	else
	{
		update(v*2,l,mid,val);
		update(v*2+1,mid+1,r,val);
	}
}

int query(int v, int l, int r)
{
	if(tree[v].l == l && tree[v].r == r)
	{
		if(tree[v].val != -1 && !vis[tree[v].val])
		{
			vis[tree[v].val] = 1;
			return 1;
		}
		else if(tree[v].val == -1)
		{
			int mid = (tree[v].l + tree[v].r) >> 1;
			return query(v*2,tree[v].l,mid) + query(v*2+1,mid+1,tree[v].r);
		}
		else
			return 0;
	}
	int mid = (tree[v].l + tree[v].r) >> 1;
	if(r <= mid)
		return query(v*2,l,r);
	else if(l > mid)
		return query(v*2+1,l,r);
	else
		return query(v*2,l,mid) + query(v*2+1,mid+1,r);
}

int main()
{
	int test;
	scanf("%d",&test);

	while(test--)
	{
		scanf("%d",&n);
		np = 0;
		for(int i = 1; i <= n; i++)
		{
			scanf("%d %d",&post[i].l,&post[i].r);
			tmp[np++] = post[i].l;
			tmp[np++] = post[i].r;
		}

		sort(tmp,tmp+np);
		//        
		int k = 1;
		for(int i = 1; i < np; i++)
		{
			while(tmp[i] == tmp[k-1])
			{
				i++;
				if(i == np)
					break;
			}
			if(i == np)
				break;
			tmp[k++] = tmp[i];
		}
		np = k;
		for(int i = 0; i < np; i++)
		{
			f[tmp[i]] = i + 1;
		}
		build(1,1,np);
		for(int i = 1; i <= n; i++)
		{
			update(1,f[post[i].l],f[post[i].r],i);
		}
		memset(vis,0,sizeof(vis));
		int ans = query(1,1,np);
		printf("%d
",ans);
		
	}
	return 0;
}

1、  セグメントツリーは二叉木であり、必ずバランス二叉木であるが、必ずしも完全二叉木ではない.
2、  区間[a,b]については、mid=(a+b)/2とすると、その左サブツリーは[a,mid]、右サブツリーは[mid+1,b]となり、a=bの場合、この区間は線分ツリーの葉であり、下に区切る必要はない.
3、  線分樹は完全二叉木ではありませんが、完全二叉木で構築して保存することができますが、最後の層にはいくつかの葉と葉の間に「空の葉」が現れる可能性があります.これは気にする必要はありません.同様に空の葉に順番に番号を付けて、線分樹を遍歴したときにa=bと判断したとき、「空の葉」は永遠に遍歴しないと考えられます.
4、  完全二叉木で線分ツリーを格納するのは,線分挿入や探索時の効率化のためである.p*2,p*2+1のインデックス方式でpの左右のサブツリーを検索するのはポインタよりずっと速い.
5、線分樹の真髄は、下に検索しないで、下に検索しないで、できるだけ子樹の根の情報を利用して本の木全体の情報を取得することです.線分を挿入したり、フィーチャー値を検索したりするたびに、葉を検索しなければならない場合は、普通の木を直接作るほうが便利です.