首页 > 代码库 > HDU2492 Ping pong
HDU2492 Ping pong
题解:
每个数,求出左右两边比这个数大的和比这个数小的,然后以每个数作为裁判,求和就行了
代码:
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=20100;const int N=100010;const int mod=1e9+7;const int INF=1e9;int a[maxn],l_num[N],r_num[N];LL L[N],R[N];int n;int lowbit(int x){return x&-x;}void add(int x,int v,int*c){ while(x<N){ c[x]+=v; x+=lowbit(x); }}LL sum(int x,int*c){ LL cnt=0; while(x){ cnt+=c[x]; x-=lowbit(x); } return cnt;}int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); CLR(l_num);CLR(r_num); for(int i=1;i<=n;i++){ L[i]=sum(a[i]-1,l_num);//左边比a[i]小 R[n+1-i]=sum(a[n+1-i]-1,r_num);//右边比a[n+1-i]小 add(a[i],1,l_num); add(a[n+1-i],1,r_num); } LL ans=0; for(int i=1;i<=n;i++){ //cout<<L[i]<<" "<<R[i]<<endl; ans+=L[i]*(n-i-R[i])+(i-1-L[i])*R[i]; } printf("%lld\n",ans); } return 0;}
HDU2492 Ping pong
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。