本文主要是介绍POJ 3368 Frequent values RMQ / 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意；给定一个升序的数列（1-100000）， 比如 array[10] = -1 -1 1 1 1 1 3 10 10 10， 求其中某段区间上相同的数字最多有几个。[ 2, 3 ] = 1, [ 1, 10 ] = 4, [ 5, 10 ] = 3。（下标从1开始）。
题解：先将连续相等的几个数合并为一个部分（part), 或者说一个点。每点包括了起始位置，终止位置，相等元素个数三个信息。
查询的时候需要整点的查询，假设对区间 [ a, b ] 查询 ( [ a, b ] 里可能包含了多个点 ）， 若 a, b 均不是点的边界位置，那么就需要进行处理。
例如前面的数列求 [ 5, 10 ]， 我们已经知道 { -1, -1 } = 点 1， { 1,1,1,1 } = 点2， { 3 } = 点3， { 10,10,10 } = 点4。array[5]属于点2但不是点的边界，那么将 5 - 6 取出来单独讨论，然后再查询点3，点4。
#include <iostream>
using namespace std;
#define N 1000000
#define M 100005
int array[M], hash[M];/* hash表示每一个数字所属的part */
struct partition
{
int s, t, cnt;
} part[M];
struct item
{
int l, r, num;
} node[N];
int max ( int a, int b )
{
return a > b ? a : b;
}
void build_tree ( int l, int r, int u )
{
node[u].l = l;
node[u].r = r;
if ( l == r )
{
node[u].num = part[l].cnt;
return;
}
int mid = ( l + r ) / 2;
build_tree ( l, mid, u * 2 );
build_tree ( mid + 1, r, u * 2 + 1 );
node[u].num = max ( node[u*2].num, node[u*2+1].num );
}
int query ( int l, int r, int u )
{
if ( node[u].l == l && node[u].r == r )
return node[u].num;
int mid = ( node[u].l + node[u].r ) / 2;
if ( r <= mid )
return query ( l, r, u * 2 );
else if ( l > mid )
return query ( l, r, u * 2 + 1 );
else
return max ( query(l,mid,u*2), query(mid+1,r,u*2+1) );
}
int main()
{
int n, q;
int i, id, a, b, num1, num2, num3;
//freopen("a.txt","r",stdin);
while ( scanf("%d",&n) && n )
{
scanf("%d",&q);
for ( i = 1; i <= n; ++i )
scanf("%d",&array[i]);
memset(part,0,sizeof(part));
part[1].s = id = 1;
for ( i = 1; i <= n; ++i ) / *离散化，连续相同的数字归为一个part */
{
part[id].cnt++;
hash[i] = id;
if ( array[i] != array[i+1] || i == n )
{
part[id].t = i;
id++;
part[id].s = i+1;
}
}
build_tree ( 1, id - 1, 1 );
while ( q-- )
{
scanf("%d%d",&a,&b);
if ( hash[a] == hash[b] )
printf("%d\n",b-a+1);
else
{
num1 = part[ hash[a] ].t - a + 1;
num2 = b - part[ hash[b] ].s + 1;
num3 = 0;
if ( hash[b] - hash[a] > 1 )
num3 = query ( hash[a] + 1, hash[b] - 1, 1 );
printf("%d\n", max( max(num1,num2), num3 ) );
}
}
}
return 0;
}
RMQ解法：
#include <cmath>
#include <iostream>
using namespace std;
#define M 100010
int array[M], hash[M];
int dp[M][18];
struct partition
{
int s, t, cnt;
} part[M];
int max ( int a, int b )
{
return a > b ? a : b;
}
void Dpmax ( int n )
{
int i, j, temp;
for ( i = 1; i <= n; ++i )
dp[i][0] = part[i].cnt;
temp = log(n+1.0)/log(2.0);
for ( i = 1; i <= temp; ++i )
for ( j = 1; j + (1<<i) - 1 <= n; ++j )
dp[j][i] = max ( dp[j][i-1], dp[j+(1<<(i-1))][i-1] );
}
int getmax ( int a, int b )
{
int k = (int)( log(b-a+1.0) / log(2.0) );
return max ( dp[a][k], dp[b-(1<<k)+1][k] );
}
int main()
{
int n, q;
int i, id, a, b, num1, num2, num3;
//freopen("a.txt","r",stdin);
while ( scanf("%d",&n) && n )
{
scanf("%d",&q);
for ( i = 1; i <= n; ++i )
scanf("%d",&array[i]);
memset(part,0,sizeof(part));
part[1].s = id = 1;
for ( i = 1; i <= n; ++i )
{
part[id].cnt++;
hash[i] = id;
if ( array[i] != array[i+1] || i == n )
{
part[id].t = i;
id++;
part[id].s = i+1;
}
}
Dpmax(id-1);
while ( q-- )
{
scanf("%d%d",&a,&b);
if ( hash[a] == hash[b] )
printf("%d\n",b-a+1);
else
{
num1 = part[ hash[a] ].t - a + 1;
num2 = b - part[ hash[b] ].s + 1;
num3 = 0;
if ( hash[b] - hash[a] > 1 )
num3 = getmax ( hash[a] + 1, hash[b] - 1 );
printf("%d\n", max( max(num1,num2), num3 ) );
}
}
}
return 0;
}
这篇关于POJ 3368 Frequent values RMQ / 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
