原题链接 题意：给定一个非严格单调增数列，请快速求解一个区间内出现最频繁的数的频次。 思路：其实就是把相同的值合并成三个信息，即相同的值的数量，左端点，右端点。这样我们就可以把问题分为三种情况 1、属于同一个区间：答案就是它们之间的大小 2、属于相邻区间：找到它们的分隔点，取两个区间大小的较大者 3、属于两个不相邻的区间：取出头尾两个区间，计算它们的大小。对于中间的一个或多个区间，它们都是完整的，因此可以使用更新最大值的线段树，计算出它们中的最大值。最后的答案即为该最大值与头尾两个区间的大小，一共三个数的最大值。
#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int maxn = 100000 + 10;typedef struct mtree{ //区间用[ql,qr],[l,r]表示 int maxt[maxn * 4]; //向上更新区间最值 //比如区间[1,8]我们要在5位置将原来的数改为2就需要传入(5,2,1,1,8) void update(int loc,int x,int k,int l,int r){ if(l==r) maxt[k]=x; else{ int mid = l + (r-l)/2; if(loc<=mid) update(loc,x,k*2,l,mid); else update(loc,x,k*2+1,mid+1,r); maxt[k] = max(maxt[k*2],maxt[k*2+1]); } } //查询区间最大值 //比如区间[1,8]我们要查询[3,6]区间内的最大值就要传入(3,6,1,1,8) int query(int ql,int qr,int k,int l,int r){ if(ql<=l && r<=qr) return maxt[k]; int mid = l + (r-l)/2,ans=-1; if(ql<=mid) ans = max(ans,query(ql,qr,k*2,l,mid)); if(mid+1<=qr) ans = max(ans,query(ql,qr,k*2+1,mid+1,r)); return ans; }}mtree;//单点更新值求区间最值的线段树mtree mt;int v[maxn],ll[maxn],rr[maxn];//分别记录区间的长度，左端点和右端点int main(){ int n,q; while(scanf("%d",&n)==1 && n){ cin >> q; memset(v,0,sizeof(v)); memset(ll,0,sizeof(ll)); memset(rr,0,sizeof(rr)); int cnt=1,t;//cnt是离散化后的数组长度 int beginloc=1,beginnum; cin >> beginnum; for(int i=2;i<=n;i++){ scanf("%d",&t); if(t!=beginnum){ v[cnt]=i - beginloc; ll[cnt]=beginloc; rr[cnt]=i-1; cnt++; beginloc = i; beginnum = t; } } v[cnt]=n+1-beginloc; ll[cnt]=beginloc; rr[cnt]=n; //for(int i=1;i<=cnt;i++) PRintf("i:%d v:%d l:%d r:%d/n",i,v[i],ll[i],rr[i]); memset(mt.maxt,0,sizeof(mt.maxt)); for(int i=1;i<=cnt;i++) mt.update(i,v[i],1,1,cnt); //for(int i=1;i<8;i++) cout << mt.maxt[i] << " "; //得到l和r究竟是属于哪一个区间 while(q--){ int l,r,begin,end; scanf("%d%d",&l,&r); int tl=0,tr=cnt+1; while(tr-tl>1){ int mid = (tl + tr)/2; if(ll[mid]<=l) tl=mid; else tr=mid; } begin=tl; tl=0;tr=cnt+1; while(tr-tl>1){ int mid = (tl+tr)/2; if(rr[mid]<r) tl=mid; else tr=mid; } end=tr; //cout << begin << " " << end << endl; if(begin==end){//在同一个区间时 printf("%d/n",r-l+1); } else if(end-begin==1){//相邻的区间 printf("%d/n",max(rr[begin]-l+1,r-ll[end]+1)); } else{//中间至少隔了一个区间 int res=max(rr[begin]-l+1,r-ll[end]+1); res = max(res,mt.query(begin+1,end-1,1,1,cnt)); printf("%d/n",res); } } } return 0;}新闻热点
疑难解答
