POJ3368 Frequent values 线段树 - c++编程基础

TOP

POJ3368 Frequent values 线段树

2015-07-20 18:01:58 来源: 作者: 【大中小】浏览:2次

N个数为非递减顺序，给定范围l,r，求[l,r]区间内数字出现频率最高的次数。

可以用线段树来做。先说查询，我们设节点P对应的区间为[a, b]，左孩子节点为p1,右孩子节点为p2,那么 P也许不等于 max(p1 , p2)，原因是如果p1中频率较低的某个数与p2中出现频率较低的某个数是同一个数，并且两者出现次数加起来大于max(p1, p2)，但是，题目说N个数为非递减顺序排列，所以这个可能只会发生在p1的右端和p2的左端对应的数是同一个数，因此，我们还要处理这第三个可能。

查询的问题解决，现在剩下的就是建立这棵线段树，这比较容易，只是在从叶子节点向根节点更新的时候有点特殊，我们只要知道当前更新的元素以及它在当前节点对应的区间内出现的次数即可，然后以最大值更新该节点，这一步，需要进行一个预处理：依次扫描N个数，对每个数出现的开始位置和结束位置进行记录即可。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               using namespace std; inline void QuadMemSet(void* dst, int iSize, int value) { iSize = iSize / 4; int* newDst = (int*) dst; #ifdef WIN32 __asm { mov edi, dst mov ecx, iSize mov eax, value rep stosd } #else for (int i = 0; i < iSize;i++) { newDst[i] = value; } #endif } #define MAXN 100001 #define MAXVALUE 200001 int values[MAXN]; int ranges[MAXVALUE][2]; int St[265000]; template
              
                void Updateva lue(TYPE st[],int i, TYPE value, int N) { int a = i; int b = i; i += N - 1; st[i] = 1; int left = ranges[value][0]; int right = ranges[value][1]; int tmp; while (i > 0) { tmp = (i - 1) / 2; if (tmp * 2 + 1 == i) //左孩子 { b += (b - a) + 1; } else { a -= (b - a) + 1; } int count = 0; int tmpa = max(a, left); int tmpb = min(b, right); count = tmpb - tmpa + 1 > 0 ? tmpb - tmpa + 1 : 0; i = tmp; st[i] = max(st[i], count); } } template
               
                 TYPE QueryST(TYPE st[], int a, int b, int l, int r, int k) { if (l > b || a > r) { return 0; } if (l >= a && b >= r) { return st[k]; } else { TYPE value1 = QueryST(st, a, b, l, (r + l) / 2, k * 2 + 1); TYPE value2 = QueryST(st, a, b, (r + l) / 2 + 1, r, k * 2 + 2); TYPE value3 = 0; if (values[(r + l) / 2] == values[(r + l) / 2 + 1]) { int start = ranges[values[(r + l) / 2]][0]; int end = ranges[values[(r + l) / 2]][1]; start = max(a, start); end = min(b, end); value3 = end - start + 1; } return max(max(value1, value2), value3); } } int main() { #ifdef _DEBUG freopen("e:\\in.txt", "r", stdin); #endif int n, q; while (scanf("%d", &n) != EOF) { if (n == 0) { break; } scanf("%d",&q); QuadMemSet(ranges, sizeof(ranges), -1); QuadMemSet(St, sizeof(St), 0); int lastvalue = -1; for (int i = 0; i < n; i++) { scanf("%d", &values[i]); values[i] += 100000; if (lastvalue != values[i]) { if (lastvalue != -1) { ranges[lastvalue][1] = i - 1; } lastvalue = values[i]; ranges[lastvalue][0] = i; } } int maxn = 1; while (maxn < n) { maxn *= 2; } ranges[lastvalue][1] = n - 1; for (int i = 0; i < n; i++) { Updateva lue
                
                 (St, i, values[i], maxn); } for (int i = 0; i < q; i++) { int a, b; scanf("%d %d", &a, &b); a--; b--; printf("%d\n", QueryST
                 
                  (St, a, b, 0, maxn - 1, 0)); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 1253 胜利大逃亡(BFS)	下一篇：UVa 1583 Digit Generator(数)

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: