SPOJ DCEPC206

Link : DCEPC206

Category : Segment Tree

Code:

	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <queue>
	#include <stack>
	#include <map>
	#include <ctime>
	#include <utility>
	#include <climits>
	#include <cfloat>
	#include <cassert>
	using namespace std;
	#define readint(n) scanf("%d",&n);
	#define readll(n) scanf("%lld",&n);
	#define readchar(n) scanf("%c",&n);
	#define readf(n) scanf("%f",&n);
	#define readd(n) scanf("%lf",&n);
	#define readstr(s) scanf("%s",&s);
	#define init(mem) memset(mem,0,sizeof(mem));
	int pabs(int n){return (n>0?n:-n);}
	int hcf(int a,int b){if(b==0){return a;} else{return hcf(b,a%b);}}
	long long int mem[4000004];
	int n;
	void update(int ind,int l,int u,int v){
	if(v<l or v>u)return;
	if(l==u){
	mem[ind]+=l;
	return;
	}
	int mid=(l+u)/2;
	update(2*ind,l,mid,v);
	update(2*ind+1,mid+1,u,v);
	mem[ind]=(mem[ind*2]+mem[2*ind+1]);
	}
	long long int query(int ind,int l,int u,int x,int y){
	if(u<x or l>y){
	return 0;
	}
	if(x<=l and u<=y){
	return mem[ind];
	}
	int mid=(l+u)/2;
	return query(2*ind,l,mid,x,y)+query(2*ind+1,mid+1,u,x,y);
	}
	int main(){
	int t,v;
	readint(t);
	while(t--){
	init(mem);
	readint(n);
	long long int sum=0;
	for(int i=1;i<=n;i++){
	readint(v);
	sum+=query(1,1,1000001,1,v-1);
	update(1,1,1000001,v);
	}
	printf("%lld\n",sum);
	}
	return 0;
	}

view raw DCEPC206.cpp hosted with ❤ by GitHub