灯泡开关

题目链接：ybtoj 20028

题目大意

就是每次可以将一个数加一或者到达你设定的一个点。
如果加到 m + 1 m+1 m+1 就会变回一。

然后给你一个序列，数原来是序列的第一个数，然后要变换到第二个数，在变成第三个，直到最后一个。

然后要你求最少操作次数。

思路

很容易想到 n 2 n^2 n2 做法，就是枚举设定的点。

但是怎么优化呢？
考虑一开始不设点，然后设 f i f_i fi​ 为设定的点设在 i i i 会使答案减少多少步。

那我们看，如果要从 x x x 走到 y y y，我们就来分类讨论。
如果你设的点是 x x x 或者 x + 1 x+1 x+1（如果加了超过 m m m 自动 − m -m −m，下同），那直接走会设跳了再走一样，甚至更优。
那如果设的点 x + 2 x+2 x+2 或者之后，那就会分别省 1 , 2 , 3 , . . . 1,2,3,... 1,2,3,... 步，以此类推。

那要让一个序列加上一个等差序列，很容易就想到要用双重差分。
第一次，变成 1 , 1 , 1 , . . . , − ( 前 面 1 的 个 数 ) 1,1,1,...,-(前面1的个数) 1,1,1,...,−(前面1的个数)。
第二次，变成这个：
1 , 0 , 0 , . . . , − ( 上 面 的 这 一 个 + 1 ) , ( 前 面 的 这 个 数 − 1 ) 1,0,0,...,-(上面的这一个+1),(前面的这个数-1) 1,0,0,...,−(上面的这一个+1),(前面的这个数−1)

但是你会发现它可能会断开两节。
那右边那一节还好，左边一节又要重新搞。

假设这里是从 i i i 开始。
那我们就开一个一重的差分数组，在第一位加 i − 1 i-1 i−1，在最后一位的后面减回去，就可以变成跟上面一样都从一开始了。

最后把它还原，然后找到减少数量最大的。
然后就算出答案了。

代码

#include<cstdio>
#include<iostream>

using namespace std;

int n, m, a[1000001], sum;
long long ans, an, cf[1000001], cf2[1000001];

long long getdis(int x, int y) {
	if (x < y) return (long long)(y - x);
	return (long long)(y + m - x);
}

void work(int x, int y, int from, int add) {
	cf[x] += (long long)from;
	cf[y + 1] -= (long long)from;
	cf2[x + 1] += (long long)add;
	cf2[y + 1] -= (long long)add * (long long)(y - x + 1);
	cf2[y + 2] += (long long)add * (long long)((y - x + 1) - 1);
}

int main()
{
	freopen("light.in", "r", stdin);
	freopen("light.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	
	for(int i = 2; i <= n; i++) {
		ans += getdis(a[i - 1], a[i]);
		
		if (a[i] > a[i - 1]) {
			if (a[i] - a[i - 1] > 1) work(a[i - 1] + 2, a[i], 1, 1);
		}
		else {
			if (m - a[i - 1] > 1) {
				work(a[i - 1] + 2, m, 1, 1);
				work(1, a[i], m - (a[i - 1] + 1) + 1, 1);
			}
			if (m - a[i - 1] == 1) {
				work(1, a[i], 1, 1);
			}
			if (m == a[i - 1] && a[i] > 1) work(2, a[i], 1, 1);
		}
	}
	
	for (int i = 2; i <= m; i++) {
		cf[i] += cf[i - 1];
		cf2[i] += cf2[i - 1];
	}
	for (int i = 2; i <= m; i++)
		cf2[i] += cf2[i - 1];
	for (int i = 1; i <= m; i++)
		an = max(cf[i] + cf2[i], an);
	
	printf("%lld", ans - an);
	
	return 0;
}