将每个数字的位置存进该数字的vector中
原数组排个序从小到大处理，每次在vector里二分找到距离当前位置“最远”的位置（相差最大），更新答案
树状数组维护每个数字现在的位置和原位置之差
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 const int N = 100005; 5 int n; 6 int a[N], b[N]; 7 vector<int> v[N]; 8 int c[N]; 9 void modify(int x, int num) 10 { 11 while (x <= 100000) c[x] += num, x += x&-x; 12 } 13 int sum(int x) 14 { 15 int s = 0; 16 while (x) s += c[x], x -= x&-x; 17 return s; 18 } 19 int main() 20 { 21 scanf("%d", &n); 22 for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i]; 23 sort(b+1, b+1+n); 24 for (int i = 1; i <= n; i++) 25 v[a[i]].push_back(i); 26 LL ans = 0; 27 int now = 0; 28 for (int i = 1; i <= n;) 29 { 30 int p = lower_bound(v[b[i]].begin(), v[b[i]].end(), now) - v[b[i]].begin(); 31 if (p == 0) 32 { 33 int pos = v[b[i]][v[b[i]].size()-1]; 34 ans += pos - sum(pos) - (now - sum(now)); 35 now = pos; 36 } 37 else 38 { 39 int pos = v[b[i]][p-1]; 40 ans += n - sum(n) - (now-sum(now)) + pos - sum(pos); 41 now = pos; 42 } 43 for (int j = 0; j < v[b[i]].size(); j++) modify(v[b[i]][j], 1); 44 i += v[b[i]].size(); 45 } 46 cout << ans << endl; 47 }