当前位置:网站首页>ABC 261 F - Sorting Color Balls (reverse pair)
ABC 261 F - Sorting Color Balls (reverse pair)
2022-07-31 00:33:00 【Harris-H】
ABC 261 F - Sorting Color Balls(逆序对)
Regardless of color,The minimum number of times that the adjacent swaps complete the sorting is the inverse logarithm.
The proof is that the number of times the largest number is moved to the end is the reverse logarithm,Then the next largest value、And so on until the minimum value.
Consider color,Therefore, we can subtract the inverse numbers of the same color.
那么答案就是: a n s = t o t r e v e r s e − t o t c o l i ans=tot_{reverse}-tot_{col_i} ans=totreverse−totcoli
We start with each colorvector存,Then run the reverse order pair.
Finally, run the whole side in reverse order.
reverse order B I T BIT BIT 即可.
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,x[N],c[N],tr[N];
vector<int>V[N];
long long rs;
void Ad(int i,int w){
for(;i;i-=i&-i)tr[i]+=w;
}
int Qr(int i){
int rs=0;
for(;i<=n;i+=i&-i)rs+=tr[i];
return rs;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&c[i]);
V[c[i]].push_back(i);
}
for(int i=1;i<=n;++i)scanf("%d",&x[i]);
for(int i=1;i<=n;++i){
int l=V[i].size();
for(int o=0;o<l;++o){
rs-=Qr(x[V[i][o]]+1);
Ad(x[V[i][o]],1);
}
for(int o=0;o<l;++o)Ad(x[V[i][o]],-1);
}
for(int i=1;i<=n;++i){
rs+=Qr(x[i]+1);
Ad(x[i],1);
}
printf("%lld\n",rs);
return 0;
}
边栏推荐
- Linux 部署mysql 5.7全程跟踪 完整步骤 django部署
- MySQL的grant语句
- Strict Mode for Databases
- firewalld
- 【Multithreading】
- Thesis understanding: "Designing and training of a dual CNN for image denoising"
- [Yugong Series] July 2022 Go Teaching Course 016-Logical Operators and Other Operators of Operators
- 【多线程】
- 限制字符绕过
- Homework: iptables prevent nmap scan and binlog
猜你喜欢
【Multithreading】
What is Promise?What is the principle of Promise?How to use Promises?
joiplay模拟器rtp如何安装
The difference between h264 and h265 decoding
加密传输过程
Understand from the 11 common examples of judging equality of packaging types in the written test: packaging types, the principle of automatic boxing and unboxing, the timing of boxing and unboxing, a
Error ER_NOT_SUPPORTED_AUTH_MODE Client does not support authentication protocol requested by serv
论文理解:“Designing and training of a dual CNN for image denoising“
How to install joiplay emulator rtp
MySQL database advanced articles
随机推荐
Neural Network (ANN)
从笔试包装类型的11个常见判断是否相等的例子理解:包装类型、自动装箱与拆箱的原理、装箱拆箱的发生时机、包装类型的常量池技术
firewalld
Jmeter参数传递方式(token传递,接口关联等)
Kotlin协程:协程上下文与上下文元素
VSCode高效开源神器有哪些
MySQL数据库进阶篇
Detailed explanation of 9 common reasons for MySQL index failure
论文理解:“Designing and training of a dual CNN for image denoising“
乌克兰外交部:乌已完成恢复粮食安全出口的必要准备
作业:iptables防止nmap扫描以及binlog
数据库的严格模式
[Yugong Series] July 2022 Go Teaching Course 015-Assignment Operators and Relational Operators of Operators
SWM32系列教程6-Systick和PWM
【深入浅出玩转FPGA学习15----------时序分析基础】
Word文件损坏如何修复
DATA AI Summit 2022提及到的对 aggregate 的优化
GO GOPROXY proxy Settings
MySQL master-slave replication and read-write separation script - pro test available
MySQL笔记下