(POJ - 3685) matrix (two sets and two parts)

 

Chinese question meaning ： There is one N Square matrix The first i That's ok ,j The value of the column Aij =i^2 + 100000 × i + j^2 - 100000 × j + i × j, We need to find out the third part of this matrix M Small value .

Looking at this equation first, we can find ,Aij along with i To increase by , So we can pass two points x To find out , The content of every two points is to judge the ratio x Whether the number of small numbers is greater than or equal to m, If the number is greater than or equal to m, Then the current binary value is greater than or equal to the answer , On the contrary, the current binary value is less than the answer , The specific dichotomy process is as follows ：

We enumerate columns violently , The number of each column is monotonically increasing , So for each column, we can enumerate in two , The total complexity is n*log(n)*log(q)（q Is the range size of the possible values of the answer ）, There are quite a lot of details , The code is attached below

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
ll n,m;
ll cal(ll i,ll j)
{
	return i*i+100000*i+j*j-100000*j+i*j;
}
bool check(ll x)// If it is less than or equal to x The number of is greater than or equal to m One returns true, Instead, return to false 
{
	ll cnt=0;
	for(int i=1;i<=n;i++)// Enumerating columns 
	{
		ll l=0,r=n,mid;// Binary enumeration, each column is less than x The number of numbers 
		if(l==r) return cal(1,1)<=x;
		while(l<r)
		{
			mid=l+r+1>>1;
			if(cal(mid,i)<=x) l=mid;// Find a value greater than or equal to x The last number of  
			else r=mid-1;
		}
		cnt+=l;
		if(cnt>=m) return true;
	}
	return false;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		ll l=-9999999999,r=9999999999,mid;// Enumerator  
		while(l<r)
		{
			mid=l+r>>1;
			if(check(mid)) r=mid;// explain mid Larger 
			else l=mid+1;
		}
		printf("%lld\n",l);
	}
	return 0;
}