一、题目大意
长度为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;
}