为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 319333
  • 排名 - 75

最新评论

阅读排行榜

评论排行榜

(所有数组下标从1计)计算出原数列中每个数出现次数的数列,并用RMQ预处理
如 a[]={ -1 -1 1 1 1 1 3 10 10 10} 得到 sum[]={ 2 4 1 3 }
用index数组记录a[i]在sum中的下标。index[]={1,1,2,2,2,2,3,4,4,4};
first数组记录每组数据中第一个出现的在a中的下标
first[]={1,3,7,8};

对于每个询问的区间[from,to],首先计算出from to在sum中对应的位置f,t
1、如果f==t,则[from,to]区间中数据是一样的
2、如果f+1=t,则[from,to]区间只有两种数据。
3、如果f+1<t,则[from,to]区间有大于两种数据
#include<iostream>
#include
<vector>
#include
<string>
#include
<cmath>
using namespace std;
const int maxsize=100001;
int sum[maxsize],st[maxsize][20],a[maxsize],index[maxsize],first[maxsize];
void rmq_init(int len)
{
    
for(int i=1;i<=len;i++)
        st[i][
0]=sum[i];
    
int m=floor(log((double)len)/log(2.0));
    
for(int i=1;i<=m;i++)
        
for(int j=len;j>0;j--)
        {
            st[j][i]
=st[j][i-1];
            
if(i+(1<<(i-1))<=len) st[j][i]=max(st[j][i],st[j+(1<<(i-1))][i-1]);
        }
}
int query(int l,int r)
{
    
int m=floor(log((double)(r-l+1))/log(2.0));
    
return max(st[l][m],st[r-(1<<m)+1][m]);
}
int solve(const int & from,const int & to)
{
    
int f=index[from],t=index[to];
    
if(f==t) return to-from+1;
    
else if(f+1==t) return max(first[t]-from,to-first[t]+1);
    
else
    {
        
int res;
        res
=max(first[f+1]-from,to-first[t]+1);
        res
=max(res,query(f+1,t-1));
        
return res;
    }
}

int main()
{
    
int from,to;
    
int n,q;
    
int len;
    
while(scanf("%d",&n)!=EOF)
    {
        
if(n==0break;
        scanf(
"%d",&q);
        a[
0]=INT_MAX;
        
        len
=0;
        memset(sum,
0,sizeof(sum));
        
for(int i=1;i<=n;i++)
        {
            scanf(
"%d",&a[i]);
            
if(a[i]==a[i-1])
            {
                index[i]
=len;
                sum[len]
++;
            }
            
else
            {
                index[i]
=++len;
                sum[len]
=1;
                first[len]
=i;
            }
        }
        rmq_init(len);
        
while(q--)
        {
            scanf(
"%d%d",&from,&to);
            printf(
"%d\n",solve(from,to));
        }
    }
}


posted on 2009-10-25 21:58 baby-fly 阅读(212) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

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