此题真是一言难尽。下面这么大一串，真的只是在讲一个小模拟。。。
此题也是被几个julao反复讲，各种五花八门的奇淫巧技，什么数学变形，树状数组，差分，单调……好吧，我是那种只会30分暴力的人
，也没理由嫌弃这些我听不懂的做法。
于是看到了一篇极其妙的题解，思路是建坐标系，然而这位julao的题解的code跑出来只有30pts。借用大佬的图
首先，以i为横坐标，ai为纵坐标，建立平面直角坐标系，将点全部描在坐标系里，并画出y=x的直线，可以发现，点到直线的竖直距离
之和，就是我们要求的答案。
然而怎么求不同顺序的答案呢？
只需要左右平移这条直线！
可以发现，向左平移，在这条直线上方的点，到直线的竖直距离会减小1，而在这条直线下方或处于直线上的点，到直线的竖直距离会
加1。
如果是向右平移，显然是恰好相反，所以要枚举所有情况，只需要将这条直线向一个方向，平移n次，每次平移一个单位。
然而有一个特殊的点，n->1
假如选择向左平移，1~n-1个点的值的计算方式完全不变。
但是第n个点会变，所以每次平移特殊处理第n个点。
其实你或许已经发现了，图象是答案的几何含义，本质上我们的平移操作等效于在序列上移动下标。
到这里，大体思路就已经出现了，但是我觉得细节也是比较难懂的（或许是我太菜了），所以我再稍微补充一下。
1.怎么维护每次移动后的直线上下方的点呢？用up,down记录在直线上方下方的点的个数。先预处理点对于初始直线的上下方个数。再维
护一个d[ ]数组，每出现一个处于直线上方的点，就将这个 d[s]++(s为这个点到直线的竖直距离)。这 表示在直线上方的距离处s处，有
d[s]个 点，由初中数学知识易证，y=x向左平移1单位等价于向上平移1单位。所以当我们一共平移了i个单位后，我们就需要利用d[i]来更
新在直线上方的点，显然，在直线上方的点的数量up-=d[i]，因为本来离初始直线距离为i的点，在直线经过i个单位的平移后，已经落在
了直线上，而不再在直线上方。相应地down+=d[i]
2.因为ai<=n的，所以第n个点本来一定是属于down集的，现在相当于它移到了第一个位置，只要比1大的，就可从down集出来进入up集。
3.计算答案的时候是tmp+=down-up根据2中所述，最后一个点显然属于down集，所以它已经被算成了，对答案的贡献加一，所以真正的更新方式应是tmp+=down-up-1.
温馨提示：1.longlong
2.数组开四倍。我挂了半天，最后瞎搞胡乱改错然后过了。01dalao给我指点了一下，因为按照序列的理论上来说，d的偏移量是2n，而这又是个环，所以是4n空间。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define N 4000100 #define ll long long ll a[N],d[N]; ll n,ans,tmp,up,down; int main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); if(a[i]>i)tmp+=a[i]-i,up++,d[a[i]-i]++; else tmp+=i-a[i],down++; } ans=tmp; for(int i=1;i<=n;i++) { tmp+=down-up-1; tmp-=n-a[n-i+1],tmp+=a[n-i+1]-1; if(a[n-i+1]>1)up++,down--,d[i+a[n-i+1]-1]++; down+=d[i],up-=d[i]; ans=min(ans,tmp); } printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/NSD-email0820/p/9735072.html