0%

HDU-2492 Ping pong

题目链接

思路

​ 本题的关键就是求第i个点的左边和右边有多少个小于i点的等级的点,分别用min_l[]和min_r[]来存储。
等级范围是$1\le a_i \le 10^5$,所以我们在对a[]数组正向遍历时直接用BIT[]数组存储某个等级的是否出现过,出现过的标记为1,否则为0,这样这个题就变成了一个区间求和的问题。
既然是区间求和问题,那么用二叉索引树(树状数组,BIT)和线段树都可以解决。

树状数组解

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
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <string.h>
using namespace std;
const int max_a=1e5+10;
const int max_N=2e4+10;
#define LL long long
int a[max_N];
int BIT[max_a];
int min_l[max_N];
int min_r[max_N];
LL lowbit(int x){
return x&(-x);
}
void add(int x,int d){
while(x<=max_a){
BIT[x]+=d;
x+=lowbit(x);
}
}
LL sum(int x){
LL ret=0;
while(x>0){
ret+=BIT[x];
x-=lowbit(x);
}
return ret;
}
int main(){
int T,N;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%d",&a[i]);
}
memset(BIT,0,sizeof BIT);
for(int i=1;i<=N;i++){
min_l[i]=sum(a[i]-1);
add(a[i],1);
}
memset(BIT,0,sizeof BIT);
for(int i=N;i>=1;i--){
min_r[i]=sum(a[i]-1);
add(a[i],1);
}
LL ans=0;
for(int i=2;i<N;i++){
ans+=(min_l[i]*(N-i-min_r[i])+(i-min_l[i]-1)*min_r[i]);
}
printf("%lld\n",ans);
}

}

线段树解

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 <iostream>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <string.h>
using namespace std;
#define LL long long
#define lc (o<<1)
#define rc ((o<<1)|1)
const int maxn=2e4+10;
const int maxm=1e5+10;

int a[maxn];
int C[maxm<<2];
int min_l[maxn];
int min_r[maxn];
void Build(int o,int L,int R){
C[o]=0;
if(L==R) return ;
int mid=L+((R-L)>>1);
Build(lc,L,mid);
Build(rc,mid+1,R);
}
void Update(int o,int L,int R,int x){
if(L==R){
C[o]++;
return;
}
int mid=L+((R-L)>>1);
if(x<=mid) Update(lc,L,mid,x);
else Update(rc,mid+1,R,x);
C[o]=C[lc]+C[rc];
}
int Query(int o,int L,int R,int ql,int qr){
if(ql<=L && qr>=R) return C[o];
int mid=L+((R-L)>>1);
int ret=0;
if(ql<=mid) ret+=Query(lc,L,mid,ql,qr);//ql<=mid
if(qr>mid) ret+=Query(rc,mid+1,R,ql,qr);
return ret;
}
int main(){
int T,N;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(int i=1;i<=N;i++) scanf("%d",&a[i]);
Build(1,1,maxm);
for(int i=1;i<N;i++){
min_l[i]=Query(1,1,maxm,1,a[i]);
Update(1,1,maxm,a[i]);
}
Build(1,1,maxm);
for(int i=N;i>=1;i--){
min_r[i]=Query(1,1,maxm,1,a[i]);
Update(1,1,maxm,a[i]);
}
LL ans=0;
for(int i=2;i<N;i++){
ans+=(LL)(min_l[i]*(N-i-min_r[i])+(LL)(i-min_l[i]-1)*min_r[i]);
}
printf("%lld\n",ans);
}
return 0;
}

参考了

https://blog.csdn.net/zhouchenghao123/article/details/84344499

https://blog.csdn.net/SCNU_Jiechao/article/details/8469470

如果对您有帮助,请我喝杯奶茶?