P1908 逆序对

冷不防 2024-04-20 10:33 70阅读 0赞

##  ##

P1908 逆序对

### 题意： ###

> 给你一个长度为 $ n $ 的数组，求其中的逆序对数量。

### 解法： ###

> 数据范围很大 $ (n \\leq 5 \\times 10^5) $ ，所以考虑离散化+树状数组。

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> using namespace std; #define LL long long const int N = 5e5 + 100; struct Node { int val,pos; } a[N]; int tree[N],tag[N],n; LL ans; inline int lowbit(int x) { return x & (-x); } inline void add(int x) { for(; x <= n ; x += lowbit(x)) tree[x]++; return; } inline int query(int x) { int ans = 0; for(; x ; x -= lowbit(x)) ans += tree[x]; return ans; } inline bool cmp(Node a,Node b) { if(a.val == b.val) return a.pos < b.pos; return a.val < b.val; } inline int read() { int x = 0,f = 1; char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') f=-1; ch=getchar();} while(ch >= '0' && ch <= '9') {x = (x<<1) + (x<<3) + (ch^48);ch = getchar();} return x * f; } int main() { n = read(); for(int i = 1 ; i <= n ; i++) { a[i].val = read(); a[i].pos = i; } sort(a + 1,a + n + 1,cmp); for(int i = 1 ; i <= n ; i++) tag[a[i].pos] = i; for(int i = n ; i >= 1 ; i--) { ans += query(tag[i]); add(tag[i]); } printf("%lld \n",ans); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11469774.html

发表评论取消回复

表情：

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

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

相关阅读

相关 P1908 逆序对

P1908 逆序对题意： > 给你一个长度为 $ n $ 的数组，求其中的逆序对数量。解法： > 数据范围很大 $ (n \\leq 5 \\t...

冷不防/ 2024年04月20日 10:33/ 0 赞/ 71 阅读

相关 P1908 逆序对 (归并排序实现)

题目描述 > 猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之

朱雀/ 2023年05月29日 11:56/ 0 赞/ 232 阅读

相关求逆序对

题型: 编程题语言: 不限定 Description 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列

ゞ浴缸里的玫瑰/ 2023年02月11日 03:21/ 0 赞/ 17 阅读

相关 P3531 [POI2012]LIT-Letters（求逆序对）

题目传送门：[https://www.luogu.com.cn/problem/P3531][https_www.luogu.com.cn_problem_P3531] 题

布满荆棘的人生/ 2022年12月31日 01:26/ 0 赞/ 118 阅读

相关 1013 逆序对

Description 给定一个长度为N的int型数组a[0,1,2,...N-1], 请计算逆序对个数.当i<j且a[i]>a[j], 则称a[i]与a[j]是一对

墨蓝/ 2022年09月11日 15:21/ 0 赞/ 174 阅读

相关洛谷P1908 逆序对

题目描述猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“

客官°小女子只卖身不卖艺/ 2022年05月30日 06:44/ 0 赞/ 206 阅读

相关逆序对数目 java

逆序对数目 java 题目描述：设A\[1…n\]是一个包含n个两两不同数的数组。若在i<j的情况下，有A\[i\]>A\[j\]，则(i,j)称为A中的一个逆序对

偏执的太偏执、/ 2022年05月11日 14:33/ 0 赞/ 223 阅读

相关排序---逆序对

题目：[https://www.acwing.com/problem/content/description/109/][https_www.acwing.com_proble

喜欢ヅ旅行/ 2022年02月23日 09:34/ 0 赞/ 230 阅读

相关逆序对个数

题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的

蔚落/ 2022年01月30日 08:21/ 0 赞/ 246 阅读

相关 P1908-逆序对

1 include <bits/stdc++.h> 2 using namespace std; 3 define _for(i,a,b) for(

喜欢ヅ旅行/ 2021年11月09日 07:40/ 0 赞/ 329 阅读