学到几点：
1、树状数组C[i]的构建，一则c[i]=s[i]-s[i-lowbit(i)];这是一直用的做法，现在学到一种新的，直接add(i,a[i])，（s[i]为a[1]到a[i]的和）
2、前缀和思想，树状数组的Sum本身就是基于前缀和的思想，本题把比某数小的数的个数，通过开大量空间+后缀数组，高效的统计出来比某数小的数的个数
3、其实我觉得通过这个题，可以做出来一种O(nlogn)的排序算法，当然不完善的地方就是只能是整数了，但是应该可以用vector+map解决？
贴自己的代码先，，，因为后面的Lrj大牛的代码太简洁...
#include#include #include #include #include #include using namespace std; #define MAXN 20010 #define SIZE 100015 int a[MAXN],sma[SIZE],c[SIZE],s[SIZE],e[SIZE],tot[SIZE]; int n,mmax; int lowbit(int i) { return i & (-i); } int sum(int i) { int ans=0; for(;i>0;i-=lowbit(i)) ans+=c[i]; return ans; } void add(int x, int d) { while(x <= SIZE) { c[x] += d; x += lowbit(x); } } void Init() { memset(c,0,sizeof(c)); memset(a,0,sizeof(a)); memset(sma,0,sizeof(sma)); memset(s,0,sizeof(s)); memset(e,0,sizeof(e)); memset(tot,0,sizeof(tot)); } int main() { //freopen(la4329.txt,r,stdin); int t; long long ans; scanf(%d,&t); while(t--) { mmax=0; ans=0; Init(); scanf(%d,&n); for(int i=1;i<=n;i++) { scanf(%d,&a[i]); mmax=max(mmax,a[i]); add(a[i],1); //c[i]=sum(a[i]-1); e[a[i]]=1; sma[a[i]]=sum(a[i]-1); } memset(c,0,sizeof(c)); for(int i=1;i<=mmax;i++) { s[i] =s[i-1]+e[i]; c[i]=s[i]-s[i-lowbit(i)]; tot[i]=sum(i-1); } /////////////////////// //for(int i=1;i<=n;i++) //{ // printf(sma[a[%d]] = %d tot(%d) = %d ,i,sma[a[i]],a[i],tot[a[i]]); //} /////////////////////// for(int i=1;i<=n;i++) { int tmp = tot[a[i]]-sma[a[i]];/*a[i]之后比a[i]小的个数*/ ans+=(long long )tmp*(i-1-sma[a[i]])+(long long)sma[a[i]]*(n-i-tmp); } printf(%lld ,ans); } return 0; }
标程
// LA4329 Ping pong // Rujia Liu #include#include using namespace std; //inline int lowbit(int x) { return x&(x^(x-1)); } inline int lowbit(int x) { return x&-x; } struct FenwickTree { int n; vector C; void resize(int n) { this->n = n; C.resize(n); } void clear() { fill(C.begin(), C.end(), 0); } // A[1]+A[2]+...+A[x] (x<=n) int sum(int x) { int ret = 0; while(x > 0) { ret += C[x]; x -= lowbit(x); } return ret; } // A[x] += d (1<=x<=n) void add(int x, int d) { while(x <= n) { C[x] += d; x += lowbit(x); } } }; const int maxn = 20000 + 5; int n, a[maxn], c[maxn], d[maxn]; FenwickTree f; int main() { freopen(la4329.txt,r,stdin); int T; scanf(%d, &T); while(T--) { scanf(%d, &n); int maxa = 0; for(int i = 1; i <= n; i++) { scanf(%d, &a[i]); maxa = max(maxa, a[i]); } f.resize(maxa); f.clear(); for(int i = 1; i <= n; i++) { f.add(a[i], 1); c[i] = f.sum(a[i]-1); } f.clear(); for(int i = n; i >= 1; i--) { f.add(a[i], 1); d[i] = f.sum(a[i]-1); } long long ans = 0; for(int i = 1; i <= n; i++) ans += (long long)c[i]*(n-i-d[i]) + (long long)(i-c[i]-1)*d[i]; printf(%lld , ans); } return 0; }