hdu2492 Ping pong

题意:一群乒乓爱好者居住在一条直线上,如果两个人想打比赛需要一个裁判,裁判的 位置 必须在两者之间 ,裁判的能力也必须不大于 参赛者最大的,不小于参赛者最小的

白皮的题解:考虑 第 i 个 为裁判 的情况 如果 左边 比 a[i] 小的 人数 为 c[i],则 有  i-c[i]-1 个人 比 a[i] 大,同样 右边 比 a[i] 小 的人数为 d[i] ,则比a[i]大的人为 n - i - d[i];

则方案 为 d[i]*( i - c[i] - 1 ) + c[i] * (n - i - d[i])

用 x[ a[i] ] 表示 比 a[i] 小的个数,这就涉及到了 树状数组

代码……

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <string>
using namespace std;
typedef long long ll;
const double ESP = 10e-;
const int MOD = ;
typedef long long LL;
const int MAXN = + ;
const int MAXA = + ;
int bit[MAXA];
int c[MAXN];
int d[MAXN];
int arr[MAXN]; int sum(int i){
int s = ;
while(i > ){
s += bit[i];
i -= i&-i;
}
return s;
} void add(int i,int x){
while(i < MAXA){
bit[i] += x;
i += i&-i;
}
}
int main(){
// freopen("input.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
memset(bit,,sizeof(bit));
memset(c,,sizeof(c));
memset(d,,sizeof(d));
for(int i = ;i <= n;i++){
scanf("%d",&arr[i]);
c[i] = sum(arr[i]);
add(arr[i],);
}
memset(bit,,sizeof(bit));
for(int i = n;i > ;i--){
d[i] = sum(arr[i]-);
add(arr[i],);
}
LL ans = ;
for(int i = ;i <= n;i++){
ans += c[i]*(n-i-d[i]) + d[i]*(i-c[i]-);
}
printf("%I64d\n",ans);
}
return ;
}
05-11 09:32