网店美工的技能要求/seo网站优化多少钱

　　本来是想练一下线段树的，看到这题逆序对，不用下树状数组都可惜了啊！

　　用树状数组很简单，就中间有一个细节，因为数组中是有0的，在我进行区间求和的时候，判断条件是x>=0,而lowb(0)==0，这就会使程序陷入死循环！注意！

 

　　因为这题是求数组a位置i右边比a[i]大的数的个数，按照网上的说法（http://apps.hi.baidu.com/share/detail/16352612）：

　　如果要求b[i] = 位置i左边大于等于a[i]的数的个数呢？当然我们可以离散化时倒过来编号，但有没有更直接的方法呢?答案是有。几乎所有教程上树状数组的三个函数都是那样写的，但我们可以想想问啥修改就是x不断增加，求和就是x不断减少，我们是否可以反过来呢，答案是肯定的。代码如下：

 

void Update(int x, int c)
{
int i;
for (i = x; i >= 1; i -= Lowbit(i))
{
tree[i] += c;
}
}

int Getsum(int x)
{
int i;
int temp(0);
for (i = x; i < maxn; i += Lowbit(i))
{
temp += tree[i];
}
return temp;
}

　　今天我写程序运行了一下，感觉这个观点并不是对的。我们应该还记得树状数组那张标志性的图（可以去看看）：

  　　树状数组之所以快，是因为它的结构很好，它的C[4]表示前4个数，C[8]表示前8个数……再写博客的时候，突然觉得是对的。它的修改时往下修改，每一个比它小的数都会有+1的，也只有比它小的才有+1。而求和的话是看比这个数大的数在前面出现几次，在修改操作中已经确定，这个是符合前面的逻辑的！

 

　　带上1094的树状数组代码吧： 

#include <iostream>
#include <cstdio>
using namespace std;
#define min(c,d) (c>d?d:c)

int n,S,mmin;
int C[5005];
int a[5005];

int lowb(int t)
{
return t&(-t);
}

void up(int i,int val)
{
for(;i<=n;i+=lowb(i))
{
C[i] += val;
}
}

int down(int i)
{
int sum = 0;
for(;i>0;i-=lowb(i))
{
sum += C[i];
}
return sum;
}

void Init()
{
int i;
S = 0;
memset(C,0,sizeof(C));
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i] += 1; //因为有0的存在，在求和的时候判断条件是i>=0，会陷入死循环，所以加1
}

}

void Play()
{
int i;
for(i=n;i>=1;i--)
{
S += down(a[i]);
up(a[i],1);
}

mmin = S;
for(i=1;i<=n;i++)
{
S = S - (a[i] - 1) //移动前左边比a[i]小的数
+ (n - a[i]); //移动后右边比a[i]大的数
mmin = min(mmin,S);
}
}

void print()
{
printf("%d\n",mmin);
}

int main()
{
while(scanf("%d",&n)!=EOF)
{
Init();
Play();
print();
}
}

　　线段树代码：

#include <iostream>
#include <cstdio>
using namespace std;

#define min(c,d) (c>d?d:c)
const long maxn = 5005;

int n;
int mmin;
int a[maxn];

struct node
{
int l;
int r;
int sum;
}inv[maxn*4];

void CreateTree(int ini,int a,int b)
{
inv[ini].l = a;
inv[ini].r = b;
inv[ini].sum = 0;

if(a == b)
return;

int mid = (a+b) >> 1;
CreateTree(ini*2,a,mid);
CreateTree(ini*2+1,mid+1,b);
}

void Updata(int ini,int x,int val)
{
if(inv[ini].l == x && inv[ini].r == x)
{
inv[ini].sum += val;
return;
}

int mid = (inv[ini].l + inv[ini].r) >> 1;

if(x <= mid)
{
Updata(ini*2,x,val);
inv[ini].sum += val;
}
else
{
Updata(ini*2+1,x,val);
inv[ini].sum += val;
}
}

int Find(int ini,int x,int y)
{
if(inv[ini].l == x && inv[ini].r == y)
{
return inv[ini].sum;
}

int mid = (inv[ini].l + inv[ini].r) >> 1;

if(y <= mid)
{
return Find(ini*2,x,y);
}
else if(x > mid)
{
return Find(ini*2+1,x,y);
}
else
{
return Find(ini*2,x,mid) + Find(ini*2+1,mid+1,y);
}
}
void Init()
{
int i;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
}

void Play()
{
int i;
int sum = 0;
CreateTree(1,0,n);
for(i=n-1;i>=0;i--)
{
sum += Find(1,0,a[i]);
Updata(1,a[i],1);
}

mmin = sum;
for(i=0;i<n;i++)
{
sum = sum - a[i] + (n-a[i]-1);
mmin = min(mmin,sum);
}
}

void print()
{
printf("%d\n",mmin);
}

int main()
{
while(scanf("%d",&n)!=EOF)
{
Init();
Play();
print();
}
}