http://acm.hdu.edu.cn/showproblem.php?pid=2689
C++版本一
线段树
/*
*@Author: STZG
*@Language: C++
*/
//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
ll tree[N<<2];
void pushup(int rt){
tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void updata(int l,int r,int rt,int L,int C){
if(l==r){
tree[rt]+=C;
return;
}
int mid=(l+r)>>1;
if(L<=mid)updata(l,mid,rt<<1,L,C);
else updata(mid+1,r,rt<<1|1,L,C);
pushup(rt);
}
ll query(int l,int r,int rt,int L,int R){
if(l>=L&&r<=R){
return tree[rt];
}
int mid=(l+r)>>1;
ll res=0;
if(L<=mid)res+=query(l,mid,rt<<1,L,R);
if(R>mid)res+=query(mid+1,r,rt<<1|1,L,R);
return res;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
while(~scanf("%d",&n)){
memset(tree,0,sizeof(tree));
ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&t);
ans+=query(1,n,1,t+1,n);
updata(1,n,1,t,1);
}
cout << ans << endl;
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
树状数组
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
const int N=1001;
int n;
int num[N];
int c[N];
struct node
{
int x;
int id;
}q[N] ;
bool cmp(node a,node b)
{
return a.x<b.x;
}
int lowbit(int x)
{
return x&(-x);
}
int getsum(int x)
{
int s=0;
while(x>0)
{
s+=c[x];
x-=lowbit(x);
}
return s;
}
void add(int x,int y)
{
while(x<=n)
{
c[x]+=y;
x+=lowbit(x);
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(c,0,sizeof(c));
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++)
{
scanf("%d",&q[i].x);
q[i].id=i;
}
sort(q+1,q+1+n,cmp);
for(int i=1;i<=n;i++)
{
num[q[i].id]=i;
}
int sum = 0;
for(int i=1;i<=n;i++)
{
add(num[i],1);
sum+=getsum(n)-getsum(num[i]);
}
printf("%d\n",sum);
}
return 0;
}