T1
Desctription
一队勇士正在向你进攻，每名勇士都有一个战斗值$a_i$。但是这队勇士却有一个致命弱点，如果存在$i$<$j$<$k$使得$a_i$>$a_j$>$a_k$，则会影响他们整体的战斗力。我们将这样的一组(i,j,k)称为这队勇士的一个弱点。请求出这队勇士的弱点数目。
输入文件：$weakness.in$
输入的第一行是一个整数n，表示勇士的数目。
接下来一行包括n个整数，表示每个勇士的战斗值$a_i$
Output
输入文件：$weakness.out$
输出为一行，包含一个整数。表示这队勇士的弱点数目。
Anlysis
这一道题很明显的就是一个逆序对数的题目，求每一个数和前面的数可以组成多少逆序对数，和后面可以组成多少逆序对数，然后乘起来，用树状数组来进行计算就可以了。
Codes
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<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) x&(-x)
#define maxn 1000000
using namespace std;
int N,a[maxn+5];
int dat[maxn+5],dat2[maxn+5];
int par[maxn+5],par2[maxn+5];
int limnum=0;
long long ans=0;
inline void read(int &x){
x=0;int sign=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')sign=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
x*=sign;
}
void upd(int x,int d[]){
while(x<=limnum){
d[x]++;
x+=lowbit(x);
}
}
long long sum(int x,int d[]){
int res=0;
while(x>0){
res+=d[x];
x-=lowbit(x);
}
return res;
}
int main(){
freopen("weakness.in","r",stdin);
freopen("weakness.out","w",stdout);
read(N);
for(int i=1;i<=N;i++){
read(a[i]);
if(a[i]>limnum)limnum=a[i];
}
for(int i=1;i<=N;i++){
upd(a[i],dat);
par[i]=sum(limnum,dat)-sum(a[i],dat);
upd(a[N-i+1],dat2);
par2[N-i+1]=sum(a[N-i+1]-1,dat2);
}
for(int i=1;i<=N;i++){
ans+=(par[i]*par2[i]);
}
printf("%lld",ans);
return 0;
}
|