POJ 3368 Frequent values 题解 《挑战程序设计竞赛》

POJ 3368 Frequent values

最频繁的数：给定一个非严格单调增数列，请快速求解一个区间内出现最频繁的数的频次。

3.3活用各种数据结构

线段树和平方分割

采用线段树充分利用中间计算结果，定义区间的最大长度为最长连续子区间的长度，定义左孩子区间长度为包含左端点在内的最长连续区间的长度，同理定义右孩子区间。线段树的每个阶段维护这三个信息即可，这样预处理之后合并区间将会变得非常快捷。

在预处理的时候，将数组不断地拆成两半，直至不能再分，也就是只有一个元素，上述三个值都为1（因为三个区间元素都只有一个）。然后往上合并，合并的时候分四种情况讨论：

1. 默认
   继承左孩子的左端、右孩子的右端

2. 左孩子右端和右孩子左端相等
   合并左右孩子更新最大长度。

3. 左孩子左端和右孩子左端相等
   合并左孩子和右孩子的左端

4. 左孩子右端和右孩子右端相等
   合并右孩子和左孩子的右端

举个例子，对于数列

  0     0     1     1     1     1     3     8

构造如下线段树(每个三元组分别代表total_length left_length right_length)：

                     4 2 1                     |
         2 2 2         |         2 2 1         |
   2 2 2   |   2 2 2   |   2 2 2   |   1 1 1   |
1 1 1|1 1 1|1 1 1|1 1 1|1 1 1|1 1 1|1 1 1|1 1 1|
  0     0     1     1     1     1     3     8

查询的时候也进行类似的操作即可。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct SegTree
{
	int n;
	// 本区间最长序列的长度，左右孩子区间最长序列的长度，原来的序列
	vector<int> length, left, right, src;

	struct Result
	{
		int length, l, r;
		Result(int len = 0, int l = 0, int r = 0) : length(len), l(l), r(r){}

		operator int() // 转为int时自动求最大值
		{
			return max(length, max(l, r));
		}
	};

	SegTree(int n, vector<int> &src) : n(n), length(n * 3 + 1), left(n * 3 + 1), right(n * 3 + 1), src(src)
	{
		init(0, 0, n);
	}

	//************************************
	// Method:    init
	// FullName:  SegTree::init
	// Access:    public 
	// Returns:   void
	// Qualifier: 初始化线段树的一个节点
	// Parameter: int p 节点下标
	// Parameter: int l 节点维护区间的起点
	// Parameter: int r 节点维护区间的终点
	//************************************
	void init(int p, int l, int r)
	{
		if (l + 1 == r) // 长度为1
		{
			length[p] = right[p] = left[p] = 1;
			return;
		}

		int pl = p * 2 + 1, pr = p * 2 + 2, mid = (l + r) / 2;

		init(pl, l, mid);
		init(pr, mid, r);

		length[p] = max(length[pl], length[pr]);

		left[p] = left[pl];
		right[p] = right[pr];

		// 左孩子右端和右孩子左端相等
		if (src[mid - 1] == src[mid])
		{
			length[p] = max(length[p], right[pl] + left[pr]);
		}

		// 左孩子左端和右孩子左端相等
		if (src[l] == src[mid])
		{
			left[p] += left[pr];
		}

		// 左孩子右端和右孩子右端相等
		if (src[mid - 1] == src[r - 1])
		{
			right[p] += right[pl];
		}
	}

	//************************************
	// Method:    query
	// FullName:  SegTree::query
	// Access:    public 
	// Returns:   SegTree::Result
	// Qualifier: 查询从a到b的最大长度
	// Parameter: int a 起点
	// Parameter: int b 终点
	//************************************
	Result query(int a, int b)
	{
		return query(a, b, 0, 0, n);
	}

private:
	//************************************
	// Method:    query
	// FullName:  SegTree::query
	// Access:    private 
	// Returns:   SegTree::Result
	// Qualifier: 查询从a到b的最大长度
	// Parameter: int a 起点
	// Parameter: int b 终点
	// Parameter: int p 节点id
	// Parameter: int l 查询起点
	// Parameter: int r 查询终点
	//************************************
	Result query(int a, int b, int p, int l, int r)
	{
		int pl = p * 2 + 1, pr = p * 2 + 2, mid = (l + r) / 2;

		if (b <= l || r <= a)
		{
			return Result();
		}
		else if (a <= l && r <= b)
		{
			return Result(length[p], left[p], right[p]);
		}
		else
		{
			Result child_l = query(a, b, pl, l, mid);
			Result child_r = query(a, b, pr, mid, r);

			Result result(max(child_l.length, child_r.length), child_l.l, child_r.r);

			// 左孩子右端和右孩子左端相等
			if (src[mid - 1] == src[mid])
			{
				result.length = max(result.length, child_l.r + child_r.l);
			}

			// 左右孩子左端相等
			if (src[l] == src[mid])
			{
				result.l += child_r.l;
			}

			// 左右孩子右端相等
			if (src[mid - 1] == src[r - 1])
			{
				result.r += child_l.r;
			}

			return result;
		}
	}
};


///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	while (true)
	{
		int n;
		scanf(" %d", &n);

		if (!n)
		{
			break;
		}
		vector<int> A(n);

		int q;
		scanf(" %d", &q);

		for (int i = 0; i < n; ++i)
		{
			scanf(" %d", &A[i]);
		}

		SegTree tree(n, A);

		for (int i = 0; i < q; ++i)
		{
			int l, r;
			scanf("%d %d", &l, &r);
			l--;

			printf("%d\n", tree.query(l, r));
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3368 Frequent values 题解 《挑战程序设计竞赛》