codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <cstdio> #include <cstring> using namespace std; typedef long long LL; const int MAXN = 20005; const int MAXX = 100000; int BIT[2][MAXX + 5]; // index 0 untuk kiri, 1 untuk kanan int n,tc; int arr[MAXN]; void Update(int id,int x,int val){ for( ; x <= MAXX ; x += x & -x) BIT[id][x] += val; } int Query(int id,int x){ int res = 0; for( ; x > 0 ; x -= x & -x) res += BIT[id][x]; return res; } int main(){ scanf("%d",&tc); while(tc--){ memset(BIT,0,sizeof BIT); scanf("%d",&n); for(int i = 0 ; i < n ; i++){ scanf("%d",&arr[i]); Update(1, arr[i], 1); } LL ans = 0; for(int i = 0 ; i < n ; i++){ Update(1, arr[i], -1); int val1 = Query(0,arr[i] - 1); int val2 = Query(0,MAXX) - Query(0,arr[i]); int val3 = Query(1,arr[i] - 1); int val4 = Query(1,MAXX) - Query(1,arr[i]); ans += val1 * val4; ans += val2 * val3; Update(0, arr[i], 1); } printf("%lld\n",ans); } return 0; }
Private
[
?
]
Run code
Submit