本文主要是介绍poj 3368 Frequent values(线段树+离散化) -，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第一步就死离散化，现在才开始接触。。乃琦神牛要我一定要做几题，我也就试试罗。
对于相同的数，记录起点和终点，记录出现的次数，缩成一个点。就可以建线段树。
还要注意如果给出的点不是起点，那么这个点连续的一段相同的要先算出来。。
而且这道题没有动态变化。个人觉得RMQ一样可以过。。。。下次有空试一下。
不过正在学线段树，就做一下线段树的吧。
#include<iostream>
#include<cstdio>#include<cstring>
using namespace std;
const int MAXN = 110000;
struct node{
int left;
int right;
int num;
int count;
}p[MAXN];
int ha[MAXN];
int data[MAXN];
struct seg{
int left,right,count;
}tree[MAXN*4];
void Init(int pos,int left,int right){
tree[pos].left = left;
tree[pos].right = right;
if(left==right){
tree[pos].count = p[left].count;
return ;
}
int mid = (left+right)/2;
Init(pos*2,left,mid);
Init(pos*2+1,mid+1,right);
if(tree[pos*2].count>tree[pos*2+1].count){
tree[pos].count = tree[pos*2].count;
}else tree[pos].count = tree[pos*2+1].count;
}
int query(int pos,int left,int right){
if(tree[pos].left==left && tree[pos].right==right)return tree[pos].count;
int mid = (tree[pos].left+tree[pos].right)/2;
int x,y;
if(mid>=right)return query(pos*2,left,right);
else if(left>=mid+1)return query(pos*2+1,left,right);
else {
x = query(2*pos,left,mid);
y = query(2*pos+1,mid+1,right);
return x>y?x:y;
}
}
int solve(int a,int b){
if(ha[a]==ha[b])
return b-a+1;
if(ha[a]+1==ha[b]){
int x = p[ha[a]].right-a+1;
int y = b-p[ha[b]].left+1;
return x>y?x:y;
}
int x = p[ha[a]].right-a+1;
int y = b-p[ha[b]].left+1;
x = x>y?x:y;
y = query(1,ha[a]+1,ha[b]-1);
return x>y?x:y;
}
int main(){
int n,q;
while(scanf("%d",&n),n!=0){
scanf("%d",&q);
for(int i = 1;i<=n;i++){
scanf("%d",&data[i]);
}
int t = 1;
ha[1] = 1;
p[1].left = p[1].right = 1;
p[1].num = data[1];
p[1].count = 1;
for(int i = 2;i<=n;i++){
if(data[i]!=data[i-1]){
t++;
p[t].left = p[t].right = i;
p[t].num = data[i];
p[t].count = 1;
}else {
p[t].right = i;
p[t].count++;
}
ha[i] = t;
}
Init(1,1,t);
while(q--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",solve(l,r));
}
}
return 0;
}
这篇关于poj 3368 Frequent values(线段树+离散化) -的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
