当前位置:网站首页>Template_ Find the reverse pair of permutations_ Sort based on merge
Template_ Find the reverse pair of permutations_ Sort based on merge
2022-07-06 02:21:00 【This question AC sleep again】
//
#include<bits/stdc++.h>
using namespace std;
#define int long long // Large amount of data
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 ) Position difference
{
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;
}
边栏推荐
- 零基础自学STM32-复习篇2——使用结构体封装GPIO寄存器
- 从顶会论文看2022年推荐系统序列建模的趋势
- Regular expressions: examples (1)
- Sword finger offer 12 Path in matrix
- Campus second-hand transaction based on wechat applet
- 更改对象属性的方法
- 通过PHP 获取身份证相关信息 获取生肖,获取星座,获取年龄,获取性别
- Computer graduation design PHP college classroom application management system
- Use the list component to realize the drop-down list and address list
- 论文笔记: 图神经网络 GAT
猜你喜欢
Overview of spark RDD
Computer graduation design PHP part-time recruitment management system for College Students
2022 China eye Expo, Shandong vision prevention and control exhibition, myopia, China myopia correction Exhibition
Unity learning notes -- 2D one-way platform production method
从顶会论文看2022年推荐系统序列建模的趋势
Blue Bridge Cup embedded_ STM32 learning_ Key_ Explain in detail
Minecraft 1.18.1, 1.18.2 module development 22 Sniper rifle
MySQL lethal serial question 1 -- are you familiar with MySQL transactions?
Ue4- how to make a simple TPS role (II) - realize the basic movement of the role
[solution] every time idea starts, it will build project
随机推荐
安装php-zbarcode扩展时报错,不知道有没有哪位大神帮我解决一下呀 php 环境用的7.3
Selenium waiting mode
Spark accumulator
Global and Chinese market of commercial cheese crushers 2022-2028: Research Report on technology, participants, trends, market size and share
Use Scrollview and tabhost to realize vertical scrollbars and tabs
【机器人手眼标定】eye in hand
Paper notes: graph neural network gat
Derivation of Biot Savart law in College Physics
Structural theme model (I) STM package workflow
爬虫(9) - Scrapy框架(1) | Scrapy 异步网络爬虫框架
Adapter-a technology of adaptive pre training continuous learning
Bigder:34/100 面试感觉挺好的,没有收到录取
2022 eye health exhibition, vision rehabilitation exhibition, optometry equipment exhibition, eye care products exhibition, eye mask Exhibition
Minecraft 1.16.5 生化8 模组 2.0版本 故事书+更多枪械
500 lines of code to understand the principle of mecached cache client driver
Leetcode3, implémenter strstr ()
Extracting key information from TrueType font files
Computer graduation design PHP animation information website
SSM 程序集
我把驱动换成了5.1.35,但是还是一样的错误,我现在是能连成功,但是我每做一次sql操作都会报这个