首页 > 试题广场 >

逆序对

[编程题]逆序对

作为程序员的小Q，他的数列和其他人的不太一样，他有 $2^n$ 个数。

老板问了小Q一共 m次，每次给出一个整数 $q_i (1 <= i <= m)$ , 要求小Q把这些数每 $2^{q_i}$ 分为一组，然后把每组进行翻转，小Q想知道每次操作后整个序列中的逆序对个数是多少呢？

例如:

对于序列1 3 4 2，逆序对有(4, 2),(3, 2),总数量为2。

翻转之后为2 4 3 1，逆序对有(2, 1),(4, 3), (4, 1), (3, 1),总数量为4。

第一行一个数
第二行个数，表示初始的序列()
第三行一个数
第四行m个数表示

m行每行一个数表示答案。

示例1

输入

初始序列2 1 4 3
 ->
第一次：1 2 3 4 -> 逆序对数为0
 ->
第二次：4 3 2 1 -> 逆序对数为6
 ->
第三次：4 3 2 1 -> 逆序对数为6
 ->
第四次：1 2 3 4 -> 逆序对数为0

算法知识视频讲解

大厂算法岗必拿下

发表于 2021-09-23 05:39:25

注意，一个序列的正序对+逆序对永远是常数。最后输出整个逆序对的结果。 index最后一层必为1；交换的时候顺序对每pow（2，x）交换其实就是预先构建好的正序对交换到逆序对上，然后对逆序对求和。 #include<bits/stdc++.h> using namespace std 展开全文

小牛冲冲冲jiang

发表于 2021-09-23 05:07:26

反转加计算只能过40% import java.util.Scanner; import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) { 展开全文

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师腾讯 2020 Java工程师

上传者：小小

难度：

38条回答 328收藏 18292浏览

扫一扫，把题目装进口袋