hihoCoder 1524 : 逆序对（树状数组）

客官°小女子只卖身不卖艺 2024-02-17 22:15 69阅读 0赞

#### \#1524 : 逆序对 ####

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

<table></table>

#### 描述 ####

给定一个1-N的排列A1, A2, ... AN，如果Ai和Aj满足i < j且Ai > Aj，我们就称(Ai, Aj)是一个逆序对。

求A1, A2 ... AN中所有逆序对的数目。

#### 输入 ####

第一行包含一个整数N。

第二行包含N个两两不同整数A1, A2, ... AN。(1 <= Ai <= N)

对于60%的数据 1 <= N <= 1000

对于100%的数据 1 <= N <= 100000

#### 输出 ####

一个整数代表答案

样例输入

5
    3 2 4 5 1

样例输出

5

分析：树状数组求逆序对

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long LL;
    const int maxn=1e5+10;
    LL a[maxn];
    LL C[maxn];
    int n;
    
    int lowbit(int i){
    	return i&-i;
    }
    
    LL sum(int i){
    	LL cnt=0;
    	while(i){
    		cnt+=C[i];
    		i-=lowbit(i);
    	}
    	return cnt;
    }
    
    void update(int i){
    	while(i<=n){
    		C[i]++;
    		i+=lowbit(i);
    	}
    }
    
    int main(){
    	while(scanf("%d",&n)==1){
    		for(int i=1;i<=n;i++){
    			scanf("%d",&a[i]);
    		}
    		
    		memset(C,0,sizeof(C));
    		LL ans=0;
    		for(int i=n;i>=1;i--){
    			update(a[i]);
    			ans+=sum(a[i]-1);
    		}
    		
    		printf("%lld\n",ans);
    	} 
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，69人围观）

还没有评论，来说两句吧...

相关阅读

相关 hihoCoder 1524 : 逆序对（树状数组）

\1524 : 逆序对时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB <table></table> 描述给定一个1-N的

客官°小女子只卖身不卖艺/ 2024年02月17日 22:15/ 0 赞/ 70 阅读

相关数组中的逆序对

一、题目在数组中，如果前一个数字大于后一个数字，则两个数字组成一个逆序对。输入一个数组，求逆序对总数。二、分析（1）暴力求解：顺序扫描这个数组，每扫描到一个数字，如

超、凢脫俗/ 2023年11月20日 07:37/ 0 赞/ 260 阅读

相关 WUST 1954 小朋友排队（树状数组+求两次逆序对）

1954: 小朋友排队 Time Limit: 1 Sec Memory Limit: 256 MB 64bit IO Format: %lld Submitted:

末蓝、/ 2022年06月11日 07:16/ 0 赞/ 170 阅读

相关求逆序对数的方法(归并排序 and 树状数组)

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1

水深无声/ 2022年05月29日 06:24/ 0 赞/ 212 阅读

相关数组中的逆序对

![这里写图片描述][70] public class Solution { public int count=0; //方法一、暴力

系统管理员/ 2022年05月25日 10:38/ 0 赞/ 211 阅读

相关数组中的逆序对

写在前面 > 题目：剑指offer-数组中的逆序对 > 考点：归并排序。知识点归并排序要求 > 在数组中的两个数字，如果前面一个数字大于

约定不等于承诺〃/ 2022年05月18日 07:15/ 0 赞/ 193 阅读

相关逆序对——浅谈一维树状数组 & 离散化

计算逆序对问题 BZOJ 1266 -------------------- 目录前言正文普通做法归并排序树状数组数组离散化 STL+

小灰灰/ 2022年04月11日 02:43/ 0 赞/ 246 阅读

相关数组中的逆序对

[数组中的逆序对][Link 1] 题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的

Myth丶恋晨/ 2022年03月25日 15:38/ 0 赞/ 216 阅读

相关数组中的逆序对

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ 题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=19][

àì夳堔傛蜴生んèń/ 2022年03月20日 03:27/ 0 赞/ 244 阅读

相关数组中的逆序对

时间限制：2秒空间限制：32768K 热度指数：259937 本题知识点：数组算法知识视频讲解题目描述在数组中的两个数字，如果前面一个数字大于后面的数

比眉伴天荒/ 2022年03月09日 10:50/ 0 赞/ 237 阅读