hihocoder#1707 麻烦的第K大问题

由区间第 \(x\times y\) 大 又到多重集第 \(k\) 大

从普通的元素到我们要求的\(ans\)之间是有大小关系的（在区间内 \(<-->\) 区间第\(x\times y\)大 \(<-->\) 多重集内第\(k\)大）

再加上二分时产生的单调性：

此时设二分的值为 \(mid\) ,标记数组为 \(b[]\)

那么对于区间 \([l,l+len\times x-1]\)

其第 \(x \times y\) 比 \(mid\) 大 当且仅当 \(sum\{b_r , b_l-1\}>=k*y\)

把 \(b_i\) 弄成前缀和 统计符合条件的 区间 的个数就完成了 \(check\)

bool check(int mid){
    for (int i = 1;i<=n;++i) b[i] = (a[i] > mid),b[i] += b[i - 1];
    int res = 0;
    for(int i = 1;i * len <= n;++i)
        for (int l = 1,r = l + i * len - 1;r <= n;++l,++r)
            if (b[r] - b[l - 1] >= i * y) ++res;
    return res >= k;
}

时间复杂度 $O(n log^2 $ \(n)\)

再想想正解

对于二分、标记的思路应该大致是不变的

想想对于式子本身的转化/化简

对于 \(i\) 不就是 $\frac{r-l+1}{len} $ 吗

带入两边变成只与 \(r\) 和 \(l\) 这两个下标有关的表达式

\(b_r \times len - r \times y >= b_{l-1} \times y - (l-1) \times y\)

关于 \(i\) 的函数 \(cal(i) = b_i \times len - i \times y\)

\(cal(r) >= cal(l-1) , l<r\)

这不是 逆序对/二维偏序 还是什么,用数据结构（树状数组/权值线段树）维护即可

关键代码(这里用树状数组)

bool check(int x){
	int ans = 0;
	b[0] = 0;
        for(i,1->n) b[i] = b[i-1] + (a[i]>=x);
	for(i,1->n) c[i] = {b[i]*len-i*y,i};
        c[0]={-inf,0},c[n+1] = {0,0};
	sort(c+1,c+n+2);
	int cur = 0;
	for(i,1->n+1){// 离散化
		if(c[i].num != c[i-1].num) ++cur;
		b[c[i].id] = cur;// 再次利用 b ,作为 cal
	}
	for(i,0->n-1){
		for(int j=i;j<=n;j+=len) ans += tree.query(b[j]),tree.add(b[j],1);
		for(int j=i;j<=n;j+=len) tree.add(b[j],-1);
	}
	return ans>=k;
}