区间离散化+线段树区间求最值poj 3368 Frequent values

Frequent values
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 15238 Accepted: 5553
Description
You are given a sequence of n integers a1 , a2 , … , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , … , aj.
Input
The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , … , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, …, n}) separated by spaces. You can assume that for each i ∈ {1, …, n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
query.
The last test case is followed by a line containing a single 0.
Output
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
Sample Input
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
Sample Output
1
4
3
Source
Ulm Local 2007
本题关键点是区间离散化。所谓离散就是把连续相等的点缩成一个点，同时用结构体记录该点所代表的的区间的端点和元素个数。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int a[maxn];
int hash[maxn];
int p;
struct node
{
int start;
int end;
}seg[maxn];//seg记录每个离散得到的点对应区间的端点。
struct line
{
int l;
int r;
int maxnum;
}tree[maxn<<2];
void build(int Node, int l, int r)
{
tree[Node].l = l; tree[Node].r = r;
if(l == r)//是叶子点
{
tree[Node].maxnum = seg[l].end - seg[l].start + 1;//这个节点里面重复的数有几个
return;
}
int mid = (tree[Node].l+tree[Node].r)>>1;
build(Node*2,l,mid);
build(Node*2+1,mid+1,r);
tree[Node].maxnum = max(tree[Node*2].maxnum, tree[Node*2+1].maxnum);
}
int query(int Node, int l, int r)
{
if(tree[Node].l == l && tree[Node].r == r) return tree[Node].maxnum;
int mid = (tree[Node].l+tree[Node].r)>>1;
if(r <= mid) return query(Node*2,l,r);
else if(l > mid) return query(Node*2+1,l,r);
else return max(query(Node*2,l,mid),query(Node*2+1,mid+1,r));
}
int main()
{
freopen("output.txt","w",stdout);
freopen("input.txt","r",stdin);
int n,m,pre;
while(EOF!=scanf("%d",&n)&&n)
{
scanf("%d",&m);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
pre = 100001;
p = 0;
//p为离散成的点。
for(int i = 1; i <= n; i++)
{
if(a[i] != pre)//新的节点
{
pre = a[i];
p++;
seg[p].start = i;
seg[p].end = i;
}
else seg[p].end = i;
hash[i] = p;
//标记原序列中每个下标对应离散后的点。
}
build(1,1,p);
//对离散后的点建树
while(m--)
{
int x,y,xx,yy;
scanf("%d %d",&x,&y);
xx = hash[x];//下标为x的点离散后对应的点
yy = hash[y];//下标为y的点离散后对应的点
if(xx == yy)//离散后的点是用一个点，说明[x,y]为同一个点集
{
printf("%dn",y-x+1);
continue;
}
else
//[x,y]不是同一个点集，就分为三部分，第二部分的点集最大值用线段树来求。
{
int ans1 = seg[xx].end-x+1;
int ans2 = 0;
int ans3 = y-seg[yy].start+1;
if(yy-xx > 1)
ans2 = query(1,xx+1,yy-1);
printf("%dn",max( max(ans1,ans2),ans3 ) );
continue;
}
}
}
return 0;
}

最后

以上就是粗犷眼神为你收集整理的区间离散化+线段树区间求最值poj 3368 Frequent values的全部内容，希望文章能够帮你解决区间离散化+线段树区间求最值poj 3368 Frequent values所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。