Algorithm
Problem link- https://www.spoj.com/problems/DCEPC206/
DCEPC206 - Its a Murder!
Once detective Saikat was solving a murder case. While going to the crime scene he took the stairs and saw that a number is written on every stair. He found it suspicious and decides to remember all the numbers that he has seen till now. While remembering the numbers he found that he can find some pattern in those numbers. So he decides that for each number on the stairs he will note down the sum of all the numbers previously seen on the stairs which are smaller than the present number. Calculate the sum of all the numbers written on his notes diary.
Input
First line gives T, number of test cases.
2T lines follow.
First line gives you the number of stairs N
Next line gives you N numbers written on the stairs.
Output
For each test case output one line giving the final sum for each test case.
Constraints
T<=10
1<=N<=10^5
All numbers will be between 0 and 10^6.
Example
Input: 1
5
1 5 3 6 4
Output: 15
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = (int)1e6+5;
ll BIT[MAXN];
void update(int idx, int val){
while(idx <= 1000000){
BIT[idx] += val;
idx += idx&-idx;
}
}
ll query(int idx){
ll sum = 0;
while(idx > 0){
sum += BIT[idx];
idx -= idx&-idx;
}
return sum;
}
int main(){
io;
int t;
cin >> t;
while(t--){
memset(BIT, 0, sizeof BIT);
int n;
cin >> n;
ll ans = 0;
for(int i = 0;i < n; i++){
int foo;
cin >> foo;
if(foo > 0){
ans += query(foo-1);
update(foo, foo);
}
}
cout << ans << endl;
}
return 0;
}Input
5
1 5 3 6 4
Output
Demonstration
SPOJ Solution-Its a Murder!-Solution in C, C++, Java, Python