树状数组

#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#define N 110000
#define mol 99999997
#define ll long long
using namespace std;

struct node
{
int num,xuhao;
}a[N],b[N];

int c[N],n,d[N];
ll ans;

bool cmp(node x,node y)
{
return x.num<y.num;
}

int lowbit(int x)
{
return x&(x^(x-1));
}

int sum(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x-=lowbit(x);
}
return ans;
}

void update1(int x,int d)
{
while(x<=n)
{
c[x]+=d;
x+=lowbit(x);
}
}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].num);
a[i].xuhao=i;
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&b[i].num);
b[i].xuhao=i;
}
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++)
d[a[i].xuhao]=b[i].xuhao;
for(int i=1;i<=n;i++)
{
update1(d[i],1);
ans+=i-sum(d[i]);
}
printf("%lld\n",ans%mol);
return 0;
}

2 条评论

  • @ 2016-11-18 21:33:51

    这似乎是贪心吧 ?
    (a-b)^2=a^2-2ab+b^2,最小化ab即可

  • @ 2016-07-16 15:27:14

    树状数组是什么?

    • @ 2016-08-27 19:21:30

      类似线段树,解决区间问题的...

  • 1

信息

ID
1842
难度
7
分类
(无)
标签
递交数
5085
已通过
1102
通过率
22%
被复制
10
上传者