"Weilai Cup" 2022 Niuke summer multi school training camp 2 g.[link with monotonic subsequence] block structure

G. Link with Monotonic Subsequence structure

Topic analysis

It is required to construct a length of $n$ Sequence , Make the sequence $\max (\text{lis}(p),\text{lds}(p))$ As small as possible .

Dilworth theorem ： Pair poset $<A,\le >$, set up A The length of the longest chain in is $n$, Will $A$ The elements in are divided into disjoint inverse chains , The number of anti chains is at least $n$.

So there are $\text{lds}(p)=cnt(\text{lis(p)})$, So clearly $\max (\text{lis}(p),\text{lds}(p))\ge \max (k,\frac{k}{n})\ge \sqrt{n}$ . Therefore, direct construction $\sqrt{n}$ Just one block .

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;


inline void solve(){
    
    int n = 0; cin >> n;
    int b = ceil(sqrt(n));
    while(n > 0){
    
        for(int i = max(1ll, n - b + 1); i <= n; i++) cout << i << " ";
        n -= b;
    }
    cout << endl;
}

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