树状数组求逆序对 + 离散化？
我好像永远都记不住怎么用树状数组求逆序对……以前我记得都是正着写的，这次怎么得倒着写才能过……
然后本题a的范围极大，但是n的范围不大，500000，需要先手离散化一波，之后就可以正常按照树状数组操作了。然后在query的时候注意要-1.
我们来看一下代码。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #include<utility> #include<map> #define pr pair<int,int> #define mp make_pair #define fi first #define sc second #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') #define lowbit(x) x & (-x) using namespace std; typedef long long ll; const int M = 500005; const int N = 32005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >='0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int n,a[M],c[M],tot,d[M]; ll ans; void add(int x) { while(x <= M-5) a[x]++,x += lowbit(x); } int query(int x) { int cur = 0; while(x) cur += a[x],x -= lowbit(x); return cur; } void clear() { tot = ans = 0; memset(a,0,sizeof(a)); } int main() { while(1) { n = read(); if(n == 0) break; clear(); rep(i,1,n) c[i] = read(),d[i] = c[i]; sort(c+1,c+1+n); tot = unique(c+1,c+1+n) - c - 1; per(i,n,1) { int k = lower_bound(c+1,c+1+tot,d[i]) - c; //printf("#%d ",k); ans += query(k-1),add(k); } printf("%lld ",ans); } return 0; }