题目链接：http://poj.org/problem?id=2299
归并排序解法链接：http://blog.csdn.net/lyy289065406/article/details/6647346
然后是自己写的线段树：
注意点在代码中。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r//2. 这一块的l,1分清楚 const int maxn=500005; struct M
{
int x;
int id;
}m[maxn]; int b[maxn];
struct Tree
{
int l,r,sum;
}tree[maxn*4];// 1.此处的结点maxn*4? 开maxn*2会RE int cmp(struct M a,struct M b)
{
return a.x<b.x;
}
void Pushup(int rt)
{
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
} void build(int rt,int l,int r)
{
if(l==r) {tree[rt].sum=0;return;}
else
{
int m=(l+r)>>1;
build(lson);
build(rson);
}
Pushup(rt);
//tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void update(int p,int add,int rt,int l,int r)
{
if(p>r) return;
if(l==r)
{
tree[rt].sum+=add;
return;
}
else
{
int m=(l+r)>>1;
if(p<=m) update(p,add,lson);//3. 要p的作用哪。只更新一半 。因为下面有Pushup
else update(p,add,rson);
}
Pushup(rt);
}
int query(int a,int b,int rt,int l,int r)
{
int ans=0;
if(a<=l&&b>=r)
{
return tree[rt].sum;
}
else
{
int m=(l+r)>>1;
if(a<=m)
ans+=query(a,b,lson);
if(b>m) //4. 这地方是r>m果断而不是r>=m
ans+=query(a,b,rson);
}
return ans;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(!n) break; for(int i=1;i<=n;i++)
{
scanf("%d",&m[i].x);
m[i].id=i;
} sort(m+1,m+1+n,cmp); //离散化
b[m[1].id]=1;
for(int i=2;i<=n;i++)
{
if(m[i].x==m[i-1].x)
b[m[i].id]=b[m[i-1].id];
else b[m[i].id]=i;
} build(1,1,n); long long ans=0;
for(int i=1;i<=n;i++)
{
ans+=query(b[i]+1,n,1,1,n);
update(b[i],1,1,1,n);
}
printf("%lld\n",ans); }
return 0;
}
//还有不懂的时候调试一下，出现奇怪的地方一般是自己错了。 或者模板敲错。