Codeforces Round #590 (Div. 3)E. Special Permutations

問題概要

p_i(n) を次の順列で定義する : p_i(n) = \{i, 1, 2, \cdots, i-1, i+1, \cdots, n\} (i 番目を先頭に移動しただけ)

pos(p_i(n), j) を, p_i(n) における j の index 番号とする. このとき, 長さ m の数列 x に対して f を

f(p_i(n)) = \sum_{j=1}^{m-1} |pos(p_i(n), x_j) - pos(p_i(n), x_{j+1})|

と定義する. f(p_1(n)), f(p_2(n)), \cdots, f(p_n(n)) をすべて求めよ. 

問題へのリンク

制約

  • 1 \le n, m \le 2\times 10^5
  • 1 \le x_i \le m

解法

pos(p_i(n), j) がどのような値をとるかを考えましょう. これは, i=j のとき 1, i \lt j のとき j, i \gt j のとき j+1 です. よって, 各 x_i に対して pos(p_j(n), x_i) がとる値は 3 種類しかないので, 答えの配列に対応する区間の値を足しこめばいいです. imos 法で何とかします.

実装

Submission #147560038 - Codeforces