【JZOJ6292】序列【思维】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/6292

---

思路：

这道题移动数字不是很好办，考虑移动下标，这样和移动数字是等价的。
如果第$i$个数字的下标移动到了$i+1$，那么原来的$|a_i-i|$就变成了$|a_i-i-1|$，那么原来$a_ileq i$的贡献就增加了1，$a_i>i$的贡献就减少了1。
所以我们需要记录下每一个时刻有多少个$a_ileq i$，同时又有多少个$a_i>i$。考虑到在移动下标时$a_i$与$i$的大小关系可能是会变的，所以我们需要开一个桶来记录移动了$i$个单位后，有多少的大小关系会变动。
这样就做到了每次$O(1)$修改，时间复杂度$O(n)$。

---

代码：

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=5000010;
int n,s1,s2,a[N],t[N];
ll ans,minn;

int read()
{
	int d=0; char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch))
		d=(d<<3)+(d<<1)+ch-48,ch=getchar();
	return d;
}

int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	n=read();
	for (register int i=1;i<=n;i++)
	{
		a[i]=read();
		if (a[i]>i)
		{
			s1++;
			t[a[i]-i]++;
			minn+=(ll)a[i]-i;
		}
		else
		{
			s2++;
			minn+=(ll)i-a[i];
		}
	}
	ans=minn;
	for (register int i=1;i<=n;i++)
	{
		int k=n-i+1;
		ans=ans+(ll)s2-s1;
		ans=ans-(ll)(n-a[k]+1)+(ll)(a[k]-1);
		if (a[k]<=1) s2++; 
		else
		{
			s1++;
			t[i+a[k]-1]++;
		}
		s2--;
		s1-=t[i]; s2+=t[i];
		minn=min(minn,ans);
	}
	printf("%lld",minn);
	return 0;
}