关于二维偏序的题

简单的逆序对
可以用树状数组搞
就是插入时,找前面比他大的和
插入时弄一个桶,记下有多少个数
然后对后面的进行区间求和,这个可以用树状数组搞
最后求一个总和

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
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
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,a[49999],sum[4999999],max1,sum2[4419999];
int add(int x,int w)
{
for(int i=x;i<=max1;i+=i&(-i))
sum[i]+=w;
}
int chaxun(int x)
{
int ans=0;
for(int i=x-1;i>0;i-=i&(-i))
ans+=sum[i];
return ans;
}
int add2(int x,int w)
{for(int i=x;i>0;i-=i&(-i))
sum2[i]+=w;
}
int chaxun2(int x)
{
int ans=0;
for(int i=x+1;i<=max1;i+=i&(-i))
ans+=sum2[i];
return ans;
}
int main()
{
long long ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);max1=max(a[i],max1); add2(a[i],1);
}




for(int i=1;i<=n;i++)
{

add(a[i],1);add2(a[i],-1);
//printf("%d %d",chaxun(a[i]),chaxun2(a[i]));
ans+=1ll*chaxun2(a[i])*chaxun(a[i]);
}
printf("%lld",ans);
}

这个题有一点难度
需要你转化思想
你知道这个题就是求一个和,暴力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);
}

最近的文章

优先队列

较简单的排队打水,合并果子。。。 合并序列这是一个堆的问题,就用stl里的优先队列完美搞掉有两个序列先sort一下在算出最小的a[1]+b[1]…..a[1]+b[n]为一组删掉+如a[i][j+1]放进去找最小的k个12345678910111213141516171819202122232425 …

于  优先队列 继续阅读
更早的文章

day6

cyclic这个题直接模拟,先把k%一下防止过大然后直接做就行了 1234567891011121314151617181920212223242526#include&lt;cstdio&gt;#include&lt;algorithm&gt;#include&lt;iostream&gt;#in …

于  2017 继续阅读