2025/11/10
C. 圆环（circle）
感觉比 T2 要简单/kk
dp 状态是好想的，非常明显可以设 \(f_{i, j}\) 表示当操作完 \(i\) 操作，另一只手在 \(j\) 位置的最小代价。这个东西的状态转移方程也不难。
- 当由不是完成操作的手过来的时候 \(f_{i, p_{i - 1}} = \min f_{i - 1, p_{i - 1}} + Dist(p_{i - 1}, a_i)\)
- 当由是完成操作的手过来的时候 \(f_{i, j} = f_{i - 1, j} + Dist(a_{i - 1}, a_i)\)
显然当同一时间需要去两个位置的时候需要禁止第 2 种操作，所以其他位置的值应该设为 \(INF\)。这个东西显然是可以用线段树优化的，只需要维护 \(\min\limits_{l \leq j \leq r}f_{i, j}, \min\limits_{l \leq j \leq r}f_{i, j} - j, \min\limits_{l \leq j \leq r}f_{i, j} + j\) 这样就可以完成转移
区间赋值 tag 没清空，调了好久。标记下放一定要记得清空标记！！！
Code
#include <algorithm>
#include <iostream>using namespace std;
using ll = long long;const int kN = 3e5 + 1;
const ll kI = 1e15;int c, n, m;
struct Op {int t, p;
} op[kN];
struct Tr {ll p, s, mn, add, clr;
} tr[kN * 4];
struct Info {ll p, s;
};
Info Min(Info x, Info y) { return {min(x.p, y.p), min(x.s, y.s)}; }void Func(int x, ll k) { tr[x].p += k, tr[x].s += k, tr[x].mn += k, tr[x].add += k; }
void Clear(int x) { tr[x].mn = tr[x].p = tr[x].s = kI, tr[x].clr = 1, tr[x].add = 0; }
void Pushdown(int x) {if (tr[x].clr)Clear(x * 2), Clear(x * 2 + 1);Func(x * 2, tr[x].add), Func(x * 2 + 1, tr[x].add), tr[x].add = tr[x].clr = 0;
}
void ChkMin(int p, ll v, int x = 1, int l = 1, int r = n) {if (l == r) {v < tr[x].mn && (tr[x] = {v + l, v - l, v, 0, 0}, 0);return;}Pushdown(x);int m = (l + r) / 2;if (p <= m)ChkMin(p, v, x * 2, l, m);elseChkMin(p, v, x * 2 + 1, m + 1, r);tr[x].mn = min(tr[x * 2].mn, tr[x * 2 + 1].mn), tr[x].p = min(tr[x * 2].p, tr[x * 2 + 1].p), tr[x].s = min(tr[x * 2].s, tr[x * 2 + 1].s);
}
void Build(int x = 1, int l = 1, int r = n) {tr[x] = (l == 1 ? (Tr){1, -1, 0, 0, 0} : (Tr){kI, kI, kI, 0, 0});if (l == r)return;int m = (l + r) / 2;Build(x * 2, l, m), Build(x * 2 + 1, m + 1, r);
}
Info Query(int nl, int nr, int x = 1, int l = 1, int r = n) {if (nl <= l && r <= nr)return {tr[x].p, tr[x].s};Pushdown(x);int m = (l + r) / 2;if (nr <= m)return Query(nl, nr, x * 2, l, m);if (nl > m)return Query(nl, nr, x * 2 + 1, m + 1, r);return Min(Query(nl, nr, x * 2, l, m), Query(nl, nr, x * 2 + 1, m + 1, r));
}int Dist(int l, int r) {(l > r) && (swap(l, r), 0);return min(r - l, n - r + l);
}int main() {
#ifndef ONLINE_JUDGEfreopen("in", "r", stdin);freopen("out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);cin >> c >> n >> m;for (int i = 1; i <= m; i++)cin >> op[i].t >> op[i].p;sort(op + 1, op + m + 1, [](Op& x, Op& y) { return x.t < y.t; });Build(), op[0].p = n;for (int i = 1; i <= m; i++) {Info L = Query(1, op[i].p), R = Query(op[i].p, n);ll v = min({op[i].p + L.s, n - op[i].p + L.p, R.p - op[i].p, n + R.s + op[i].p});if (op[i].t == op[i - 1].t)Clear(1);elseFunc(1, Dist(op[i - 1].p, op[i].p));ChkMin(op[i - 1].p, v);// cout << tr[1].mn << '\n';}cout << tr[1].mn;return 0;
}