Codeforces Round 642 (Div. 3) D. Constructing the Array

题目连接：Problem - 1353D - Codeforces

题意：根据所示方法构造数组。

我们可以发现每次填充一个数之后，我们就得到两段新的线段。所以按照题目所说的方法，我们模拟就可以得到答案。但我们需要把更新控制到nlog(n)以内。

每次选择，我们要先选择最长的字段，在长度相等的情况下选择最靠左边的。我们可以将最靠左边的这个条件转换为右边剩余长度最长的，这样字段和剩余长度的增减性相同，我们可以用pair来存储字段长度和剩余长度，用大根堆来存储每个线段，每次取出队头元素，得到答案。

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second

using namespace std;
typedef pair<int,int> PII ;
const int N = 200010 ;
int n ;
int a[N] ;

void solve()
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++) a[i] = 0 ;
    priority_queue<PII> h ;
    h.push({n , 0}) ;
    int cnt = 1 ;
    while(h.size())
    {
        auto t = h.top() ;
        h.pop() ;
        int y = n - t.y , x = n - t.y - t.x + 1 ;
        int mid = (x + y) / 2 ;
        a[mid] = cnt ++ ;

        if(mid - x != 0)
        {
            h.push({mid - x , n - mid + 1}) ;
        }
        if(y - mid != 0)
        {
            h.push({y - mid , n - y}) ;
        }
    }

    for(int i = 1 ; i <= n ; i ++)
        cout << a[i] << " " ;
    puts("") ;
}

signed main()
{
    int t ;
    cin >> t ;
    while(t --)
    {
        solve() ;
    }
    return 0 ;
}