POJ 2777——線段樹Lazy的重要性

2020 年 5 月 5 日
筆記
樹的使用

POJ 2777 Count Color ——線段樹Lazy的重要性

原題

                                 Count Color

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 59087 Accepted: 17651
Description

Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.

There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, … L from left to right, each is 1 centimeter long. Now we have to color the board – one segment with only one color. We can do following two operations on the board:

“C A B C” Color the board from segment A to segment B with color C.
“P A B” Output the number of different colors painted between segment A and segment B (including).

In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, … color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.
Input

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains “C A B C” or “P A B” (here A, B, C are integers, and A may be larger than B) as an operation defined previously.
Output

Ouput results of the output operation in order, each line contains a number.
Sample Input

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
Sample Output

2
1
Source

POJ Monthly–2006.03.26,dodo

思路

題目大意

一開始我們有一段長為L的序列，其上每個數都為1，之後我們要處理o個操作，一種是將一個區間全部修改為另一個數，另一種是給我們一個區間，要求我們算出這個區間內有多少種不同的數，每個數的值小於30

思路
- 1.一看區間問題，首先想到了線段樹
- 2.發現種類數量不符合區間加法，但是我想到了set去重
- 3.但是又想到這個去重，會讓複雜度變成約 \(O(o*L*log_2n)\)，這對於1e5量級的L與o是絕對不可以的
- 不過又發現每個數最大為30，那便想到了用二進位來表示一個區間內有多少種數——第幾位為1表示這個區間記憶體在幾，而最終我們拆分這個二進位數，統計1的個數就能得出答案。區間合併的時候，用「或|」就可以完美地將兩個區間的資訊合併而不用擔心去重的問題。
- 還要注意每次區間操作時，先檢查左右端點值，保證l <= r以免被坑
線段樹code：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set> 

using namespace std;

long long ff[400005];
int n, t, oo;

long long qu(int o, int l, int r, int x, int y)
{
	if (l >= x && r <= y)
	{
		return ff[o];
	}
	int mid = (l + r) >> 1;
	long long ans1 = 0;
	long long ans2 = 0;
	if (x <= mid)
	{
		ans1 = qu(o << 1, l, mid, x, y);
	}
	if (y > mid)
	{
		ans2 = qu(o << 1 | 1, mid + 1, r, x, y);
	}
	return ans2 | ans1;
}

void ch(int o, int l, int r, int x, int y, int v)
{
	if (l == r)
	{
		ff[o] = (1 << (v - 1));
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid)
	{
		ch(o << 1, l, mid, x, y, v);
	}
	if (y > mid)
	{
		ch(o << 1 | 1, mid + 1, r, x, y, v);
	}
	ff[o] = ff[o << 1] | ff[o << 1 | 1];
}

int main()
{
	scanf("%d%d%d", &n, &t, &oo);
	for (int i = 1; i <= 4 * n; ++i)
	{
		ff[i] = 1;
	}
	while (oo--)
	{
		char cc;
		scanf("\n%c", &cc);
		if (cc == 'C')
		{
			int ll, rr, tt;
			scanf("%d%d%d", &ll, &rr, &tt);
			if (ll > rr)
			{
				int tt = rr;
				rr = ll;
				ll = tt;
			}
			ch(1, 1, n, ll, rr, tt);
		}
		else
		{
			int ll, rr;
			scanf("%d%d", &ll, &rr);
			if (ll > rr)
			{
				int tt = rr;
				rr = ll;
				ll = tt;
			}
			long long cco = qu(1, 1, n, ll, rr);
			int co = 0;
			while (cco)
			{
				if (cco & 1)
				{
					++co;
				}
				cco >>= 1;
			}
			printf("%d\n", co);
		}
	}
	return 0;
}

這結束了嗎？

我一開始感到一陣不解，因為計算次數最多是 o*t 約等於 3e6 的量級，不過看這複雜度，，很是危險

好吧缺了些東西，這就是線段樹的lazy標記，因為我們沒有設置lazy標記，所以導致冗餘計算很多，lazy標記的加入也較為簡單，新開4*L的數組空間，在修改操作的區間包含當前區間時，進行標記，並且在其他操作之前進行下放即可，這一操作可以減少大量的計算，是一種不可缺少的優化

AC程式碼

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set> 

using namespace std;

int ff[400005], ad[400005];
int n, t, oo;

void pd(int o)
{
	ad[o << 1] = ad[o];
	ad[o << 1 | 1] = ad[o];
	ff[o << 1] = ad[o];
	ff[o << 1 | 1] = ad[o];
	ad[o] = 0;
}

int qu(int o, int l, int r, int x, int y)
{
	if (l >= x && r <= y)
	{
		return ff[o];
	}
	if (ad[o])
	{
		pd(o);
	}
	int mid = (l + r) >> 1;
	int ans1 = 0;
	int ans2 = 0;
	if (x <= mid)
	{
		ans1 = qu(o << 1, l, mid, x, y);
	}
	if (y > mid)
	{
		ans2 = qu(o << 1 | 1, mid + 1, r, x, y);
	}
	return ans2 | ans1;
}

void ch(int o, int l, int r, int x, int y, int v)
{
	if (l >= x && y >= r)
	{
		ff[o] = (1 << (v - 1));
		ad[o] = (1 << (v - 1));
		return;
	}
	if (ad[o])
	{
		pd(o);
	}
	int mid = (l + r) >> 1;
	if (x <= mid)
	{
		ch(o << 1, l, mid, x, y, v);
	}
	if (y > mid)
	{
		ch(o << 1 | 1, mid + 1, r, x, y, v);
	}
	ff[o] = ff[o << 1] | ff[o << 1 | 1];
}

int main()
{
	scanf("%d%d%d", &n, &t, &oo);
	for (int i = 1; i <= 4 * n; ++i)
	{
		ff[i] = 1;
	}
	while (oo--)
	{
		char cc;
		scanf("\n%c", &cc);
		if (cc == 'C')
		{
			int ll, rr, tt;
			scanf("%d%d%d", &ll, &rr, &tt);
			if (ll > rr)
			{
				int tt = rr;
				rr = ll;
				ll = tt;
			}
			ch(1, 1, n, ll, rr, tt);
		}
		else
		{
			int ll, rr;
			scanf("%d%d", &ll, &rr);
			if (ll > rr)
			{
				int tt = rr;
				rr = ll;
				ll = tt;
			}
			int cco = qu(1, 1, n, ll, rr);
			int co = 0;
			while (cco)
			{
				if (cco & 1)
				{
					++co;
				}
				cco >>= 1;
			}
			printf("%d\n", co);
		}
	}
	return 0;
}

數據結構在可行的範圍內能優化就要優化，不能抱有僥倖心理而增加自己的WA，用線段樹處理區間修改類問題時，一定要考慮能否用標記來優化。

Tags: 樹的使用