POJ2299 Ultra-QuickSort（离散化 树状数组）
source link: https://arminli.com/poj2299/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
POJ2299 Ultra-QuickSort（离散化 树状数组）
February 14, 2016
题意：求 n 个数的逆序对数。
思路：首先 n 只有 500000，然而数字范围非常大，将输入离散化成 1~500000 范围的数，离散化后的数组为 li[]，li[1]为第一个进入数，将 li[i]对应的树状数组更新为 1，判断 1~li[i]间有几个数已进入（有为 1，无为 0，就是 sum），i-sum(li[i])就是逆序对数。
#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[500005];
int li[500005];
struct node{
int order;
int num;
}N[500005];
bool cmp(node x, node y){
return x.num<y.num;
}
int lowbit(int x){
return x&(-x);
}
void add(int pos , int num){
while(pos <= n){
a[pos] += num;
pos += lowbit(pos);
}
}
int sum(int n){
int sum = 0;
while(n > 0){
sum += a[n];
n -= lowbit(n);
}
return sum;
}
int main(){
//freopen("a.txt", "r", stdin);
while(scanf("%d", &n) != EOF && n){
for(int i = 1; i <= n; i++){
scanf("%d", &N[i].num);
N[i].order = i;
}
sort(N+1, N+n+1, cmp);
for(int i = 1; i <= n; i++)
li[N[i].order] = i;
memset(a, 0, sizeof(a));
long long ans = 0;
for(int i = 1; i <= n; i++){
add(li[i], 1);
ans += i-sum(li[i]);
}
cout << ans << endl;
}
return 0;
}
Recommend
-
65
-
21
简介 树状数组和下面的线段树可是亲兄弟了，但他俩毕竟还有一些区别： 树状数组能有的操作，线段树一定有； 线段树有的操作，树状数组不一定有。 这么看来选择线段树 不就 「得天下了」...
-
37
学习了一周的线段树和树状数组，深深地体会到了这每种操作几乎都是 \(O(logN)\) 级别的数据结构的美，但是做起题来还是相当痛苦的（特别是一开始只会模板的时候，很难灵活运用线段树的性质）。还好有雨巨大神带入门，视频讲...
-
10
【小算法】将数组处理成树状结构 2021年4月8日 96次浏览 将数组处理成树状结构，也是在工作中经常遇到的，今天就和大家一起分享一下思路和方法。 如下代码，处理成树状结构，要求程序具有容错能力，也就是可以判断输...
-
10
POJ2155 Matrix（二维树状数组）February 15, 2016题目链接 题意：矩阵默认全为 0，操作是对输入的两个点构成的矩形内所有元素取反，询问是问某个点是 1 还是 0。 二维树状数组解...
-
10
NEU1686 Sort（DP 树状数组）February 15, 2016题目链接 题意：题目比较难懂，复制讨论版的内容，为第二个样例的分析： As we know, there are 27 kinds of p...
-
16
Armin's BlogNEU1438 Car race game（树状数组）February 17, 2016题目链接 题意：在一维坐标轴上给出 n 个人的起点和速度，问一...
-
4
UESTC1217 The Battle of Chibi（DP 树状数组）February 15, 2016题目链接 题意：从 n 个数中找出 m 个数，满足严格递增，问能找出几个序列。 思路：dp[i][j]表示以...
-
19
Armin's BlogPOJ1195 Mobile phones（二维树状数组）February 15, 2016题目链接 题意：给定矩阵，对点更新，询问给两个点，求这两个点构成矩形内元素...
-
14
POJ2481 Cows（树状数组）March 05, 2016题目链接 题意：n 个牛，每个牛在一条数轴上控制的范围是[a, b]，如果牛 1 控制的范围完全包括了牛 2（除了范围完全相等的情况），那么称牛 1 比...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK