简单的逆序对
可以用树状数组搞
就是插入时,找前面比他大的和
插入时弄一个桶,记下有多少个数
然后对后面的进行区间求和,这个可以用树状数组搞
最后求一个总和1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,a[49999],sum[4999999],max1;
int add(int x,int w)
{
for(int i=x;i>0;i-=i&(-i))
sum[i]+=w;
}
int chaxun(int x)
{
int ans=0;
for(int i=x;i<=max1;i+=i&(-i))
ans+=sum[i];
return ans;
}
int main()
{
int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
add(a[i],1);
max1=max(a[i],max1);
ans+=chaxun(a[i]);
}
printf("%d",ans-n);
}
难一点的
三元逆序对
这样的话就可以枚举一个位置,找前面比他大的,和后面比他小的,乘起来,统计和
1 | #include<iostream> |
这个题有一点难度
需要你转化思想
你知道这个题就是求一个和,暴力n^2可以完成,但一定过不了
所以就需要一些优化
像上面这样,从小到大枚举v,之前的一定比他小直接统计就行了,但有个很麻烦的绝对值。。。
那你就维护两个和,一个是小的一个是大的,这个可以轻易的用树状数组维护,这样就把绝对值去了
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n;
ll s,ans;
struct st{
ll v,x;
}p[299099];
ll maxn,sum[299099],tot[299099],sum2[299099],tot2[290999];
ll cmp(const st &a,const st &b)
{
if(a.v<b.v||a.v==b.v&&a.x<b.x)
return 1;
return 0;
}
ll add(ll x,ll w,ll w2)//前缀
{
for(ll i=x;i<=maxn;i+=i&-i)
sum[i]+=w,tot[i]+=w2;
}
ll cx(ll x){
ans=0,s=0;
for(ll i=x;i>0;i-=i&-i)
ans+=sum[i],s+=tot[i];
}
ll add2(ll x,ll w,ll w2)//后缀
{
for(ll i=x;i>0;i-=i&-i)
sum2[i]+=w,tot2[i]+=w2;
}
ll cx2(ll x){
ans=0,s=0;
for(ll i=x+1;i<=maxn;i+=i&-i)
ans+=sum2[i],s+=tot2[i];
}
int main(){
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld%lld",&p[i].v,&p[i].x),maxn=max(maxn,p[i].x);;
sort(p+1,p+n+1,cmp);
ll ss=0;
for(ll i=1;i<=n;i++)
{
ll sss=0;
add(p[i].x,1,p[i].x);
add2(p[i].x,1,p[i].x);
cx(p[i].x);
sss+=(ans*p[i].x-s);
cx2(p[i].x);
sss+=(s-ans*p[i].x);
sss*=p[i].v;
ss+=sss;
}
printf("%lld",ss);
}