题目链接：https://www.luogu.org/problemnew/show/P1908
1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <queue> 5 #include <string> 6 #include <cstdio> 7 #include <cstring> 8 #include <iostream> 9 #include <algorithm> 10 #define forn(i, n) for (int i = 0; i < (n); i++) 11 #define forab(i, a, b) for (int i = (a); i <= (b); i++) 12 #define forba(i, b, a) for (int i = (b); i >= (a); i--) 13 #define mset(a, n) memset(a, n, sizeof(a)) 14 #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) 15 #define P pair<int,int> 16 #define fi first 17 #define se second 18 using namespace std; 19 #define N 500005 20 #define maxn 1005 21 #define inf 0x3f3f3f3f 22 #define ll long long 23 ll a[N], c[N * 4]; 24 ll b[N]; 25 int n; 26 int sum; 27 inline int lowbit(int x) { return x & (-x); } 28 void add(int x,int y) 29 { 30 for (; x <= N;x+=lowbit(x)) 31 c[x] += y; 32 } 33 int ask(int x) 34 { 35 int ans = 0; 36 for (; x;x-=lowbit(x)) 37 ans += c[x]; 38 return ans; 39 } 40 bool cmp(int x,int y) 41 { 42 return b[x] > b[y]; 43 } 44 int main() 45 { 46 scanf("%d", &n); 47 forab(i, 1, n) 48 { 49 scanf("%d", b + i); 50 a[i] = i; 51 } 52 sort(a + 1, a + 1 + n, cmp); 53 // forab(i, 1, n) cout << a[i] << " "; 54 // cout << endl; 55 forab(i, 1, n) 56 { 57 58 // cout << "sum=" << sum << endl; 59 add(a[i], 1); 60 sum += ask(a[i] - 1); 61 } 62 cout << sum << endl; 63 system("pause"); 64 } 65 /* 66 6 67 5 4 2 6 3 1 68 69 */