308147: CF1473C. No More Inversions
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
No More Inversions
题意翻译
### 题目描述 你有一个长度为 $n$ 的序列 $a$。$a=\{1,2,3,\dots,k-1,k,k-1,k-2,\dots,k-(n-k)\}(k\le n<2k)$。 我们称 $a$ 中的一个逆序对为下标 $i,j$ 的两个元素有 $a[i]>a[j] (i<j)$。 你能构造出一些长度为 $k$ 的排列 $p$,然后用以下规则构造长度为 $n$ 序列 $b$:$b[i]=p[a[i]]$。 你的目标是找到一个排列 $p$,在 $b$ 中逆序对的个数不超过 $a$ 中逆序对个数的情况下使得 $b$ 的字典序最大。 小提示:长度为 $k$ 的排列列中 $1\sim k$ 各出现且仅出现一次。 另一个小提示:序列 $s$ 的字典序小于 $t$ 意味着 $s$ 是 $t$ 的前缀或者第一个$s_i\ne t_i$ 有 $s_i<t_i$。 ### 输入格式 第一行是一个整数 $t(1\le t\le1000)$——测试数据组数。 每一组测试数据只有一行,包含两个整数 $n,k(k\le n<2k;1\le k\le10^5)$ ——$a$ 的长度及其峰值。 ### 输出格式 对于每一个测试数据,输出 $k$ 个整数——排列 $p$ 使得 $b$ 是不增加逆序对个数的字典序最大序列。 可以证明 $p$ 是存在且唯一的。题目描述
You have a sequence $ a $ with $ n $ elements $ 1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k) $ ( $ k \le n < 2k $ ). Let's call as inversion in $ a $ a pair of indices $ i < j $ such that $ a[i] > a[j] $ . Suppose, you have some permutation $ p $ of size $ k $ and you build a sequence $ b $ of size $ n $ in the following manner: $ b[i] = p[a[i]] $ . Your goal is to find such permutation $ p $ that the total number of inversions in $ b $ doesn't exceed the total number of inversions in $ a $ , and $ b $ is lexicographically maximum. Small reminder: the sequence of $ k $ integers is called a permutation if it contains all integers from $ 1 $ to $ k $ exactly once. Another small reminder: a sequence $ s $ is lexicographically smaller than another sequence $ t $ , if either $ s $ is a prefix of $ t $ , or for the first $ i $ such that $ s_i \ne t_i $ , $ s_i < t_i $ holds (in the first position that these sequences are different, $ s $ has smaller number than $ t $ ).输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The first and only line of each test case contains two integers $ n $ and $ k $ ( $ k \le n < 2k $ ; $ 1 \le k \le 10^5 $ ) — the length of the sequence $ a $ and its maximum. It's guaranteed that the total sum of $ k $ over test cases doesn't exceed $ 10^5 $ .
输出格式
For each test case, print $ k $ integers — the permutation $ p $ which maximizes $ b $ lexicographically without increasing the total number of inversions. It can be proven that $ p $ exists and is unique.
输入输出样例
输入样例 #1
4
1 1
2 2
3 2
4 3
输出样例 #1
1
1 2
2 1
1 3 2