当前位置:网站首页>模板_求排列逆序对_基于归并排序
模板_求排列逆序对_基于归并排序
2022-07-06 02:06:00 【这题AC再睡.】
//
#include<bits/stdc++.h>
using namespace std;
#define int long long // 大数据量
const int N=1e5+6;
int in[N];
int ans;
void merge( int x1,int y1,int x2,int y2 )
{
int tt[N];
int i=x1,j=x2,pos=0;
while( i<=y1 && j<=y2 ) // j-( x1+pos ) 位置差
{
if( in[i]<=in[j] ) tt[pos++]=in[i++];
else { ans+=j-( x1+pos ); tt[pos++]=in[j++]; }
}
while( i<=y1 ) tt[pos++]=in[i++];
while( j<=y2 ) tt[pos++]=in[j++];
for( i=0;i<pos;i++ ) in[x1+i]=tt[i];
}
void f( int x,int y )
{
if( x==y ) return ;
int mid=( x+y )>>1;
f( x,mid );
f( mid+1,y );
merge( x,mid,mid+1,y );
}
signed main()
{
int n,i;
while( cin>>n )
{
for( i=0;i<n;i++ ) cin>>in[i];
ans=0;
f( 0,n-1 );
cout<<ans<<endl;
}
return 0;
}
边栏推荐
- Use image components to slide through photo albums and mobile phone photo album pages
- Selenium element positioning (2)
- How to upgrade kubernetes in place
- 02.Go语言开发环境配置
- Global and Chinese markets of general purpose centrifuges 2022-2028: Research Report on technology, participants, trends, market size and share
- Multiple solutions to one problem, asp Net core application startup initialization n schemes [Part 1]
- SPI communication protocol
- 01.Go语言介绍
- [robot hand eye calibration] eye in hand
- [community personas] exclusive interview with Ma Longwei: the wheel is not easy to use, so make it yourself!
猜你喜欢
【机器人库】 awesome-robotics-libraries
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
2022 PMP project management examination agile knowledge points (8)
NumPy 数组索引 切片
Computer graduation design PHP enterprise staff training management system
在线怎么生成富文本
Tensorflow customize the whole training process
TrueType字体文件提取关键信息
Prepare for the autumn face-to-face test questions
Know MySQL database
随机推荐
Open source | Ctrip ticket BDD UI testing framework flybirds
Computer graduation design PHP campus restaurant online ordering system
Reasonable and sensible
Card 4G industrial router charging pile intelligent cabinet private network video monitoring 4G to Ethernet to WiFi wired network speed test software and hardware customization
FTP server, ssh server (super brief)
leetcode-两数之和
【机器人库】 awesome-robotics-libraries
Competition question 2022-6-26
Lecture 4 of Data Engineering Series: sample engineering of data centric AI
阿裏測開面試題
Use image components to slide through photo albums and mobile phone photo album pages
General process of machine learning training and parameter optimization (discussion)
Redis string type
Using SA token to solve websocket handshake authentication
Computer graduation design PHP college classroom application management system
【社区人物志】专访马龙伟:轮子不好用,那就自己造!
Flowable source code comments (36) process instance migration status job processor, BPMN history cleanup job processor, external worker task completion job processor
[coppeliasim] efficient conveyor belt
Adapter-a technology of adaptive pre training continuous learning
Publish your own toolkit notes using NPM