BZOJ2259: [Oibh]新型计算机 DP+线段树

据说有$O(n)$*玄学的算法？

不知道怎么$O(n)$，于是就水了一发线段树，虽然复杂度有点虚，不过在BZ能过。

首先设$f_i$表示修改$i$这个位置的数，使得$[i,n]$这一段数合法的最小代价。

不难得到转移：

\[f_i=min_{i<j\leq{n}}\{f_j+|a_i-(j-i-1)|\}\]

分类讨论来拆开绝对值：

当$a_i\leq{j-i-1}$即$j\geq{a_i+i+1}$时，有$f_i=(f_j+j)-a_i-i-1$，在线段树上维护最小的$f_j+j$就行了。

当$a_i\geq{j-i-1}$即$j\leq{a_i+i+1}$时，有$f_i=(f_j-j)+a_i+i+1$，在线段树上维护最小的$f_j-j$就行了。

这样就能做到$O(nlogn)$辣。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;

#define N 2100000
#define inf 0x3f3f3f3f
struct SegmentTree {
	int mn1[N], mn2[N], M;
	void init(int _size) {
		for (M = 1; M < _size + 2; M <<= 1);
		for (int i = 0; i < (M << 1); ++i)
			mn1[i] = mn2[i] = inf;
	}
	int query1(int tl, int tr) {
		if (tl > tr)
			return inf;
		int re = inf;
		for (tl += M - 1, tr += M + 1; tl ^ tr ^ 1; tl >>= 1, tr >>= 1) {
			if (~tl & 1)
				re = min(re, mn1[tl ^ 1]);
			if (tr & 1)
				re = min(re, mn1[tr ^ 1]);
		}
		return re;
	}
	int query2(int tl, int tr) {
		if (tl > tr)
			return inf;
		int re = inf;
		for (tl += M - 1, tr += M + 1; tl ^ tr ^ 1; tl >>= 1, tr >>= 1) {
			if (~tl & 1)
				re = min(re, mn2[tl ^ 1]);
			if (tr & 1)
				re = min(re, mn2[tr ^ 1]);
		}
		return re;
	}
	void modify1(int x, int v) {
		for (mn1[x += M] = v, x >>= 1; x; x >>= 1)
			mn1[x] = min(mn1[x << 1], mn1[x << 1 ^ 1]);
	}
	void modify2(int x, int v) {
		for (mn2[x += M] = v, x >>= 1; x; x >>= 1)
			mn2[x] = min(mn2[x << 1], mn2[x << 1 ^ 1]);
	}
}Seg;

int getc() {
	static const int L = 1 << 15;
	static char buf[L], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, L, stdin);
		if (S == T)
			return EOF;
	}
	return *S++;
}

int getint() {
	int c;
	while (!isdigit(c = getc()));
	int x = c - '0';
	while (isdigit(c = getc()))
		x = (x << 1) + (x << 3) + c - '0';
	return x;
}

int A[1000010], f[1000010];

int dist(int x, int y) {
	return x < y ? y - x : x - y;
}

int main() {
	//freopen("tt.in", "r", stdin);
	int n = getint(), i, j;
	for (i = 1; i <= n; ++i)
		A[i] = getint();
	
	Seg.init(n);
	
	for (i = n; i >= 1; --i) {
		f[i] = dist(A[i], n - i);
		if (i + 1 <= A[i] + i + 1)
			f[i] = min(f[i], A[i] + i + 1 +Seg.query1(i + 1, min(n, A[i] + i + 1)));
		if (A[i] + i + 1 <= n)
			f[i] = min(f[i], Seg.query2(A[i] + i + 1, n) - A[i] - i - 1);
		Seg.modify1(i, f[i] - i);
		Seg.modify2(i, f[i] + i);
	}
	
	cout << f[1] << endl;
	
	return 0;
}