kuangbin专题23 二分尺取单调栈队列

zhujio / 2023-06-07 / 原文

Matrix

题意：给你一个n * n的矩阵，矩阵一点的值是i^2 + 100000 × i + j^2 - 100000 × j + i × j，问在整个矩阵中第ｍ大的值是多少。

//想分解公式但是什么都没看出来，这个公式是用于判断单调性的
//主函数里面二分答案，check二分查找有多少个小于当前M的数
//显然x越大结果越大，相同y情况下对于x是递增的（根据此二分）

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<string.h>
#include<stdio.h>
#include<queue>
#include<stack> 
#include<set>
#define endl "\n"
typedef long long ll;
using namespace std;
//想分解公式但是什么都没看出来，这个公式是用于判断单调性的
//主函数里面二分答案，check二分查找有多少个小于当前M的数
ll n,m;
ll calc(ll x,ll y){
    //显然x越大结果越大，相同y情况下对于x是递增的（根据此二分）
    return x*x+100000*x+y*y-100000*y+x*y;
}
bool check(ll x){
    ll cnt=0;
    for(ll j=1;j<=n;j++){
        ll L=0,R=n+1;
        while(L+1<R){
            ll M=(L+R)>>1;
            if(x>calc(M,j))L=M;
            else R=M;
        }
        cnt+=L;
    }
    return cnt<m;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T=1;cin>>T;
    while(T--){
        cin>>n>>m;
        ll L=-1e12,R=1e12;
        while(L+1<R){
            ll M=(L+R)>>1;
            if(check(M))L=M;
            else R=M;
        }
        cout<<L<<endl;
    }
    return 0;
}