D.小红的差值构造 - easy+hard+extreme

注意到我们只需要确定x的位置即可，因为y = x + l。
所求的其实就是到和的最短距离。
在左端的数全部离最近，在右端的数全部离最近，在和中间的数直接对半分即可。
这样我们就可以通过等差数列求和的方式求出确定了某个的，具体求的时候对边界情况处理即可。
的范围取即可，因为的时候显然不可能是最优解，而的时候和的情况是一样的。
直接暴力显然是不足以通过本题。
我们又注意到，这个区间内肯定存在一个点是最优解，并且距离越远越大，然后就转换成了求一个二次函数的最小值，直接三分即可。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll n, l;

ll check(ll x){
    ll res = 0;
  	//x左端的数字
    ll t = x - 1;
    res += t * (1 + t) / 2;
  	//x和y中间的数字，取一半，向上取整
    ll k = ((l - 1) + 1) / 2;
    if(x + k <= n){
        res += k * (1 + k) / 2;
        //y <= n
      	if(x + l <= n){
            ll temp = (l - 1) - k;
            res += temp * (1 + temp) / 2;
            temp = (n - (x + l));
            res += temp * (1 + temp) / 2;
        }else{
          	// y > n，做差即可
            ll t1 = x + l - (x + k) - 1;
            ll t2 = x + l - n - 1;
            res += t1 * (1 + t1) / 2 - t2 * (1 + t2) / 2;
        }
    }else{
      	// 无法取到k个，直接取完
        ll temp = n - x;
        res += temp * (1 + temp) / 2;
    }
    return res;
}


void solve() {
    cin >> n >> l;
    ll lo = 1, hi = n + 1;
    while(lo + 2 < hi){
        int mid1 = lo + (hi - lo) / 3;
        int mid2 = hi - (hi - lo) / 3;
        if(check(mid1) >= check(mid2)){
            lo = mid1;
        }else{
            hi = mid2;
        }
    }
    ll mi = check(lo);
    ll ans = lo;
    for(int x = lo; x < hi; x++){
        if(check(x) < mi){
            mi = check(x);
            ans = x;
        }
    }
    cout << ans << " " << ans + l << " " << check(ans) << "\n";
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}