[AtCoder] ARC 077 E: guruguru

題目連結:http://arc077.contest.atcoder.jp/tasks/arc077_c

---

賽中完全沒頭緒，最後是被雷了才知道這題怎麼做的XD想法大概是我們在算cost的時候其實就是算$\sum_{i=1}^{n}(R_i-L_i)$，那顯然等價於$\sum_{i=1}^{n}R_i-\sum_{i=1}^{n}L_i$(注意若其中$R_i < L_i$，那$R_i = arr[i]+m$)，那這樣對於一個$x$，他的cost就會是$\sum_{i=1}^{n}R_i-\sum_{i=1}^{n}L_i-x \times C_x+LL_x+C_x$，其中$C_x$為x被多少個區間覆蓋，$LL_x$則是覆蓋到x的那些線段的左界和。概念其實是先算原本的，再把多算跟少算的補回去。這樣的話先預處理好$C_x$跟$LL_x$，我們就可以在$O(1)$的時間內計算一個x的cost，所以就枚舉x即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
 
const int INF = 2000000000;
const int N = 100000 + 10;
lld arr[N], cnt[N], sm[N];
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;cin>>n>>m;
	for(int i=0;i<n;i++) cin>>arr[i];
	lld sumL=0, sumR=0;
	for(int i=0;i<n-1;i++) sumL+=arr[i];
	for(int i=1;i<n;i++) sumR+=arr[i]+m*(arr[i-1]>arr[i]);
	for(int i=1;i<n;i++){
		if(arr[i-1]>arr[i]){
			cnt[arr[i-1]+1]+=1;
			cnt[m+1]-=1;
			cnt[1]+=1;
			cnt[arr[i]+1]-=1;
			sm[arr[i-1]+1]+=arr[i-1];
			sm[m+1]-=arr[i-1];
			sm[1]+=arr[i-1]-m;
			sm[arr[i]+1]-=arr[i-1]-m;
		}else{
			cnt[arr[i-1]+1]+=1;
			cnt[arr[i]+1]-=1;
			sm[arr[i-1]+1]+=arr[i-1];
			sm[arr[i]+1]-=arr[i-1];
		}
	}
	for(int i=1;i<=m+1;i++) cnt[i]+=cnt[i-1];
	for(int i=1;i<=m+1;i++) sm[i]+=sm[i-1];
	lld val=sumR-sumL;
	for(int i=1;i<=m;i++){
		lld curV=sumR-sumL-cnt[i]*(i-1)+sm[i];
		if(curV < val) val=curV;
	}
	cout<<val<<'\n';
	return 0;
}