“蔚来杯“2022牛客暑期多校训练营2 G.[Link with Monotonic Subsequence] 分块构造

G. Link with Monotonic Subsequence 构造 题目分析

要求构造一个长度为 n n n的序列，使得序列的 max ⁡ ( lis ( p ) , lds ( p ) ) \max(\text{lis}(p), \text{lds}(p)) max(lis(p),lds(p))尽可能的小。

狄尔沃斯定理：对偏序集 < A ， ≤ > ，设A中最长链的长度是 n n n，则将 A A A中元素分成不相交的反链，反链个数至少是 n n n。

那么有 lds ( p ) = c n t ( lis(p) ) \text{lds}(p) = cnt(\text{lis(p)}) lds(p)=cnt(lis(p))，那么显然 max ⁡ ( lis ( p ) , lds ( p ) ) ≥ max ⁡ ( k , k n ) ≥ n \max(\text{lis}(p), \text{lds}(p)) \geq \max(k, \frac{k}{n}) \geq \sqrt{n} max(lis(p),lds(p))≥max(k,nk​)≥n ​ 。因此直接构造 n \sqrt{n} n ​个块即可。

Code

#include 
#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