OI

ARC 077 E - guruguru

E – guruguru

時間制限 : 2sec / メモリ制限 : 256MB

配点 : 700 点

問題文

snuke 君は明るさを m 段階に切り替えられる照明を買いに来ました。 この照明の 明るさは 1 以上 m 以下の整数で表され、 リモコンに付いた 2 種類のボタンで明るさを切り替えます。

1 つめのボタンは「順送り」ボタンで、 明るさを 1 増やすことができます。ただし、ボタンを押す前の明るさが最大の m である場合には、 明るさは 1 になります。

2 つめのボタンは「お気に入り」ボタンで、 購入時に決めたお気に入りの明るさ x に切り替えることが出来ます。

snuke 君はお気に入りの明るさ x を、できるだけ効率的に明るさが切り替えられるように設定しようと考えました。 snuke 君は今後 n−1 回明るさを切り替える予定で、i 回目には明るさ ai から 明るさ ai+1 に切り替えようと計画しています。 最初、明るさは a1 です。 ボタンを押す回数の合計が最小になるようにお気に入りの明るさ x を決めた時の ボタンを押す回数を求めて下さい。

制約

  • 2≤n,m≤105
  • 1≤ai≤m
  • ai≠ai+1
  • n,m,ai は整数である。

入力

入力は以下の形式で標準入力から与えられる。

1
2

n m
a1 a2 ... an

出力

ボタンを押す回数の合計の最小値を出力せよ。

入力例 1

Copy

1
2

4 6
1 5 1 4

出力例 1

Copy

1

5

お気に入りの明るさを 1,2,3,4,5,6 のそれぞれに設定したときのボタンを押す最小回数はそれぞれ 8,9,7,5,6,9 回です。 よって、お気に入りの明るさを 4 に設定したときにボタンを押す回数の合計を最小に出来ます。 お気に入りの明るさを 4 に設定したときの切り替え方は以下のとおりです。

  • 1 回目には、お気に入りボタンを 1 回押した後、順送りボタンを 1 回押します。
  • 2 回目には、順送りボタンを 2 回押します。
  • 3 回目には、お気に入りボタンを 1 回押します。

入力例 2

Copy

1
2

10 10
10 9 8 7 6 5 4 3 2 1

出力例 2

Copy

1

45

题意：给你一个环，每次操作可以选择向前走一格，或者走到设定好的一个位置。现在给出一个位置序列，问遍历这个序列最小操作次数。

题解：まず、お気に入りボタンは必ず明るさを切り替える一番最初に押した方が効率的です。なぜなら、それ以前に他のボタンを押していたとしても、お気に入りボタンを押した後の明るさは変わらないためです。順送りボタンのみを使って明るさ A から B に切り替えるためボタンを押す回数は、A ≤ B なら B − A 回で、A > B なら B + N − A 回です。これは、まとめて (B + N − A)%N と書けます。ただし、x%y で x を y で割ったあまりを表します。

よって、お気に入りボタンを最初に押した場合のボタンを押す回数は 1 +(B + N − X)%N 回で、そうでない場合は (B + N − A)%N 回です。

また、お気に入りボタンを使うのは、ai と ai+1 間（ai+1 を含む）の状態にお気に入りの明るさ x が存在しているときのみです。

以上を元に、お気に入りが x であるときと x + 1 である時でボタンを押す回数がどのように変わるか考えてみます。

• ai+1 = x である iお気に入りボタンを 1 回押すだけで済んでいたのが、順送りボタンを(ai+1 + N − ai)%N 回押さないといけなくなります。

• ai と ai+1 間（両端を含まない）に x があるような i順送りボタンを押す回数が 1 回減ります。

• それ以外変化無しです。

まとめると、ボタンを押す回数は、ai+1 = xであるすべてのiについて(ai+1+N − ai)%N − 1 回分増えて、ai と ai+1 間に x があるような i の数だけ減ります。

ai と ai+1 間に x があるような i の数は、累積和を取る操作を使うと O(n+m) で求めることができます。imos 法という名前で呼ばれることもあります。

ai+1 = x である i については、当然全部で n 個しか無いので、いちいち計算して足しても問題ありません。

以上から、x = 0 である場合の答えを求めた後、x = i の場合を使ってx = i + 1 の場合を順番に求めていくことで、すべての x についてボタンを押す回数が求まるため、最小値も求まります。

考场上有个地方把n当成m，WA成狗。

代码：

 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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100005;
const int N = maxn * 60;
vector<int> v[maxn];
int n, m, root1[maxn], root2[maxn], lc[N], rc[N], a[maxn], tot;
LL siz[N], nxt[N], cur[N], qsiz, qnxt, qcur;
void change(int &x, int y, int l, int r, LL c, LL n) {
    x = ++tot;
    lc[x] = lc[y];
    rc[x] = rc[y];
    siz[x] = siz[y] + 1;
    nxt[x] = nxt[y] + n;
    cur[x] = cur[y] + c;
    if (l == r) return;
    else {
        int mid = (l + r) >> 1;
        if (n <= mid) change(lc[x], lc[y], l, mid, c, n);
        else change(rc[x], rc[y], mid + 1, r, c, n);
    }
}
void query(int x, int y, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
        qsiz += siz[y] - siz[x];
        qnxt += nxt[y] - nxt[x];
        qcur += cur[y] - cur[x];
    }
    else {
        int mid = (l + r) >> 1;
        if (ll <= mid) query(lc[x], lc[y], l, mid, ll, rr);
        if (rr > mid) query(rc[x], rc[y], mid + 1, r, ll, rr);
    }
}
void query(int *root, int l1, int r1, int l2, int r2) {
    qsiz = qnxt = qcur = 0;
    if (l1 > r1 || l2 > r2) return;
    query(root[l1 - 1], root[r1], 1, m, l2, r2);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i < n; ++i)
        v[a[i]].push_back(a[i+1]);
    for (int i = 1; i <= m; ++i) {
        root1[i] = root1[i-1];
        root2[i] = root2[i-1];
        for (auto &x : v[i]) {
            if (x < i) change(root1[i], root1[i], 1, m, i, x);
            else change(root2[i], root2[i], 1, m, i, x);
        }
    }
    LL tmp, ans = 1e16;
    for (int i = 1; i <= m; ++i) {
        tmp = 0;
        query(root1, 1, i - 1, 1, m);       tmp += qnxt + qsiz * (m - i + 1);
        query(root2, 1, i - 1, i, m);       tmp += qnxt + qsiz * (1 - i);
        query(root2, 1, i - 1, 1, i - 1);   tmp += qnxt - qcur;
        query(root1, i, m, i, m);           tmp += qnxt + qsiz * (1 - i);
        query(root1, i, m, 1, i - 1);       tmp += qnxt + qsiz * m - qcur;
        query(root2, i, m, 1, m);           tmp += qnxt - qcur;
        ans = min(ans, tmp);
    }
    printf("%lld\n", ans);
}