当前位置:网站首页>P1908 reverse sequence pair
P1908 reverse sequence pair
2022-07-02 13:56:00 【Fu Fushou grass】
Tree array + discretization
The technique of discretization is to weight the order of input ( The value of the input ) Sort
Such as [5,4,2,6,3,1] The sequence obtained after sorting is [6,3,5,2,1,4]
The number of reverse pairs of the two is equal .
We can understand that : Choose any number in this ordered sequence , For this number , All the numbers in front of it are smaller than it , If the subscript of the previous number in the original array is greater than it , Then it forms a reverse order pair .
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
struct fenwick {
const int n;
std::vector<int> c;
fenwick(int n) : c(n + 10), n(n + 10) {
}
void add(int pos, int val) {
for (int i = pos; i < n; i += i & -i) {
c[i] += val;
}
}
int sum(int pos) {
int ans = 0;
for (int i = pos; i > 0; i -= i & -i) {
ans += c[i];
}
return ans;
}
int range(int l, int r) {
return std::abs(sum(r) - sum(l)); }
};
constexpr int N = 5e5 + 100;
pair<int, int> a[N];
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].first;
a[i].second = i + 1;
}
sort(a, a + n);
int ans = 0;
fenwick f(n);
for (int i = 0; i < n; i++) {
ans += f.range(a[i].second, n);
f.add(a[i].second, 1);
}
cout << ans << "\n";
}
int32_t main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int tt(1);
//std::cin >> tt;
while (tt--) {
solve();
}
return 0;
}
边栏推荐
- Tupang multi-target tracking! BOT sort: robust correlated multi pedestrian tracking
- 题解:《压缩技术》(原版、续集版)
- P3807 [template] Lucas theorem /lucas theorem
- Origin plots thermogravimetric TG and differential thermogravimetric DTG curves
- The 29 year old programmer in Shanghai was sentenced to 10 months for "deleting the database and running away" on the day of his resignation!
- 基于ssm+jsp框架实现的学生选课信息管理系统【源码+数据库】
- 693. 行程排序(map + 拓扑)
- Error: eacces: permission denied, access to "/usr/lib/node_modules"
- Slashgear shares 2021 life changing technology products, which are somewhat unexpected
- D language, possible 'string plug-ins'
猜你喜欢
Don't spend money, spend an hour to build your own blog website
Find love for speed in F1 delta time Grand Prix
selenium 元素定位方法
使用BLoC 构建 Flutter的页面实例
Whole house Wi Fi: a pain point that no one can solve?
MySQL45讲——学习极客时间MySQL实战45讲笔记—— 05 | 深入浅出索引(下)
Sum of the first n terms of Fibonacci (fast power of matrix)
题解:《压缩技术》(原版、续集版)
浏览器驱动的下载
Why is the default of switch followed by break?
随机推荐
Subcontracting configuration of uniapp applet subpackages
Halcon extract orange (Orange)
代码实现MNLM
Achievements in science and Technology (27)
混沌工程平台 ChaosBlade-Box 新版重磅发布
uniapp小程序 subPackages分包配置
Origin plots thermogravimetric TG and differential thermogravimetric DTG curves
瀏覽器驅動的下載
Browser driven Download
Quantum three body problem: Landau fall
故事點 vs. 人天
[技术发展-22]:网络与通信技术的应用与发展快速概览-2- 通信技术
Android kotlin material design technology points
Add sequence number column to query results in MySQL
c# 水晶报表打印
Skillfully use SSH to get through the Internet restrictions
Qt-制作一个简单的计算器-实现四则运算-将结果以对话框的形式弹出来
[indomitable medal activity] life goes on and writing goes on
Winter vacation daily question - lucky numbers in the matrix
Why can't d link DLL