计算给定范围内最小元素的数量-yiteyi-C++库

给定一个由N个数字和Q个查询组成的数组，每个查询都由L和R组成。我们需要编写一个程序，打印L-R范围内最小元素的出现次数。

null

例如：

Input: a[] = {1, 1, 2, 4, 3, 3}
        Q = 2 
        L = 1 R = 4 
        L = 3 R = 6
Output: 2 
        1 
Explanation: The smallest element in range 1-4 
is 1 which occurs 2 times. The smallest element
in the range 3-6 is 2 which occurs once.  

Input : a[] = {1, 2, 3, 3, 1}
        Q = 2 
        L = 1 R = 5 
        L = 3 R = 4
Output : 2
         2

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 正常方法 将从L-R迭代，找出范围内最小的元素。在L-R范围内再次迭代，并计算最小元素在L-R范围内出现的次数。在最坏的情况下，如果L=1且R=N，复杂性将为O（N）。

一 有效的方法 将使用分段树解决上述问题。在段树的每个节点上，存储最小元素和最小元素的计数。在叶节点，数组元素存储在最小值中，计数存储在1。对于除叶节点以外的所有其他节点，我们按照给定条件合并右节点和左节点：

1.min（左_子树）节点。min=min（左_子树），节点。计数=左_子树。计数 2.最小值（左_子树）>最小值（右_子树）： 节点。min=min（右_子树），节点。计数=右_子树。计数 3.最小值（左_子树）=最小值（右_子树）： 节点。min=min（左_子树）或min（右_子树），节点。计数=左_子树。计数+右_子树。计数

以下是上述方法的实施情况：

                     // CPP program to Count number of occurrence of                   
                     // smallest element in range L-R                   
                     #include <bits/stdc++.h>                   
                     using                               namespace                               std;                   
                             
                     #define N 100005                   
                             
                     // predefines the tree with nodes                   
                     // storing min and count                   
                     struct                               node {                   
                                         int                               min;                   
                                         int                               cnt;                   
                     } tree[5 * N];                   
                             
                     // function to construct the tree                   
                     void                               buildtree(                               int                               low,                               int                               high,                               int                               pos,                               int                               a[])                   
                     {                   
                                         // base condition                   
                                         if                               (low == high) {                   
                             
                                         // leaf node has a single element                   
                                         tree[pos].min = a[low];                   
                                         tree[pos].cnt = 1;                   
                                         return                               ;                   
                                         }                   
                             
                                         int                               mid = (low + high) >> 1;                   
                                         // left-subtree                   
                                         buildtree(low, mid, 2 * pos + 1, a);                   
                             
                                         // right-subtree                   
                                         buildtree(mid + 1, high, 2 * pos + 2, a);                   
                             
                                         // left subtree has the minimum element                   
                                         if                               (tree[2 * pos + 1].min < tree[2 * pos + 2].min) {                   
                                         tree[pos].min = tree[2 * pos + 1].min;                   
                                         tree[pos].cnt = tree[2 * pos + 1].cnt;                   
                                         }                   
                             
                                         // right subtree has the minimum element                   
                                         else                               if                               (tree[2 * pos + 1].min > tree[2 * pos + 2].min) {                   
                                         tree[pos].min = tree[2 * pos + 2].min;                   
                                         tree[pos].cnt = tree[2 * pos + 2].cnt;                   
                                         }                   
                             
                                         // both subtree has the same minimum element                   
                                         else                               {                   
                                         tree[pos].min = tree[2 * pos + 1].min;                   
                                         tree[pos].cnt = tree[2 * pos + 1].cnt + tree[2 * pos + 2].cnt;                   
                                         }                   
                     }                   
                             
                     // function that answers every query                   
                     node query(                               int                               s,                               int                               e,                               int                               low,                               int                               high,                               int                               pos)                   
                     {                   
                                         node dummy;                   
                                         // out of range                   
                                         if                               (e < low or s > high) {                   
                                         dummy.min = dummy.cnt = INT_MAX;                   
                                         return                               dummy;                   
                                         }                   
                             
                                         // in range                   
                                         if                               (s >= low and e <= high) {                   
                                         return                               tree[pos];                   
                                         }                   
                             
                                         int                               mid = (s + e) >> 1;                   
                             
                                         // left-subtree                   
                                         node ans1 = query(s, mid, low, high, 2 * pos + 1);                   
                             
                                         // right-subtree                   
                                         node ans2 = query(mid + 1, e, low, high, 2 * pos + 2);                   
                             
                                         node ans;                   
                                         ans.min = min(ans1.min, ans2.min);                   
                             
                                         // add count when min is same of both subtree                   
                                         if                               (ans1.min == ans2.min)                   
                                         ans.cnt = ans2.cnt + ans1.cnt;                   
                             
                                         // store the minimal's count                   
                                         else                               if                               (ans1.min < ans2.min)                   
                                         ans.cnt = ans1.cnt;                   
                             
                                         else                   
                                         ans.cnt = ans2.cnt;                   
                             
                                         return                               ans;                   
                     }                   
                             
                     // function to answer query in range l-r                   
                     int                               answerQuery(                               int                               a[],                               int                               n,                               int                               l,                               int                               r)                   
                     {                   
                                         // calls the function which returns a node                   
                                         // this function returns the count which                   
                                         // will be the answer                   
                                         return                               query(0, n - 1, l - 1, r - 1, 0).cnt;                   
                     }                   
                             
                     // Driver Code                   
                     int                               main()                   
                     {                   
                                         int                               a[] = { 1, 1, 2, 4, 3, 3 };                   
                             
                                         int                               n =                               sizeof                               (a) /                               sizeof                               (a[0]);                   
                                         buildtree(0, n - 1, 0, a);                   
                                         int                               l = 1, r = 4;                   
                             
                                         // answers 1-st query                   
                                         cout << answerQuery(a, n, l, r) << endl;                   
                             
                                         l = 2, r = 6;                   
                                         // answers 2nd query                   
                                         cout << answerQuery(a, n, l, r) << endl;                   
                                         return                               0;                   
                     }                   

输出：

2
1

时间复杂性： O（n） 用于建造树木。 O（对数n） 对于每个查询。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章