POJ 2528 - Mayor's posters 線段樹+離散化

%%%

//感覺部落客對于離散的解釋很好，很感謝。

%%%

//部落客解釋了一下本題離散的特殊性，感謝

如三張海報為：1~10 1~4 6~10

離散化時 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10

第一張海報時：牆的1~4被染為1；

第二張海報時：牆的1~2被染為2

3~4仍為1；

第三張海報時：牆的3~4被染為3，

1~2仍為2。

最終，第一張海報就顯示被完全覆寫了，于是輸出2，但實際上明顯不是這樣，正确輸出為3。

新的離散方法為：在相差大于1的數間加一個數，例如在上面1 4 6 10中間加5（算法中實際上1，4之間，6，10之間都新增了數的）

X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 5, X[ 4 ] = 6， X[ 5 ] = 10

這樣之後，第一次是1,5被染成1；第二次1,2被染成2；第三次4,5被染成3

最終，[1,2]為2，3為1，[4,5]為3，于是輸出正确結果3。

離散化時 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10

第一張海報時：牆的1~4被染為1；

第二張海報時：牆的1~2被染為2

3~4仍為1；

第三張海報時：牆的3~4被染為3，

1~2仍為2。

最終，第一張海報就顯示被完全覆寫了，于是輸出2，但實際上明顯不是這樣，正确輸出為3。

新的離散方法為：在相差大于1的數間加一個數，例如在上面1 4 6 10中間加5（算法中實際上1，4之間，6，10之間都新增了數的）

X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 5, X[ 4 ] = 6， X[ 5 ] = 10

這樣之後，第一次是[1,5]被染成1；第二次[1,2]被染成2；第三次[4,5]被染成3

最終，[1,2]為2，3為1，[4,5]為3，于是輸出正确結果3。

這裡說一下對于代碼的了解

if (left>mid)

update(i * 2 + 1, left, right, val);

else if (right <= mid)

update(i * 2, left, right, val);

else

{

update(i * 2, left, mid, val);

update(i * 2 + 1, mid + 1, right, val);

}

這裡目标區間的左端點大于mid，則需要向右節點進行更新（因為右節點的區間左端點更大）

同理當（right<=mid）或者（left<=mid <=right）時也是如此

代碼是之前從一位dalao那看完後，模仿的，但是之前一直沒有寫這道題目的總結，忘了收藏dalao的部落格，很抱歉.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct point {
	int l, r;
	int mark, sum;
};
point tree[10001 * 4 * 4], num[10001 * 4];
int ans, res[10001 * 4], vis[10001 * 4];
void build(int i, int left, int right)
{
	tree[i].l = left, tree[i].r = right;
	tree[i].mark = tree[i].sum = 0;
	if (left == right) return;
	int mid = (left + right) / 2;
	build(i * 2, left, mid);
	build(i * 2 + 1, mid + 1, right);
}
void update(int i, int left, int right, int val)
{
	if (left <= tree[i].l&&tree[i].r <= right) {
		tree[i].mark = tree[i].sum = val; return;
	}
	//等同于lazy
	if (tree[i].mark)
	{
		tree[i * 2].mark = tree[i * 2 + 1].mark = tree[i].mark;
		tree[i * 2].sum = tree[i * 2 + 1].sum = tree[i].mark;
		tree[i].mark = 0;
	}
	int mid = (tree[i].r + tree[i].l) / 2;
	//此時的mid取決于i是以要判斷mid>left，right<= 的情況。
	if (left>mid) update(i * 2 + 1, left, right, val);
	else if (right <= mid) update(i * 2, left, right, val);
	else
	{
		update(i * 2, left, mid, val);
		update(i * 2 + 1, mid + 1, right, val);
	}
}

//查找
int find(int i)
{
	if (tree[i].l == tree[i].r)
	{
		if (!vis[tree[i].sum])//沒被計算過
		{
			vis[tree[i].sum] = 1;
			++ans;
		}

		return ans;
	}
	//等同于lazy,即延遲更新
	if (tree[i].mark)
	{
		tree[i * 2].mark = tree[i * 2 + 1].mark = tree[i].mark;
		tree[i * 2].sum = tree[i * 2 + 1].sum = tree[i].mark;
		tree[i].mark = 0;
	}
	find(i * 2);
	find(i * 2 + 1);
}
int main()
{
	int t, i, n, tn, tn1, powr, powl;
	scanf("%d", &t);

	if (t == 0)
		return 0;
	while (t--)
	{
		res[0] = 0;
		scanf("%d", &n);
		for (i = 1; i <= n; i++)
		{
			scanf("%d %d", &num[i].l, &num[i].r);
			if (num[i].l>num[i].r) swap(num[i].l, num[i].r);
			res[++res[0]] = num[i].l;
			res[++res[0]] = num[i].r;
		}
		sort(res + 1, res + res[0] + 1);
		//離散化
		tn1 = tn = unique(res + 1, res + res[0] + 1) - res;//去重後得到範圍
		for (i = 2; i<tn; i++)//插入數
			if (res[i] - res[i - 1]>1)
				res[tn1++] = res[i] - 1;
		//每個相鄰的內插補點大于1的時候要插入一個數(就插入x[i]-1好了)
		res[0] = tn1 - 1;//插入後的資料個數
		sort(res + 1, res + res[0] + 1);
		build(1, 1, res[0]);//以新的區間（映射後的範圍）建樹
		for (i = 1; i <= n; i++)
		{
			powl = lower_bound(res + 1, res + 1 + res[0], num[i].l) - res;
			powr = lower_bound(res + 1, res + 1 + res[0], num[i].r) - res;
			//映射後所在位置，進行資料的更新
			update(1, powl, powr, i);
		}
		ans = 0;
		memset(vis, 0, sizeof(vis));
		vis[0] = 1;
		printf("%d\n", find(1));
	}

	return 0;
}