• POJ 2104 K-th Number 平方分割（分桶法）

    一、题目大意

    长度为n（n<=100000）的数组，进行m次查询（m<=5000），每次查询时，输入为 i j k，返回为数组 [i,j] 的分片里第k大数字（1<=i<=j<=n,k<=j-i+1)

    二、解题思路

    1、平方分割

    如果采用朴素的方法去计算，针对每次的i 和 j，从 i 到 j 循环把数组的元素放在一个tmp数组里，然后给tmp数组排序，输出tmp[k]的话，在最差情况下，时间复杂性为 O ( m * n * log(n) )，也就是10000000000左右，肯定是行不通的。

    于是考虑使用平方分割，按 floor(sqrt(n))为一块，分成根号n块，然后把每一块的数字进行排序，根据查询的 i 和 j，找出 i 和 j 范围内所有的块，然后把 块未覆盖到的左边的和右边范围内放在一个 other数组里，把other数组排序。

    这时相当于得到多个有序的块，然后我们需要找到这些块合并在一起后的第k大的，朴素的合并多的话，还是会很慢（合并两个有序数组为一个的操作次数，为其中大的数组的长度），所以考虑二分，可以对数组内所有的元素进行排序。

    设一开始输入的数组为dat，那么我们把dat排序后作为sortedDat，然后 L = -1,R=n（二分时候的 l 和 r 是达不到的，都取开区间）当L+1 < R时循环，mid = (L+R)/2，然后我们再循环对这些块来使用二分，找到所有块中小于sortedDat[mid]的数量和cnt，如果cnt

    考虑下复杂性 O(log(n)*sqrt(n)*log(n)*m)，好像是可以的，但实际并不如此。

    此时我们需要对算法进行优化，如何优化呢？考虑下比较糟糕的情况，假如n=100000，则我们会分316块，假设涉及的区间包含200块，那么每次二分，循环200次，然后200次循环里还有2分，起始也可能会比较慢，所以我们考虑如何把200个小块合并，假设2个相邻的合并成一个，改成100的话，速度可以快一倍。

    于是我们可以在起初分桶的时候，按2 * floor(sqrt(n)) 来分一些大块，然后对这些块也都进行排序，一个大块相当于2个小块。

    于是我们执行每次查询时需要进行的操作为：

    1、根据区间 i j 找到包含的桶

    2、根据找到的桶，来处理不在桶内，而且被 i 和 j 包含的区间，对此区域排序并记录长度。

    3、循环包含的桶，如果 两个相邻的小桶可以被一个大桶替换的话，则用这个大桶替换掉小桶，依据此思路，把所有的小桶都用大桶替换。

    4、 对sortedDat里面的数进行二分，L = -1,R=n，针对每次的mid，循环里利用二分找到所有涉及的小桶、大桶和其他区域里小于 sortedDat[mid]的数量总和cnt，如果cnt小于k，则L=mid，否则R=mid，循环结束时，输出sortedDat[L]即可

    （如果不涉及到任何桶，那直接输出other[k-1]即可，不用走二分这个思路）

    （然后利用大桶替换小桶时，可以循环涉及的小桶，如果它不是涉及到的最后一个，且它的下标 i是偶数，则它和它的下一个被一个大桶替换，否则的话这个桶保留，简单的思路就是定义一个变量i=0，设当前区间涉及的小桶数量为bucketLen，保存当前区间相关的桶的数组为bucket，然后 i < bucketLen时候循环，如果i+1小于bucketLen且bucket[i]%2==0，那么就把 i /2记录为当前涉及的大桶 bucketBig[bigLen++]=i/2，然后i +=2，否则就把 bucket[i]加到队列里，最后把不在队列里的小桶都去掉，把队列里的小桶记录下来为替换后涉及到的小桶，然后大桶就是bucketBig里的大桶）

    （我针对桶的下标从0开始计算，然后下标 i 的小桶的区间为 [ i * 根号n , (i + 1) * 根号n)，下标 i 的大桶的区间为[ 2 *  i * 根号n , (i + 1) * 2 * 根号n)，这样的话大桶 i /2就代表小桶 i 和 i + 1，需要i%2==0 ）

    优化之后，就侥幸过了

    （做完了之后看下书，发现书里使用平方分割每个桶是1000大小，不过我觉得比赛时靠自己思考很难想到扩到1000吧！我这种思路两个桶变成一个思路倒是容易想到而且可行！）

    2、线段树

    我做完了这个题目之后，读了下挑战程序设计，发现书中还有一种解决方法是线段树，维护数组的线段树也叫区域树，让叶子节点维护长度为1的有序数组，它的父节点维护长度为2有序数组，然后根节点维护 [ 0 , max(n_,2^i) ) 有序数组，

    这个树也挺好创建的，就和线段树的初始化一样，先解决叶子节点，然后把两个叶子节点合并时候，就把小的数字放前面，大的数字放后面即可。

    然后两个有序数组合并时，就可以定义两个指针 L和R，然后记录每个的长度lenL,lenR，设父数组的长度为lenPa，设父数组时arrPa，左孩子数组是arrL，右孩子数组是arrR

    while L < lenL || R < lenR

         if R >= lenR

            arrPa[lenPa++] = arrL[L++]

        else if L <  lenL && arrL[L]

            arrPa[lenPa++] = arrL[L++]

        else

            arrPa[lenPa++]=arrR[R++]

    简单写了几行不标准的伪代码，两个有序数组合并成一个有序数组，就是这样的，这个效率上和STL和merge是差不多的，所以线段树初始化就可以用这个方法把 i * 2 +1和i*2+2的数组都合并到i的数组。

    然后线段树维护这么大的一个数组，定义变量时候肯定没办法直接定义二维数组，我的思路就是定义一个 int *dat[262150]，然后在初始化的时候：

    1、如果是叶子节点就 dat[i]=new int[1]，然后记录len[i]=1

    2、如果是父节点，那就 dat[i]=new int[len[i*2 + 1] + len[i*2 + 2]]

    初始化结束之后，我们针对每次查询，先查下线段树，找到的所有线段树节点，然后这些节点自己维护的数组肯定是有序的，所以思路也是和平方分割差不多。

    把数组排序，二分排好序的数组里所有的元素，对 在区间内的 线段树节点数组 进行循环二分，记录小于 数组第mid项（拍好序数组里mid下标的） 的数量cnt，如果cnt

    我一开始用vector，挂了很多次，因为当时没看书，不知道可以使用resize+merge，所有的元素都是使用循环push_back，结果一直TLE

    后来想到可以先定义成指针数组，然后在初始化的时候使用 new int[10]这种，然后这样就可以当作int二维数组来用，放弃了vector之后侥幸过了。

    后来我过了之后，看了下书里，发现书中使用了merge和resize，也使用了upper_bound，之后我又对我自己的代码进行调优了下，去掉了一次无用的初始化，然后发现其实不用vector、merge和resize，也不用upper_bound，全都自己实现就行，自己写new int[10]这种可变数组代替vector，自己写上文中的循环那种合并代替merge，自己写binarySearch去找小于number的数量代替upper_bound，也是可以过的，时间上也优化了一些，如下

    三、代码

    1、平方分割

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5. int bucket[320][320];
    6. int bucket_1[160][640];
    7. int dat[100009], sortedDat[100009], n, bQue[320], queLen, bQue_1[160], queLen_2, b, otherLen, other[100009];
    8. queue<int> que;
    9. void input()
    10. {
    11.     for (int i = 0; i < n; i++)
    12.     {
    13.         scanf("%d", &dat[i]);
    14.         sortedDat[i] = dat[i];
    15.     }
    16.     sort(sortedDat, sortedDat + n);
    17. }
    18. void bucketMethod()
    19. {
    20.     b = 1;
    21.     while (b * b <= n)
    22.     {
    23.         b++;
    24.     }
    25.     b--;
    26.     for (int i = 0; ((i + 1) * b) <= n; i++)
    27.     {
    28.         for (int j = 0; j < b; j++)
    29.         {
    30.             bucket[i][j] = dat[j + (i * b)];
    31.         }
    32.         sort(bucket[i], bucket[i] + b);
    33.     }
    34.     for (int i = 0; ((i + 1) * 2 * b) <= n; i++)
    35.     {
    36.         for (int j = 0; j < (2 * b); j++)
    37.         {
    38.             bucket_1[i][j] = dat[j + (i * b * 2)];
    39.         }
    40.         sort(bucket_1[i], bucket_1[i] + (2 * b));
    41.     }
    42. }
    43. void findBucket(int L, int R)
    44. {
    45.     queLen = 0;
    46.     for (int i = 0; ((i + 1) * b) <= n; i++)
    47.     {
    48.         if ((i * b) >= L && ((i + 1) * b) <= R)
    49.         {
    50.             bQue[queLen++] = i;
    51.         }
    52.     }
    53. }
    54. void handleOther(int L, int R)
    55. {
    56.     otherLen = 0;
    57.     if (queLen == 0)
    58.     {
    59.         for (int i = L; i < R; i++)
    60.         {
    61.             other[otherLen++] = dat[i];
    62.         }
    63.     }
    64.     else
    65.     {
    66.         for (int i = L; i < (bQue[0] * b); i++)
    67.         {
    68.             other[otherLen++] = dat[i];
    69.         }
    70.         for (int i = ((bQue[queLen - 1] + 1) * b); i < R; i++)
    71.         {
    72.             other[otherLen++] = dat[i];
    73.         }
    74.     }
    75.     if (otherLen > 0)
    76.     {
    77.         sort(other, other + otherLen);
    78.     }
    79. }
    80. void findBucketPlus()
    81. {
    82.     queLen_2 = 0;
    83.     if (queLen == 0)
    84.     {
    85.         return;
    86.     }
    87.     while (!que.empty())
    88.     {
    89.         que.pop();
    90.     }
    91.     int i = 0;
    92.     while (i < queLen)
    93.     {
    94.         if ((i + 1) < queLen && (bQue[i] % 2 == 0))
    95.         {
    96.             bQue_1[queLen_2++] = bQue[i] / 2;
    97.             i += 2;
    98.         }
    99.         else
    100.         {
    101.             que.push(bQue[i]);
    102.             i++;
    103.         }
    104.     }
    105.     if (queLen_2 != 0)
    106.     {
    107.         queLen = 0;
    108.         while (!que.empty())
    109.         {
    110.             int _front = que.front();
    111.             que.pop();
    112.             bQue[queLen++] = _front;
    113.         }
    114.     }
    115. }
    116. int binarySearch(int *arr, int len, int num)
    117. {
    118.     int l = -1, r = len;
    119.     while (l + 1 < r)
    120.     {
    121.         int mid = (l + r) / 2;
    122.         if (arr[mid] < num)
    123.         {
    124.             l = mid;
    125.         }
    126.         else
    127.         {
    128.             r = mid;
    129.         }
    130.     }
    131.     return (l + 1);
    132. }
    133. void solve(int k)
    134. {
    135.     if (queLen == 0 && queLen_2 == 0)
    136.     {
    137.         printf("%d\n", other[k - 1]);
    138.         return;
    139.     }
    140.     int l = -1, r = n;
    141.     while (l + 1 < r)
    142.     {
    143.         int mid = (l + r) / 2;
    144.         int cnt = 0;
    145.         for (int i = 0; i < queLen; i++)
    146.         {
    147.             cnt = cnt + binarySearch(bucket[bQue[i]], b, sortedDat[mid]);
    148.         }
    149.         for (int i = 0; i < queLen_2; i++)
    150.         {
    151.             cnt = cnt + binarySearch(bucket_1[bQue_1[i]], 2 * b, sortedDat[mid]);
    152.         }
    153.         if (otherLen > 0)
    154.         {
    155.             cnt = cnt + binarySearch(other, otherLen, sortedDat[mid]);
    156.         }
    157.         if (cnt < k)
    158.         {
    159.             l = mid;
    160.         }
    161.         else
    162.         {
    163.             r = mid;
    164.         }
    165.     }
    166.     printf("%d\n", sortedDat[l]);
    167. }
    168. int main()
    169. {
    170.     int m, i, j, k;
    171.     while (~scanf("%d%d", &n, &m))
    172.     {
    173.         input();
    174.         bucketMethod();
    175.         while (m--)
    176.         {
    177.             scanf("%d%d%d", &i, &j, &k);
    178.             findBucket(i - 1, j);
    179.             handleOther(i - 1, j);
    180.             findBucketPlus();
    181.             solve(k);
    182.         }
    183.     }
    184.     return 0;
    185. }

    2、线段树

    1. #include 
    2. #include 
    3. using namespace std;
    4. int *dat[262150];
    5. int num[100009], len[262150], n_, n, inf = 0x3f3f3f3f, nodeQue[262150], queLen, sortedNum[100009];
    6. void input()
    7. {
    8.     for (int i = 0; i < n_; i++)
    9.     {
    10.         scanf("%d", &num[i]);
    11.     }
    12. }
    13. void build()
    14. {
    15.     n = 1;
    16.     while (n < n_)
    17.     {
    18.         n = n * 2;
    19.     }
    20.     for (int i = (2 * n - 2); i >= 0; i--)
    21.     {
    22.         if (i >= (n - 1))
    23.         {
    24.             dat[i] = new int[1];
    25.             len[i] = 1;
    26.             if ((i - n + 1) < n_)
    27.             {
    28.                 dat[i][0] = num[i - n + 1];
    29.             }
    30.             else
    31.             {
    32.                 dat[i][0] = inf;
    33.             }
    34.         }
    35.         else
    36.         {
    37.             int pLen = 0;
    38.             int lChild = i * 2 + 1;
    39.             int rChild = i * 2 + 2;
    40.             pLen = 0;
    41.             dat[i] = new int[len[lChild] + len[rChild]];
    42.             int lId = 0;
    43.             int rId = 0;
    44.             while (lId < len[lChild] || rId < len[rChild])
    45.             {
    46.                 if (rId >= len[rChild])
    47.                 {
    48.                     dat[i][pLen++] = dat[lChild][lId++];
    49.                 }
    50.                 else if (lId < len[lChild] && dat[lChild][lId] < dat[rChild][rId])
    51.                 {
    52.                     dat[i][pLen++] = dat[lChild][lId++];
    53.                 }
    54.                 else
    55.                 {
    56.                     dat[i][pLen++] = dat[rChild][rId++];
    57.                 }
    58.             }
    59.             len[i] = pLen;
    60.         }
    61.     }
    62.     for (int i = 0; i < n_; i++)
    63.     {
    64.         sortedNum[i] = dat[0][i];
    65.     }
    66. }
    67. void query(int l_, int r_, int i, int l, int r)
    68. {
    69.     if (l_ >= r || r_ <= l)
    70.     {
    71.     }
    72.     else if (l >= l_ && r <= r_)
    73.     {
    74.         nodeQue[queLen++] = i;
    75.     }
    76.     else
    77.     {
    78.         query(l_, r_, i * 2 + 1, l, (l + r) / 2);
    79.         query(l_, r_, i * 2 + 2, (l + r) / 2, r);
    80.     }
    81. }
    82. int binarySearch(int i, int number)
    83. {
    84.     int l = -1, r = len[i];
    85.     while (l + 1 < r)
    86.     {
    87.         int mid = (l + r) / 2;
    88.         if (dat[i][mid] < number)
    89.         {
    90.             l = mid;
    91.         }
    92.         else
    93.         {
    94.             r = mid;
    95.         }
    96.     }
    97.     return (l + 1);
    98. }
    99. void solve(int k)
    100. {
    101.     if (queLen == 1)
    102.     {
    103.         printf("%d\n", dat[nodeQue[0]][k - 1]);
    104.         return;
    105.     }
    106.     int l = -1, r = n_;
    107.     while (l + 1 < r)
    108.     {
    109.         int mid = (l + r) / 2;
    110.         int cnt = 0;
    111.         for (int i = 0; i < queLen; i++)
    112.         {
    113.             cnt += binarySearch(nodeQue[i], sortedNum[mid]);
    114.         }
    115.         if (cnt < k)
    116.         {
    117.             l = mid;
    118.         }
    119.         else
    120.         {
    121.             r = mid;
    122.         }
    123.     }
    124.     printf("%d\n", sortedNum[l]);
    125. }
    126. int main()
    127. {
    128.     int m, i, j, k;
    129.     scanf("%d%d", &n_, &m);
    130.     input();
    131.     build();
    132.     while (m--)
    133.     {
    134.         scanf("%d%d%d", &i, &j, &k);
    135.         queLen = 0;
    136.         query(i - 1, j, 0, 0, n);
    137.         solve(k);
    138.     }
    139.     return 0;
    140. }

  • 相关阅读:
    linux的shell编程入门
    智能加压站远程监控与维护，提高小区供水效率与安全性的创新方案
    [C++]多态是如何调用不同的函数对象的？
    2022/11/28-29总结
    3_电机的发展及学习方法
    基于实用拜占庭共识算法（PBFT）的区块链模型的评估与改进
    C++初阶--内存管理
    LeetCode Python - 31.下一个排列
    基于J2EE的弹幕视频网站设计
    java毕业设计对外汉语教学辅助平台Mybatis+系统+数据库+调试部署
  • 原文地址：https://blog.csdn.net/qq_53038151/article/details/133612625