AGC001F

首先考虑求出原排列的逆置换,设为 $Q$ ,于是交换就变成了如果 $|Q_i - Q_{i+1}| < k$ 那么可以交换相邻的两个元素。

于是,对于任意 $i,j$ 如果满足 $|Q_i - Q_j| < k$ 那么他们的相对顺序一定无法改变。

而且可以证明,如果两个排列 $Q,P$ 中所有元素的相对位置的关系是一样的,那么一定可以从 $Q$ 移到 $P$ 。考虑这种情况下的一次移动就可以让逆序减少 $1$ 。有限步的操作后一定可以让 $Q$ 成为 $P$ (画一下发现很对)。

于是有了一种做法,对于 $i<j$ 满足 $|Q_i - Q_j| < k$ 我们连一条 $Q_i \to Q_j$ 的有向边表示先 $Q_i$ 后 $Q_j$ ,于是我们要求的就是这个图上的一个拓扑序,满足 $1$ 尽量靠前,在 $1$ 尽量靠前的情况下 $2$ 尽量靠前… 不难发现这样的限制等价于原排列字典序尽量小。这个限制与字典序是没有关系的。比如 $3 \to 1 , 2 \to 4$ 在这个限制下应该拿 $3,1,2,4$ 但是字典序最小的应当是 $2,3,1,4$ 。

求这个拓扑序的方法可以参照 LOJ2114 这个题。我们每次拿可以放在最后的最大的数放在最后一定不劣。所以我们可以建反图再跑拓扑序,最后把拓扑序倒过来就得到了所求。

现在问题在于这样的边有 $O(n^2)$ 条。优化方法大致有两种。首先可以不建边,直接在线段树上判断一个点的出度来做拓扑排序,这是官方题解的做法。大概还有一个做法是优化边的数量。

考虑我们当前已经通过加边让 $1 \sim i - 1$ 的点对间都满足了之前提到的限制。现在我们加入 $Q_i$ 。我们只给满足 $0< Q_j - Q_i < k$ 以及 $0 < Q_i - Q_j < k$ 且大的两个 $j$ 与 $Q_i$ 连边。由于上下是对称的,我们只考虑 $Q_j > Q_i$ 的情况。因为之前 $1 \sim i - 1$ 中与 $i$ 满足 $Q_t -Q_i < k$ 的位置 与 $Q_j$ 的相对顺序已经是确定好的,并且一定是 $Q_j$ 处于最靠后,所以直接拿 $Q_j$ 向 $Q_i$ 连边即可满足所有的限制。这样连边最多也就连 $2n$ 条,边数变成了 $O(n)$ 级别。连边过程用线段树维护,总复杂度是连边的 $O(n\log n)$。

最后别忘了要还原成原排列。。这毒瘤样例全部不还原都能过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 500006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , k;
int A[MAXN] , Q[MAXN];

int T[MAXN << 2];
void add( int rt , int l , int r , int x , int c ) {
if( l == r ) { T[rt] = c; return; }
int m = l + r >> 1;
if( x <= m ) add( rt << 1 , l , m , x , c );
else add( rt << 1 | 1 , m + 1 , r , x , c );
T[rt] = max( T[rt << 1] , T[rt << 1 | 1] );
}
int que( int rt , int l , int r , int L , int R ) {
if( L <= l && R >= r ) return T[rt];
int m = l + r >> 1 , re = 0;
if( L <= m ) re = max( re , que( rt << 1 , l , m , L , R ) );
if( R > m ) re = max( re , que( rt << 1 | 1 , m + 1 , r , L , R ) );
return re;
}

vi G[MAXN];
int deg[MAXN] , as[MAXN];

void solve() {
cin >> n >> k;
rep( i , 1 , n ) scanf("%d",A + i) , Q[A[i]] = i;
rep( i , 1 , n ) {
int t = que( 1 , 1 , n , Q[i] , min( Q[i] + k - 1 , n ) );
if( t ) G[Q[i]].pb( Q[t] ) , ++ deg[Q[t]];// , cout << Q[i] << ' ' << Q[t] << endl;
t = que( 1 , 1 , n , max( 1 , Q[i] - k + 1 ) , Q[i] );
if( t ) G[Q[i]].pb( Q[t] ) , ++ deg[Q[t]];// , cout << Q[i] << ' ' << Q[t] << endl;
add( 1 , 1 , n , Q[i] , i );
}
priority_queue<int> q;
rep( i , 1 , n ) if( !deg[i] ) q.push( i );
vi re;
while( !q.empty() ) {
int u = q.top(); q.pop();
for( int v : G[u] ) {
-- deg[v];
if( !deg[v] ) q.push( v );
}
re.pb( u );
}
reverse( all( re ) );
rep( i , 1 , n ) as[re[i - 1]] = i;
rep( i , 1 , n ) printf("%d\n",as[i]);
}

signed main() {
// freopen("input","r",stdin);
// freopen("stdout","w",stdout);
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2020/11/18/agc001f/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog