最频繁的数:给定一个非严格单调增数列,请快速求解一个区间内出现最频繁的数的频次。
3.3活用各种数据结构
线段树和平方分割
采用线段树充分利用中间计算结果,定义区间的最大长度为最长连续子区间的长度,定义左孩子区间长度为包含左端点在内的最长连续区间的长度,同理定义右孩子区间。线段树的每个阶段维护这三个信息即可,这样预处理之后合并区间将会变得非常快捷。
在预处理的时候,将数组不断地拆成两半,直至不能再分,也就是只有一个元素,上述三个值都为1(因为三个区间元素都只有一个)。然后往上合并,合并的时候分四种情况讨论:
-
默认
继承左孩子的左端、右孩子的右端 -
左孩子右端和右孩子左端相等
合并左右孩子更新最大长度。 -
左孩子左端和右孩子左端相等
合并左孩子和右孩子的左端 -
左孩子右端和右孩子右端相等
合并右孩子和左孩子的右端
举个例子,对于数列
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//////////////////////////////////
13184236 | hankcs | 3368 | Accepted | 4476K | 1079MS | C++ | 3695B | 2014-07-27 23:39:34 |
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 3368 Frequent values 题解 《挑战程序设计竞赛》