首页 > 代码库 > Frequent values

Frequent values

2024-07-14 05:12:19   225人阅读

poj3368:http://poj.org/problem?id=3368

题意：给你一个非下降的序列，然后查询[l,r]内出现最多数字的次数。

题解：首先，因为序列是非下降的，所以相同的数字出现在在一起。所以，可以定义一个数组a[i]=k,表示第i个数出现的次数，另外还要记录几个东西,ll[i],rr[i],分别表示第i个数首次出现的位置和最后出现的位置。sum[i]到第i数出现结束之后一共有多少个数。准备好了这些东西之后。既可以开始了。第一步以数的个数(相同的算一个)建立线段树，叶子节点的值就是这个数出现的次数，然后维护区间最大值。2对于一个查询来说，是查询第几个数到第几个数之间出现的最大值的话，问题就爱很简单了。所以，我们要把查询转化成这样的就行了。query(l,r),我们可以通过lower_bound(sum+1,sum+temp+1)-sum,来找到l，r出现在第几个数中，然后我们查询l后面和r前面的数就可以啦 啊。对于l前面的部分，肯定是连续的，所以可以直接ll[l+1]-u得到左边的，v-rr[ed-1]得到右边的，然后3部分去最大值就可以啦。当然还有几个情况，就是1:l,r出现在同一个数中,那么可以直接u-v+1,如果是相隔一个数的话,max(sum[l]-u+1,v-sum[ed-1])即可。

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int N=1e5+5; 7 int ll[N],rr[N],sum[N]; 8 int maxn[N*4]; 9 int a[N];10 int n,q,temp;11 void input(){12     int t,tp;13      scanf("%d",&t);14      a[temp]=1;15      ll[temp]=1;16   for(int i=2;i<=n;i++){17     scanf("%d",&tp);18     if(tp==t)a[temp]++;19     else{20         a[++temp]=1;21         ll[temp]=i;22         rr[temp-1]=i-1;23         t=tp;24     }25   }26   rr[temp]=n;27 }28 void build(int l,int r,int rt){29     if(l==r){30         maxn[rt]=a[l];31         return;32     }33    int mid=(l+r)/2;34    build(l,mid,rt<<1);35    build(mid+1,r,rt<<1|1);36    maxn[rt]=max(maxn[rt<<1],maxn[rt<<1|1]);37 }38 int query(int l,int r,int rt,int from,int to){39    if(l==from&&r==to){40     return maxn[rt];41    }42    int mid=(l+r)/2;43    if(mid>=to)return query(l,mid,rt<<1,from,to);44    else if(mid<from)return query(mid+1,r,rt<<1|1,from,to);45    else{46     return max(query(l,mid,rt<<1,from,mid),query(mid+1,r,rt<<1|1,mid+1,to));47    }48 }49 int u,v;50 int main(){51     while(~scanf("%d",&n)){52         if(n==0)break;53          scanf("%d",&q);54          temp=1;55          input();56         memset(maxn,0,sizeof(maxn));57         build(1,temp,1);58         sum[0]=0;59         for(int i=1;i<=temp;i++){60             sum[i]=sum[i-1]+a[i];61         }62         for(int i=1;i<=q;i++){63             scanf("%d%d",&u,&v);64             int st=lower_bound(sum+1,sum+temp+1,u)-sum;65             int ed=lower_bound(sum+1,sum+temp+1,v)-sum;66             st++;ed--;67             if(ed>=st){68                 int ans1=query(1,temp,1,st,ed);69                 int ans2=ll[st]-u;70                 int ans3=v-rr[ed];71                 printf("%d\n",max(ans1,max(ans2,ans3)));72             }73             else if(st==ed+2){74                 printf("%d\n",v-u+1);75             }76             else{77                 st--,ed++;78                 printf("%d\n",max(sum[st]-u+1,v-sum[ed-1]));79             }80         }81 82     }83 }
View Code

 

Frequent values


联系
我们