poj 1806 Frequent values（RMQ 统计次数）详细讲解-白红宇

poj 1806 Frequent values（RMQ 统计次数）详细讲解

阅读量：6230 次

发布时间：2019-06-21

本文共 3568 字，大约阅读时间需要 11 分钟。

题目链接：

题目大意：给你一个非降序排列的整数数组，你的任务是对于一系列的询问，（i，j），回答序列中出现次数最多的数的个数；

如下图所示：

AC代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 const int N = 1e5+10;10 int a[N],b[N];11 int dp[N][20];12 int n,m;13 //构造和寻找的代码，来自大白书14 void buildrmq( )15 {16 for(int i=0;i
            
             >1);37 if(a[mid]>=tmp) r=mid;38 else l=mid+1;39 }40 return r;41 }42 int main()43 {44 int T;45 while(scanf("%d",&n) && n)46 {47 memset(b,0,sizeof(b));48 memset(dp,0,sizeof(dp));49 scanf("%d",&m);50 for(int i =0; i
             
              =0; i--)//倒序统计单个数在当前段出现的次数54 {55 if(a[i] == a[i+1])56 {57 b[i] = b[i+1]+1;58 }59 else b[i] =1;60 }61 buildrmq( );//构造RMQ函数62 int L,R,ans;63 for(int i=1; i<=m; i++)64 {65 scanf("%d %d",&L,&R);66 L = L-1;R = R-1;//题目中是从1开始计数的；67 int temp = bi_search(L,R);//寻找数组中最左端等于a[R]的数68 ans = b[temp] - b[R]+1; //统计和最左边相同的数出现的次数69 if(L == temp) printf("%d\n",ans);//如果这一区间中的数字相同的话，直接左边减去右边70 else printf("%d\n",max(ans,search(L,temp-1)));//否则，寻找（L,temp）中的最大数，进行比较71 }72 }73 return 0;74 }

AC代码2：线段树

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6 const int N = 1e5+10;  7 int a[N];  8 int ans ;  9 struct node 10 { 11     int L,R,count,fre; 12     int lcount,lfre; 13     int rcount,rfre; 14 }tree[3*N]; 15 /* 16 l,r存该节点的边界。 17 count存该节点中出现最多的数字的个数，fre存该节点中出现最多的数字。 18 lcount 存该节点左端连续出现的数字的个数， lfre存该节点左端连续出现的数字。 19 rcount 存该节点右端连续出现的数字的个数， rfre存该节点右端连续出现的数字。 20 */ 21 void build(int l,int r,int v) 22 { 23     tree[v].L = l; 24     tree[v].R = r; 25     if(l == r) 26     { 27         tree[v].fre = tree[v]. rfre = tree[v].lfre = a[r]; 28         tree[v].count = tree[v].lcount = tree[v].rcount = 1; 29         return ; 30     } 31     int mid = (l+r)/2; 32     build(l,mid,v*2); 33     build(mid+1,r,v*2+1); 34     int tmpc,tmpf; 35     if(tree[v*2].count>tree[v*2+1].count) 36     { 37         tree[v].count = tree[v*2].count; 38         tree[v].fre = tree[v*2].fre; 39     } 40     else 41     { 42         tree[v].count = tree[v*2+1].count; 43         tree[v].fre = tree[v*2+1].fre; 44     } 45     tree[v].lcount = tree[v*2].lcount; 46     tree[v].rcount = tree[v*2+1].rcount; 47     if(tree[v*2].rfre == tree[v*2+1].lfre) 48     { 49         tmpc = tree[v*2].rcount +tree[v*2+1].lcount; 50         tmpf = tree[v*2].rfre; 51         if(tree[v].count
         
          ans) 70             ans = tree[v].count; 71         return ; 72     } 73     mid = (tree[v].L+tree[v].R)/2; 74     if(y<=mid) update(x,y,v*2); 75     else if(x>mid) update(x,y,v*2+1); 76     else { 77         update(x,mid,v*2); 78         update(mid+1,y,v*2+1); 79         if(tree[v*2].rfre == tree[v*2+1].lfre) 80         { 81             if(a[x] != tree[v*2].rfre) s1 = tree[v*2].rcount; 82                 else s1 = mid-x+1; 83                 if(a[y]!=tree[v*2+1].lfre) s2 = tree[v*2+1].lcount; 84                      else s2 = y - mid; 85                 if(s1+s2>ans) ans = s1+s2; 86         } 87     } 88 } 89 int main() 90 { 91    int m,n,x,y; 92    while(scanf("%d",&m) && m) 93    { 94        scanf("%d\n",&n); 95         for(int i=1;i<=m;i++) 96           scanf("%d",&a[i]); 97           build(1,m,1); 98           for(int i=1;i<=n; i++) 99           {   ans = 0;100               scanf("%d %d",&x,&y);101               if(x==y) {printf("1\n");continue;}102               update(x,y,1);103               printf("%d\n",ans);104           }105    }106    return 0;107 }