小大中+小中大= ?
#include <cstdio> #include <cstring> const int MAXN = 100000 + 1234; const int mod = 100000007; int n; long long tree[MAXN]; long long ans[MAXN]; int a[MAXN]; inline int Lowbit(int x) { return x&(-x); } void Update(int x, long long val) { for(int i = x; i > 0; i-=Lowbit(i)) { tree[i]+=val; tree[i] %= mod; } } long long Getsum(int x) { long long temp = 0; for(int i = x; i <= n; i+=Lowbit(i)) temp+= tree[i]; temp %= mod; return temp; } void Update2(int x, long long val) { for(int i = x; i <= n; i+=Lowbit(i)) { tree[i]+=val; tree[i] %= mod; } } long long Getsum2(int x) { long long temp = 0; for(int i = x; i > 0; i-=Lowbit(i)) temp+= tree[i]; temp %= mod; return temp; } int main() { int T,cas=1; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); long long sum = 0; memset(tree, 0, sizeof(tree)); for(int i = n; i >= 1; i--) { ans[i] = Getsum(a[i]); if(ans[i] == 2) sum += 1; else { sum += (ans[i] - 1) * ans[i] / 2; } sum = sum % mod; Update(a[i], 1); //printf("sum=%d\n", sum); } // printf("sum=%d\n", sum); memset(tree, 0, sizeof(tree)); long long sum2 = 0; for(int i = 1; i <= n; i++) { sum2 += ans[i] * Getsum2(a[i]); sum2 %= mod; Update2(a[i], 1); //printf("sum2=%d\n",sum2); } long long tans = ((sum - sum2) % mod + mod) % mod; printf("Case #%d: %I64d\n",cas++, tans); } return 0; }