重工电子论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 54|回复: 0

[其他] 【数状数组求逆序对】

[复制链接]

6

主题

6

帖子

26

积分

新手上路

Rank: 1

积分
26
发表于 2018-6-14 14:01:04 | 显示全部楼层 |阅读模式
[AppleScript] syntaxhighlighter_viewsource syntaxhighlighter_copycode
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int Sum[1000],A[1000];
int lowbit(int x){return x&-x;}
void add(int x){for(int i=x;i<=n;i+=lowbit(i))Sum[i]+=1;}
int getsum(int x){int tot=0;for(int i=x;i;i-=lowbit(i))tot+=Sum[i];return tot;}
int main(){
	int ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&A[i]);
	}
	for(int i=1;i<=n;i++){
		ans+=(getsum(n)-getsum(A[i]));
		add(A[i]);
	}
	printf("%d",ans);
}
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|cqutlab ( 渝ICP备15004556号

GMT+8, 2018-8-19 07:29 , Processed in 0.089478 second(s), 26 queries .

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表