当前位置:网站首页>【SSL集训DAY2】Sort【树状数组】
【SSL集训DAY2】Sort【树状数组】
2022-08-09 22:35:00 【VL——MOESR】
思路:
模拟一下就会发现,搞完一次后最多的长度就只有2了,于是变成了求逆序对
c o d e code code
#include<iostream>
#include<cstdio>
#define lowbit(x) x & -x
using namespace std;
const int MAXN = 1e6 + 10;
int n;
int a[MAXN];
long long c[MAXN];
long long ans;
long long query_(int x) {
long long res = 0;
for(; x; x -= lowbit(x)) res += c[x];
return res;
}
void add(int x) {
for(; x <= n; x += lowbit(x)) c[x] ++;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
int i = 1;
while(i <= n) {
int j = i + 1;
while(a[j] < a[j - 1] && j <= n) j ++;
j --;
if(i != j) ans ++;
for(int k = i, g = j; k < g; k ++, g --) swap(a[k], a[g]);
i = j + 1;
}
for(int i = 1; i <= n; i ++) {
ans += query_(n) - query_(a[i]);
add(a[i]);
}
printf("%lld", ans);
return 0;
}
边栏推荐
猜你喜欢
金仓数据库 KingbaseGIS 使用手册(6.4. 几何对象存取函数)
Technology feast!Huayun Data brings six topics to OpenInfra Days China
杭电多校-Counting Stickmen-(思维+组合数+容斥)
安踏携手华为运动健康共同验证冠军跑鞋 创新引领中国体育
【JZOF】32从上往下打印二叉树
【集训DAY4】询问【Hash】
金仓数据库 KingbaseGIS 使用手册(6.5. 几何对象编辑函数)
Explore the TiDB Lightning source code to solve the found bugs
2022年最新《谷粒学院开发教程》:10 - 前台支付模块
[Cloud Native] This article explains how to add Tencent Crane to Kubevela addon
随机推荐
【JZOF】32从上往下打印二叉树
【云原生】一文讲透Kubevela addon如何添加腾讯Crane
领跑政务云,连续五年中国第一
Explore the TiDB Lightning source code to solve the found bugs
直播app开发搭建,flutter 实现自适应、自动换行、相对布局
用哈希简单封装unordered_map和unordered_set
【集训DAY5】选数字【数学】
Leetcode 701. 二叉搜索树中的插入操作
JSON对象和字符串相互转化
2022-08-09 mysql/stonedb-subquery performance improvement-introduction
ALV报表总结2022.8.9
JS--popstate事件--使用/教程/实例
上海一科技公司刷单被罚22万,揭露网络刷单灰色产业链
Qt 之 QDateEdit 和 QTimeEdit
Sqlserver restricts the ip under which accounts can access the database
2022/8/9 考试总结
Travel with Shengteng: See all the AI attractions in Jinling City in one day
leetcode 20. Valid Parentheses 有效的括号(中等)
恭喜获奖得主 | 互动有礼获赠 Navicat Premium
Leetcode 235. 二叉搜索树的最近公共祖先