随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 3368 Frequent values

 题目链接:http://poj.org/problem?id=3368

/*
题意:
    给定一个长度为N(N <= 100000)的单调不降数列Si,然后是Q(Q <= 100000)条询问
,问给定区间出现最多的数的次数。

解法:
离散化+线段树 或者 离散化+RMQ

思路:
    由于m很大,询问的复杂度必须要log(n),这样一来就先确定下来是线段树了,这个
题目有个限制条件,所有数都是单调不增的排列的,换言之,就是说如果两个数相同的话
,他们之间的所有数必定也和它们相同。
    于是就有了mlog(n)的算法:
对于所有的数均设定一个组号,也可以叫离散化吧,相同的数有相同的组号,然后将各个
数的频率统计后记录在一个数组中,表示该类数的大小,对于输入的询问[x, y],直接查
询它们在哪个组,分三种情况讨论:
1. 如果x和y在一个组,那么最长长度就是y - x + 1
2. 如果组号相差1,那么找出两者的分界点z(假设z点和x点组号相同),那么答案就是Max
{z - x + 1, y - z}
3. 如果相差大于1,那么先将两头截掉,统计大的记录,再和中间那段的最大值比较大小,
中间那段的最大值可以用线段树或者RMQ区间查询最值。
*/


#include 
<iostream>

using namespace std;

#define maxn 100010
typedef 
int Tree_Index;

struct Tree {
    
int Max;
}
T[maxn*4];

struct Pair {
    
int val;
    
int cnt;
}
Pr[maxn];

int PrSize = 0;
int x[maxn], sum[maxn], pos[maxn];
int n, m;

void Build(int p, int l, int r) {
    
if(l == r) {
        T[p].Max 
= Pr[l].cnt;
        
return ;
    }

    
int mid = (l + r) >> 1;
    Build(p
<<1, l, mid);
    Build(p
<<1|1, mid+1, r);
    T[p].Max 
= T[p<<1].Max > T[p<<1|1].Max ? T[p<<1].Max : T[p<<1|1].Max;
}


Tree_Index Query(
int p, int l, int r, int a, int b) {
    
if(l == a && b == r) {
        
return p;
    }

    
int mid = (l + r) >> 1;
    
if(b <= mid) {
        
return Query(p<<1, l, mid, a, b);
    }
else if(mid + 1 <= a){
        
return Query(p<<1|1, mid+1, r, a, b);
    }
else {
        Tree_Index p1 
= Query(p<<1, l, mid, a, mid);
        Tree_Index p2 
= Query(p<<1|1, mid+1, r, mid+1, b);
        
return T[p1].Max > T[p2].Max ? p1 : p2;
    }

}


void ProcessPr() {
    
int i, j;
    PrSize 
= 0;
    
for(i = 1; i <= n; i++{
        
if(x[i] == x[i-1]) {
            Pr[PrSize].cnt
++;
        }
else {
            PrSize
++;
            Pr[PrSize].val 
= x[i];
            Pr[PrSize].cnt 
= 1;
        }

    }

    
for(i = 1; i <= n; i++{
        sum[i] 
= Pr[i].cnt + sum[i-1];
        
for(j = sum[i-1]+1; j <= sum[i]; j++)
            pos[j] 
= i;
    }

}


int findPos(int v) {
    
int l = 0;
    
int r = PrSize;
    
int ans = -1;
    
while(l <= r) {
        
int m = (l + r) >> 1;
        
if(v > sum[m]) {
            l 
= m + 1;
            
if(m > ans)
                ans 
= m;
        }
else
            r 
= m - 1;
    }

    
return ans + 1;
}


int main() {
    
int i;    
    x[
0= INT_MIN;
    
    
while(scanf("%d"&n) != EOF && n) {
        scanf(
"%d"&m);
        
for(i = 1; i <= n; i++{
            scanf(
"%d"&x[i]);
        }

        ProcessPr();
        Build(
11, PrSize);
        
while(m--{
            
int x, y, l, r;
            scanf(
"%d %d"&x, &y);
            l 
= pos[x]; // findPos(x);
            r = pos[y]; // findPos(y);
            if(l == r) {
                printf(
"%d\n", y - x + 1);
            }
else {
                
int ans = (sum[l] - x + 1> (y - sum[r-1]) ? (sum[l] - x +  1) : (y - sum[r-1]);
                
if(l + 1 < r) {
                    Tree_Index p 
= Query(11, PrSize, l+1, r-1);
                    
if(T[p].Max > ans)
                        ans 
= T[p].Max;
                }

                printf(
"%d\n", ans);
            }

        }

    }

    
return 0;
}

posted on 2011-03-29 18:30 英雄哪里出来 阅读(1189) 评论(0)  编辑 收藏 引用 所属分类: 线段树


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理