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<k，则L=mid，否则R=mid，这样的话，最终的临界情况就是，所有块中，小于sortedDat[L]的元素为k-1个，小于sortedDat[L+1]的元素为k个，此时，sortedDat[L]就是当前区间里第k大的数。

考虑下复杂性 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]<arrR[R]

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<k，则L=mid，否则R=mid，临界情况就是，区间里小于L+1下标的元素是k个，小于L下标的元素的个数是k-1个，此时，L下标的元素就是区间内第k大的。

我一开始用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、平方分割

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int bucket[320][320];
int bucket_1[160][640];
int dat[100009], sortedDat[100009], n, bQue[320], queLen, bQue_1[160], queLen_2, b, otherLen, other[100009];
queue<int> que;
void input()
{for (int i = 0; i < n; i++){scanf("%d", &dat[i]);sortedDat[i] = dat[i];}sort(sortedDat, sortedDat + n);
}
void bucketMethod()
{b = 1;while (b * b <= n){b++;}b--;for (int i = 0; ((i + 1) * b) <= n; i++){for (int j = 0; j < b; j++){bucket[i][j] = dat[j + (i * b)];}sort(bucket[i], bucket[i] + b);}for (int i = 0; ((i + 1) * 2 * b) <= n; i++){for (int j = 0; j < (2 * b); j++){bucket_1[i][j] = dat[j + (i * b * 2)];}sort(bucket_1[i], bucket_1[i] + (2 * b));}
}
void findBucket(int L, int R)
{queLen = 0;for (int i = 0; ((i + 1) * b) <= n; i++){if ((i * b) >= L && ((i + 1) * b) <= R){bQue[queLen++] = i;}}
}
void handleOther(int L, int R)
{otherLen = 0;if (queLen == 0){for (int i = L; i < R; i++){other[otherLen++] = dat[i];}}else{for (int i = L; i < (bQue[0] * b); i++){other[otherLen++] = dat[i];}for (int i = ((bQue[queLen - 1] + 1) * b); i < R; i++){other[otherLen++] = dat[i];}}if (otherLen > 0){sort(other, other + otherLen);}
}
void findBucketPlus()
{queLen_2 = 0;if (queLen == 0){return;}while (!que.empty()){que.pop();}int i = 0;while (i < queLen){if ((i + 1) < queLen && (bQue[i] % 2 == 0)){bQue_1[queLen_2++] = bQue[i] / 2;i += 2;}else{que.push(bQue[i]);i++;}}if (queLen_2 != 0){queLen = 0;while (!que.empty()){int _front = que.front();que.pop();bQue[queLen++] = _front;}}
}
int binarySearch(int *arr, int len, int num)
{int l = -1, r = len;while (l + 1 < r){int mid = (l + r) / 2;if (arr[mid] < num){l = mid;}else{r = mid;}}return (l + 1);
}
void solve(int k)
{if (queLen == 0 && queLen_2 == 0){printf("%d\n", other[k - 1]);return;}int l = -1, r = n;while (l + 1 < r){int mid = (l + r) / 2;int cnt = 0;for (int i = 0; i < queLen; i++){cnt = cnt + binarySearch(bucket[bQue[i]], b, sortedDat[mid]);}for (int i = 0; i < queLen_2; i++){cnt = cnt + binarySearch(bucket_1[bQue_1[i]], 2 * b, sortedDat[mid]);}if (otherLen > 0){cnt = cnt + binarySearch(other, otherLen, sortedDat[mid]);}if (cnt < k){l = mid;}else{r = mid;}}printf("%d\n", sortedDat[l]);
}
int main()
{int m, i, j, k;while (~scanf("%d%d", &n, &m)){input();bucketMethod();while (m--){scanf("%d%d%d", &i, &j, &k);findBucket(i - 1, j);handleOther(i - 1, j);findBucketPlus();solve(k);}}return 0;
}

2、线段树

#include <iostream>
#include <algorithm>
using namespace std;
int *dat[262150];
int num[100009], len[262150], n_, n, inf = 0x3f3f3f3f, nodeQue[262150], queLen, sortedNum[100009];
void input()
{for (int i = 0; i < n_; i++){scanf("%d", &num[i]);}
}
void build()
{n = 1;while (n < n_){n = n * 2;}for (int i = (2 * n - 2); i >= 0; i--){if (i >= (n - 1)){dat[i] = new int[1];len[i] = 1;if ((i - n + 1) < n_){dat[i][0] = num[i - n + 1];}else{dat[i][0] = inf;}}else{int pLen = 0;int lChild = i * 2 + 1;int rChild = i * 2 + 2;pLen = 0;dat[i] = new int[len[lChild] + len[rChild]];int lId = 0;int rId = 0;while (lId < len[lChild] || rId < len[rChild]){if (rId >= len[rChild]){dat[i][pLen++] = dat[lChild][lId++];}else if (lId < len[lChild] && dat[lChild][lId] < dat[rChild][rId]){dat[i][pLen++] = dat[lChild][lId++];}else{dat[i][pLen++] = dat[rChild][rId++];}}len[i] = pLen;}}for (int i = 0; i < n_; i++){sortedNum[i] = dat[0][i];}
}
void query(int l_, int r_, int i, int l, int r)
{if (l_ >= r || r_ <= l){}else if (l >= l_ && r <= r_){nodeQue[queLen++] = i;}else{query(l_, r_, i * 2 + 1, l, (l + r) / 2);query(l_, r_, i * 2 + 2, (l + r) / 2, r);}
}
int binarySearch(int i, int number)
{int l = -1, r = len[i];while (l + 1 < r){int mid = (l + r) / 2;if (dat[i][mid] < number){l = mid;}else{r = mid;}}return (l + 1);
}
void solve(int k)
{if (queLen == 1){printf("%d\n", dat[nodeQue[0]][k - 1]);return;}int l = -1, r = n_;while (l + 1 < r){int mid = (l + r) / 2;int cnt = 0;for (int i = 0; i < queLen; i++){cnt += binarySearch(nodeQue[i], sortedNum[mid]);}if (cnt < k){l = mid;}else{r = mid;}}printf("%d\n", sortedNum[l]);
}
int main()
{int m, i, j, k;scanf("%d%d", &n_, &m);input();build();while (m--){scanf("%d%d%d", &i, &j, &k);queLen = 0;query(i - 1, j, 0, 0, n);solve(k);}return 0;
}