当前位置: 首页> 游戏> 单机 > 深圳网络营销推广_江西邢台网络科技_seo排名优化方式方法_做整站优化

深圳网络营销推广_江西邢台网络科技_seo排名优化方式方法_做整站优化

时间:2025/7/9 0:46:30来源:https://blog.csdn.net/rensifang/article/details/144804960 浏览次数:0次
深圳网络营销推广_江西邢台网络科技_seo排名优化方式方法_做整站优化

                                1282: 【J1】求逆序对

                                        时间限制: 1 Sec  内存限制: 128 MB
                                                        提交: 2  解决: 164
                                                [提交][状态][命题人:xuting]

题目描述

给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数目。

输入

第一行,一个数 n,表示序列中有 n个数。

第二行 n 个数,表示给定的序列。序列中每个数字不超过 109。

输出

输出序列中逆序对的数目。

样例输入

4
3 2 3 2

样例输出

3

提示

数据规模

对于所有数据,1<n≤5×105

代码敬上:

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define int long long
using namespace std; 
const int N = 5e6 + 10;
int tr[N * 2], n,ans;
int lowbit(int x) {return x & (-x);
}
void add(int x, int v) {while (x <= n) {tr[x] += v;x += lowbit(x);}
} 
int sum(int x) {int ans = 0;while (x) {ans += tr[x];x -= lowbit(x);}return ans;
} 
int main() {cin >> n;for (int i = 1; i <= n; i++) {int v;cin >> v;add(v, 1);ans += i - sum(v);}cout << ans << endl;return 0;
}

关键字:深圳网络营销推广_江西邢台网络科技_seo排名优化方式方法_做整站优化

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: