大致是官方题解，因为题解里没有 \(\mathcal{O(x\log x)}\) 的做法。
设 \(x\) 偶数项值域为 \(V\)。
设 \(s_i = t_i ^ 2 = \sum\limits_{j=1}^{i} x_i\)，随后 \(V \ge x_{2i} = s_{2i} - s_{2i-1} = t^2_{2i} - t^2_{2i-1} \ge 2t_{2i-1}+1\)
那么 \(t_{2i} < V\)。
考虑计算出对于所有 \(x\in[1,V]\)，使得 \(x = b ^ 2 - a ^ 2\) 的二元组 \((a,b)\)。 这里是可以暴力的。
直接枚举 \(a,b\)，如果 \(b^2 - a^2 > V\) 就跳出。
复杂度： \(V \ge b^2 - a^2 = \sum\limits_{i=a}^{b-1}2i+1\ge(2a+1)(b-a)\)
\(b-a\le \dfrac{V}{2a+1}<\dfrac{V}{a}\)。即 \(\mathcal{O}(V\log V)\)。
对于每个 \(2i\)，求出 \(t_{2i-1}, t_{2i}\)，这时凭直觉找出 \(x_{2i} = b^2 - a^2\)，中最小的 \(a\)。这样使得前缀和最小，更有机会有解（大雾）。
#include <bits/stdc++.h>
#include <assert.h>
#define int long long
typedef long long ll;
using namespace std;
inline int read(){
register int x=0,f=0,ch=getchar();
while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
while('0'<=ch&&ch<='9')x=x*10+(ch^'0'),ch=getchar();
return f?-x:x;
}
const int MAX = 2e5+5;
int t[MAX];
int n;
vector<pair<int,int>>v[MAX];
#define mp make_pair
signed main(){
for(int a=1;a<=MAX-5;++a) {
for(int b=a+1, x;(x=b*b-a*a)<=MAX-5;++b) {
v[x].push_back(mp(a,b));
}
}
n = read();
for(int i=2;i<=n;i+=2) {
int x = read();
t[i] = -1;
for(auto h:v[x]) {
if(h.first > t[i-2]) {
t[i-1] = h.first;
t[i] = h.second;
break;
}
}
if(t[i] == -1) {
puts("No");
return 0;
}
}
puts("Yes");
for(int i=1;i<=n;++i) {
printf("%lld ", t[i] * t[i] - t[i-1] * t[i-1]);
}
return 0;
}