如何在有序矩阵中找第k大的数？

378. 有序矩阵中第K小的元素 题目链接
一个矩阵从左到右递增、从上到下递增怎么找第k大的数？
1、 把矩阵变成一维然后排个序
2、 合并有序数组那样合并
3、 二分
主要说二分怎么求。
二分一个第k大是多少。
check的时候，也就是判断有没有k个数大于等于mid
比mid小的肯定在是左上角一些元素。
比如这样一个矩阵：

如果mid是12的话：
就有左上角这样一些：

这样的话就可以用n+n的时间快速统计出来有多少个数大于等于mid！！
(明明可以暴力的)

int sum = 0;
int j = 0;
int i = n - 1;
while(i >= 0 && j < n)
{
   
	if(a[i][j] > x)
		i -- ;
	else
	{
   
		sum += i + 1;
		j ++ ;
	}
}

然后用二分来写就好了
代码：

class Solution {
   
public:
	int n;
	int flag;
	bool pd(int x,vector<vector<int>>& a)
	{
   
		int sum = 0;
		int j = 0;
		int i = n - 1;
		while(i >= 0 && j < n)
		{
   
			if(a[i][j] > x)
				i -- ;
			else
			{
   
				sum += i + 1;
				j ++ ;
			}
		}
		return sum >= flag;
	}

    int kthSmallest(vector<vector<int>>& a, int k) {
   
    	flag = k;
    	n = a.size();
    	int l = a[0][0];
    	int r = a[n - 1][n - 1];
    	while(l < r)
    	{
   
    		int mid = l + r >> 1;
    		if(pd(mid, a))
    			r = mid;
    		else
    			l = mid + 1;
    	}
    	return l;
    }
};

然后来看这道题 1508. 子数组和排序后的区间和

题目链接

题目大意:

有一个数组，计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。然后将他们排序，求排完序之后 l ~ r 的和。
这个n只有1000，所以也可以暴力，
lt学长问n有100000的时候怎么处理，我不会了，我好菜

题解

看这篇题解会的：
题解地址
f(k)表示排完序后求前k项的和
所以答案就是f® - f(l - 1)。
先用数组构造一个矩阵：
a[i][j]代表原数组中 i ~ j 的元素的和。
这个矩阵只有右上角有值。
求的就是这个矩阵中前k小的值得和。
所以找到第k小，然后求比nk小的元素得所有和就好了。
注意到构造的这个矩阵也是一个有序的，因为是前缀和得矩阵。
这个矩阵不用完全构造出来。因为第i行j列得元素就是sum[j] - sum[i - 1]
然后用上面的方法求一个第k小就好了
代码：

#include<algorithm>
#include<iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef unsigned long long ull;
typedef set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.second < b.second;}};
int lb(int x){
   return  x & -x;}
//friend bool operator < (Node a,Node b) 重载
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 1e5+10;
const int M = 100000;

class Solution {
   
public:
	ll sum[maxn];
	ll ss[maxn];
	int n;
	bool pd(int x,int flag)
	{
   
		int num = 0;
		int r = 1;
		for (int  i= 1; i <= n; i ++ )
		{
   
			while(r <= n && sum[r] - sum[i - 1] <= x)
				r ++ ;
			num += r - i;
		}
		return num >= flag;
	}

	int getk(int x)
	{
   
		int l = 0, r = 1e5;// 因为数据大小小。。
		while(l < r)
		{
   
			int mid = l + r >> 1;
			if(pd(mid,x))
			{
   
				r = mid;
			}
			else
				l = mid + 1;
		}
		return l;
	}
	ll getans(int x)
	{
   
		int num = getk(x);//第k大的数是num
		// printf("%d %d\n",x,num);
		int r = 1;
		ll ans = 0;
		int s =0 ;
		for (int i = 1; i <= n; i ++ )
		{
   
			while(r <= n && sum[r] - sum[i - 1] < num)
				r++ ;
			int cnt = r - i;
			s += cnt;
			ans += (ss[r - 1] - ss[i - 1] - 1ll * cnt * sum[i - 1])%mod;
		}
		ans += 1ll * num * (x - s) % mod;
		ans %= mod;
		return ans;
	}

    int rangeSum(vector<int>& a, int np, int left, int right) {
   
    	n = np;
    	for (int i = 1; i <= n; i ++ )
    		sum[i] = sum[i - 1] + a[i - 1];
    	for (int i = 1; i <= n; i ++ )
    	{
   
    		ss[i] = (ss[i - 1] + sum[i])%mod;
    	}
    	ll s1 = getans(right);
    	ll s2 = getans(left - 1);
    	// printf("%lld %lld\n",s1,s2);
    	return (s1 - s2 + mod) % mod;
    }
};



// int main()
// {
   
// /* code */
// int n;
// scanf("%d",&n);
// std::vector<int> v;
// for (int i= 1; i <= n; i ++ )
// {
   
// int x;
// scanf("%d",&x);
// v.pb(x);
// }
// int l,r;
// scanf("%d%d",&l,&r);
// cout<<asd.rangeSum(v,n,l,r);
// return 0;
// }
/* 4 1 2 3 4 1 5 */