The Median of the Median of the Median - Problem - QOJ.ac

给定一个序列{ai},i从1到n,首先构造一个序列{bij},i和j同样是从1到n,bij表示{ai....aj}的中位数,然后再构造一个{cij},cij表示{bii.....bij.....b(i+1,i+1).......b(i+1,j).......bjj}的中位数,最后要求输出序列{cij}的中位数.

在寻找cij之前,我们要先将bij找出来,如何在n^2logn的时间复杂度之内求出所有bij,这时我们要用到对顶堆.一个大根堆一个小根堆,具体的看这个教程A16 对顶堆 第k大的数_哔哩哔哩_bilibili

在找出bij以后,我们就要考虑如何求出cij的中位数了,想要求出cij的中位数,我们可以考虑使用二分答案,那么二分的二段性存在于哪个数组上,对于cij的中位数midc,由于是向下取整,一定会有大于一半的数要大于midc,和小于一半的数要小于midc,那么我们可以二分midc,将b中小于midc的数都设为-1,大于等于midc的数设为1,我们求不出具体的cij的值,但是我们可以求出cij比midc大还是比midc小.具体的可以使用二维前缀和,可以快速求出一个块的val.这个val表示的cij.

如何直到cij是大于mid还是小于mid,cij=pre[j][j] - pre[j][i - 1] - pre[i - 1][j] + pre[i - 1][i - 1];画个图,将i和j的位置标一标就知道怎么求了.

如果val大于0表示大于等于的midc的数大于一半,该cij大于等于midc,cnt++,否则小于midc,cnt--.如果cnt>0说明大于等于cnt的cij大于一半,让需要更大的mid以此来减小cnt,如果cnt<=0则减少midc,让r=mid,如果cij的个数是偶数,最后cnt的值应该等于2,如果是奇数,最后cnt的值应该等于1.

int main() {
	std::ios::sync_with_stdio(false), std::cin.tie(0),std::cout.tie(0);
	/*while (t--) {
		solve();
	}*/
	int n;
	std::cin >> n;
	std::vector<int>a(n+1);
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}
	std::vector<std::vector<int>>b(n + 1, std::vector<int>(n + 1)),d(n + 1, std::vector<int>(n + 1)),pre(n + 1, std::vector<int>(n + 1));
	for (int i = 1; i <= n; i++) {
		std::priority_queue<int>q1;//大根堆
		std::priority_queue<int, std::vector<int>, std::greater<int>>q2;
		for (int j = i; j <= n; j++) {
			int m = (j - i+1) / 2 + 1;
			if(q2.empty()||a[j]>=q2.top())q2.push(a[j]);
			else q1.push(a[j]);//否则放入小根堆
			while (q2.size() > m)q1.push(q2.top()),q2.pop();//
			while (q2.size() < m)q2.push(q1.top()), q1.pop();
			b[i][j] = q2.top();
		}
	}
	auto check = [&](int mid)->bool {
		//大于等于中位数的设为1,小于的设为-1
		for (int i = 1; i <= n; i++) {
			for (int j = i; j <= n; j++) {
				if (j >= i) {
					if (b[i][j] >= mid)d[i][j] = 1;
					else d[i][j] = -1;
				}
			}
		}
		//求一个二维前缀和
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				pre[i][j]=pre[i-1][j] +pre[i][j-1]-pre[i-1][j-1]+d[i][j];
			}
		}
		int cnt = 0;
		
		for (int i = 1; i <= n; i++) {
			for (int j = i; j <= n; j++) {
				
				int value = pre[j][j] - pre[j][i - 1] - pre[i - 1][j] + pre[i - 1][i - 1];
				if (value > 0) cnt++;
				else cnt--;
				

			}
		}
		
		if (cnt > 0)return true;
		else return false;
	};
	int l = 0, r = 1e9 + 1;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		if (check(mid))l = mid;
		else r = mid;
	}
	std::cout << l << "\n";
	return 0;
}

midc,value,cnt,l,r的关系,l和r决定midc,midc决定1和-1的个数,从而决定每个cij(value)的值,从而决定cnt的值,最后改变l和r,value>0表示该cij>=midc,value<=0表示该cij<midc.cnt记录cij>=midc的个数和cij<midc的个数的差值,如果midc是中位数,那么cnt必须是>0的,例如22345中位数是3,223456的中位数是3,如果midc真是中位数,cij>=midc的个数一定是大于一半的,而cij<midc的个数一定是小于一半的,他们两不可能相等,如果cnt>0,那么让l=mid,最后l便是答案,应为cnt>0包含了正确的中位数的情况,否则让r=mid,从而增大cnt的值.