c/c++语言开发共享P2995 [USACO10NOV]牛的照片(树状数组,逆序对)

题目：

p2995 [usaco10nov]牛的照片cow photographs
p4545 [usaco10nov]奶牛的图片cow photographs
sp7809 cowpic – cow photographs

解析：

一个环形的逆序对
最大的数可以放在最小的数的左边而不贡献逆序对
所以就可以在原序列的基础上，从小到大枚举序列中的数，并且让这个数(+n)，变成最大的数，将某个数加(n)后，左边的数就不对它贡献逆序对了，所以逆序对个数减去((pos[i]-1))，而其右边会贡献((n-pos[i]))个逆序对，这样从小到大枚举并取min就好了
(pos[i])表示(i)在序列中的位置
注意开long long

代码：

#include <bits/stdc++.h> #define int long long using namespace std;  const int n = 5e5 + 10; const int inf = 0x3f3f3f3f;  int n, m, ans, sum; int a[n], t[n], pos[n];  namespace bit {     inline int lowbit(int x) {return x & -x;}     void add(int x, int y) {for (; x <= n; x += lowbit(x)) t[x] += y;}     int query(int x) {         int ret = 0;         for (; x; x -= lowbit(x)) ret += t[x];         return ret;     } }  using namespace bit;  signed main() {     ios::sync_with_stdio(false);     cin >> n;     for (int i = 1; i <= n; ++i) cin >> a[i], pos[a[i]] = i;     for (int i = 1; i <= n; ++i) {         add(a[i], 1);         sum += i - query(a[i]);     }     ans = sum;     for (int i = 1; i <= n; ++i) {         sum = sum - (pos[i] - 1) + (n - pos[i]);         ans = min(ans, sum);         }     cout << ans; }