编号1、14、514、1919……的人，出列！

预览版题面

$a$ 个人肩并肩地排成一条直线, 你不知道他们的具体身高, 也就是说他们的身高可能是任意值。

现在, 如果有人问你, 你能否打包票说至少存在一种方法使得队列中的 $b$ 个人向前迈出一步, 而出列的人身高是从左往右递增(或递减)的。

题解

结论

设 $n^{2}+1$ 个人肩并肩地排成一条直线。于是, 总能使 $n+1$ 个人向前迈出一步, 使得从左至右他们的身高是递增（或递减）的。

下面给出该结论的证明 (鸽巢原理)

我们首先阐明子序列的概念。如果 $b_{1}, b_{2}, \cdots, b_{m}$ 是一个序列, 那么, $b_{4}, b_{4}, \cdots, b_{4}$ 是 一个子序列, 只要 $1 \leqslant i_{1}<i_{2}<\cdots<i_{k} \leqslant m$ 。因此, $b_{2}, b_{4}, b_{5}, b_{6}$ 是 $b_{1}, b_{2}, \cdots, b_{8}$ 的子序列, 伹 $b_{2}, b_{6}, b_{5}$ 则不是。子序列 $b_{i_{1}}, b_{i_{2}}, \cdots, b_{i_{2}}$ 若满足 $b_{i_{1}} \leqslant b_{i_{2}} \leqslant \cdots \leqslant b_{i_{2}}$ 则称为递增的（更恰当地说 是非递减的)，而若满足 $b_{i_{1}} \geqslant b_{i_{2}} \geqslant \cdots \geqslant b_{i_{2}}$ 则称为递减的。 现在来证明结论。我们假设不存在长度为 $n+1$ 的递增子序列, 证朋必然存在长度 为 $n+1$ 的递减子序列。对于每一个 $k=1,2, \cdots, n^{2}+1$ , 设 $m_{k}$ 为从 $a_{k}$ 开始的最长的递增子序 列的长度。假设对于每一个 $k=1,2, \cdots, n^{2}+1$ , 有 $m_{k} \leqslant n$ , 使得不存在长度为 $n+1$ 的递增子 序列。因为对于每一个 $k=1,2, \cdots, n^{2}+1$ , 都有 $m_{k} \geqslant 1$ 成立, 所以 $m_{1}, m_{2}, \cdots, m_{a^{2}+1}$ 是 $1$ 和 $n$ 之间的 $n^{2}+1$ 个整数。由鸽巢原理的加强版可知, $m_{1}, m_{2}, \cdots, m_{n^{2}+1}$ 中有 $n+1$ 个是相等 的。令

$$m_{k_{1}}=m_{k_{2}}=\cdots=m_{k_{n+1}}$$

其中 $1 \leqslant k_{1}<k_{2}<\cdots<k_{n+1} \leqslant n^{2}+1$ 。假设对于某个 $i=1,2, \cdots, n$ , 有 $a_{k_{i}}<a_{k_{1+1}}$ 。那么, 由于 $k_{i}<k_{i+1}$ , 我们可做成一个从 $a_{k_{i+1}}$ 开始的最长的递增子序列, 并将 $a_{k_{i}}$ 放在前面而得到一个从 $a_{i}$ , 开始的递增子序列。由于这意味着 $m_{k_{i}}>m_{k_{i+1}}$, 因此我们得出 $a_{k_{i}} \geqslant a_{k_{i+1}}$ 的结论。由于这对于每个 $i=1,2, \cdots, n$ 均成立, 因此我们有

$$a_{k_{1}} \geqslant a_{k_{2}} \geqslant \cdots \geqslant a_{k_{n+1}} $$

从而得出 $a_{k_{1}}, a_{k_{2}}, \cdots, a_{k_{n+1}}$ 是一个长度为 $n+1$ 的递减子序列。

标准程序 (高精部分采用__int128)

// Idea: Codeboy
// Data: Codeboy
// Code: Codeboy
// Solution: Codeboy

// Problem: 编号1、14、514、1919……的人，出列！

#include <bits/stdc++.h>
using namespace std;
typedef __int128 lll;
template<typename T> inline void read(T &x){
    x=0;T w=1,ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}

template<typename T> inline void print(T x, bool flag = 0)
{
	if(!flag && x == 0){putchar('0'); return ;}
	if (!x && flag) return ;
	if (x < 0) putchar('-'),x = -x;
	print(x / 10, 1);
	putchar(x % 10 + '0');
}

bool check(lll a, lll b){
	if((b - 1) >= LONG_LONG_MAX) return 0;
	if((b - 1) * (b - 1) + 1 <= a) return 1;
	return 0;
}

signed main(){
	int T;
	read(T);
	while(T--){
		lll a, b;
		read(a); read(b);
		if(check(a, b)) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}