本文主要是介绍POJ 3368 Frequent values 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目大意
给定我们一个长度为n(n<=100000)的有序数组，进行q(q<=100000)次[L , R]的区间查询，对于每次查询返回 [L , R]区间内的出现次数最多的数字的出现次数。(1<=L<=R<=n)
二、解题思路
1、线段树
我们对于每个区间记录一个三元组
1、lVal代表这个区间内最左边的元素出现的次数
2、rVal代表这个区间内最右边的元素出现的次数
3、maxVal代表这个区间内出现最多的一个元素出现的次数
我们对让线段树的每个节点 i 维护对应区间 [L , R) 的这个三元组，计算方式如下：
一、R-L==1，则lVal[i]=1,rVal[i]=1,maxVal[i]=1,
二、如果R-L>1，我们先递归的计算左右两个孩子的三元组，计算好之后，将它们合并即可。设左孩子的区间为 [L1 , R1)右孩子的区间为 [L2 ,R2)，设左孩子为lch，右孩子为rch
1）首先初始化lVal[i]=lVal[lch],rVal[i]=rVal[rch],maxVal[i]=max(maxVal[lch],maxVal[rch])
2）如果num[R1-1] != num[L2]，则左右孩子无公共元素，直接返回初始化的值即可。
3）如果num[R1-1] == num[L2]，计算combine = rVal[lch] + lVal[rch] 代表合并部分
则 maxVal[i]=max(maxVal[i],combine)
若 num[L1]==num[R1-1]，则lVal[i]=combine
若 num[L2]==num[R2-1]，则rVal[i]=combine
用这种方式可以把线段树建立起来。
基于每次 [L , R)的查询，先递归的查询到被 [L , R) 包含的所有子节点区间，然后放在数组里，对数组按照 L 来排序，使用上面的方式，从左到右把所有的节点合并起来，输出最终的 maxVal即可。
三、代码
#include <iostream>
#include <algorithm>
using namespace std;
struct Node
{int lVal, rVal, maxVal;Node(int lVal, int rVal, int maxVal) : lVal(lVal), rVal(rVal), maxVal(maxVal) {}
};
struct Segment
{int l, r, idx;Segment(int l = 0, int r = 0, int idx = 0) : l(l), r(r), idx(idx) {}
};
int datL[262150], datR[262150], datMax[262150], n, num[100009], queLen;
Segment segQue[262150];
void input()
{for (int i = 0; i < n; i++){scanf("%d", &num[i]);}
}
Node merge(int L1, int R1, int lVal1, int rVal1, int maxVal1, int L2, int R2, int lVal2, int rVal2, int maxVal2)
{Node result = Node(lVal1, rVal2, max(maxVal1, maxVal2));if (num[R1 - 1] != num[L2]){return result;}int combine = rVal1 + lVal2;result.maxVal = max(result.maxVal, combine);if (num[L1] == num[R1 - 1]){result.lVal = combine;}if (num[L2] == num[R2 - 1]){result.rVal = combine;}return result;
}
void build(int i, int l, int r)
{if (r - l == 1){datL[i] = 1, datR[i] = 1, datMax[i] = 1;}else{int lch = i * 2 + 1;int rch = i * 2 + 2;int mid = (l + r) / 2;build(lch, l, mid);build(rch, mid, r);Node result = merge(l, mid, datL[lch], datR[lch], datMax[lch], mid, r, datL[rch], datR[rch], datMax[rch]);datL[i] = result.lVal;datR[i] = result.rVal;datMax[i] = result.maxVal;}
}
void query(int l_, int r_, int i, int l, int r)
{if (l_ >= r || r_ <= l){}else if (l >= l_ && r <= r_){segQue[queLen].l = l;segQue[queLen].r = r;segQue[queLen].idx = i;queLen++;}else{query(l_, r_, i * 2 + 1, l, (l + r) / 2);query(l_, r_, i * 2 + 2, (l + r) / 2, r);}
}
bool compareSeg(const Segment &a, const Segment &b)
{return a.l < b.l;
}
void solve()
{if (queLen == 1){printf("%d\n", datMax[segQue[0].idx]);return;}sort(segQue, segQue + queLen, compareSeg);int ansL = datL[segQue[0].idx];int ansR = datR[segQue[0].idx];int ansMax = datMax[segQue[0].idx];int l = segQue[0].l;int r = segQue[0].r;for (int i = 1; i < queLen; i++){Node result = merge(l, r, ansL, ansR, ansMax, segQue[i].l, segQue[i].r, datL[segQue[i].idx], datR[segQue[i].idx], datMax[segQue[i].idx]);ansL = result.lVal;ansR = result.rVal;ansMax = result.maxVal;r = segQue[i].r;}printf("%d\n", ansMax);
}
int main()
{int m, L, R;while (true){scanf("%d", &n);if (n == 0){break;}scanf("%d", &m);input();build(0, 0, n);while (m--){scanf("%d%d", &L, &R);queLen = 0;query(L - 1, R, 0, 0, n);solve();}}return 0;
}这篇关于POJ 3368 Frequent values 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
