说好的RMQ问题，结果又用线段树A了…
题意是：一个长度为n(1<=n<=100000)的非递减序列，共q(1<=1<=100000)次询问，求下标(l,h)范围内出现最频繁的元素的次数。 一开始照着RMQ问题想，还看了个ST算法（O(NlgN)预处理，O(1)在线查询），结果也没想明白怎么用。 又回头想了下，发现线段树是可以用的。由于序列非递减，连续的相同元素压缩成一个点作为线段树叶结点，记录元素在原数组中的下标范围；树分叉结点则保存子树下最频繁次数值，插入时则是按照压缩后的点编号进行处理，由此建树O(NlgN)，每次查询是O(lgN)。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<cstdio> #include<cstring> int n,q,a[100001],b[100000][2],bl,ml; struct node { int l,h,d; node *lc,*rc; }mem[200000],*root; void ins(int e,int L,int R,node *p) { if(L==R) { p->l=b[e][0]; p->h=b[e][1]; p->d=p->h-p->l+1; return; } int m=L+R>>1; if(!p->lc) { p->lc=&mem[ml++]; p->lc->l=p->lc->h=0; p->lc->lc=p->lc->rc=0; p->lc->d=0; p->rc=&mem[ml++]; p->rc->l=p->rc->h=0; p->rc->lc=p->rc->rc=0; p->rc->d=0; } if(e<=m) { ins(e,L,m,p->lc); if(p->lc->l) p->l=p->lc->l; if(p->lc->d>p->d) p->d=p->lc->d; } else { ins(e,m+1,R,p->rc); if(p->rc->h) p->h=p->rc->h; if(p->rc->d>p->d) p->d=p->rc->d; } } int que(int l,int h,node *p) { if(!p->lc) return h-l+1; if(l==p->l&&h==p->h) return p->d; int m=p->lc->h; if(h<=m) return que(l,h,p->lc); if(l>m) return que(l,h,p->rc); int a=que(l,m,p->lc),b=que(m+1,h,p->rc); return a>b?a:b; } bool input() { ml=bl=0; int i,j,k,L,R; if(scanf("%d%d",&n,&q)!=2) return 0; for(i=0;i<n;i++) scanf("%d",a+i); a[n++]=100001; for(i=1,k=0;i<n;i++) { if(a[i]!=a[i-1]) { b[bl][0]=k+1; b[bl][1]=i; k=i; bl++; } } root=&mem[ml++]; root->l=root->h=root->d=0; root->lc=root->rc=0; L=0; R=bl-1; for(i=0;i<bl;i++) ins(i,L,R,root); return 1; } void solve() { int l,h; while(q--) { scanf("%d%d",&l,&h); printf("%d\n",que(l,h,root)); } } int main() { while(input()) solve(); return 0; } |