老板问了小Q一共 m次，每次给出一个整数)
, 要求小Q把这些数每
分为一组，然后把每组进行翻转，小Q想知道每次操作后整个序列中的逆序对个数是多少呢？
例如:
对于序列1 3 4 2，逆序对有(4, 2),(3, 2),总数量为2。
翻转之后为2 4 3 1，逆序对有(2, 1),(4, 3), (4, 1), (3, 1),总数量为4。
[编程题]逆序对
- 热度指数：5804 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
作为程序员的小Q，他的数列和其他人的不太一样，他有
个数。
输入描述:
第一行一个数
第二行)
第三行一个数
第四行m个数表示
输出描述:
m行每行一个数表示答案。
示例1
输入
2 2 1 4 3 4 1 2 0 2
输出
0 6 6 0
说明
初始序列2 1 4 3->
第一次：1 2 3 4 -> 逆序对数为0->
第二次：4 3 2 1 -> 逆序对数为6->
第三次：4 3 2 1 -> 逆序对数为6->
第四次：1 2 3 4 -> 逆序对数为0
/* 段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起case通过率为0.00% */
//有没有大佬指正下
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main() {
int n, N, m;
int qi[20];
cin >> n;
N = pow(2, n);
vector<int> x(N);
for (int i = 0; i <N ; i++) {
cin >> x[i];
};
cin >> m;
for (int i = 0; i <m; i++) {
cin >> qi[i];
};
for (int i = 0; i <m; i++) {
//翻转
int b = pow(2, qi[i]); //一组多少个数
int a = N /b; //分成了多少组
//每一组进行翻转
for (int j = 0; j < a; j++) {
int temp;
for (int k = 0; k <b/2; k++) {
temp = x[k + j*b];
x[k + j*b] = x[j*b + b - 1 - k];
x[j*b + b - 1 - k] = temp;
};
};
//逆序对
int p=0;
for (int j = 0; j < N-1; j++) {
for (int k = j+1; k < N; k++) {
if (x[j] > x[k])p++;
};
};
qi[i] = p;
};
for (int i = 0; i < m; i++) {
cout << qi[i] << " ";
};
system("pause");
}
#include<vector>
#include<cmath>
using namespace std;
int main() {
int n, N, m;
int qi[20];
cin >> n;
N = pow(2, n);
vector<int> x(N);
for (int i = 0; i <N ; i++) {
cin >> x[i];
};
cin >> m;
for (int i = 0; i <m; i++) {
cin >> qi[i];
};
for (int i = 0; i <m; i++) {
//翻转
int b = pow(2, qi[i]); //一组多少个数
int a = N /b; //分成了多少组
//每一组进行翻转
for (int j = 0; j < a; j++) {
int temp;
for (int k = 0; k <b/2; k++) {
temp = x[k + j*b];
x[k + j*b] = x[j*b + b - 1 - k];
x[j*b + b - 1 - k] = temp;
};
};
//逆序对
int p=0;
for (int j = 0; j < N-1; j++) {
for (int k = j+1; k < N; k++) {
if (x[j] > x[k])p++;
};
};
qi[i] = p;
};
for (int i = 0; i < m; i++) {
cout << qi[i] << " ";
};
system("pause");
}
编辑于 2020-05-14 01:08:35
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int N = 1 << n;
//正序数组
int[] a = new int[N];
//逆序数组
int[] b = new int[N];
long[] order = new long[n + 1];
long[] reOrder = new long[n + 1];
for (int i = 0; i < N; ++i) {
//正序添加元素
a[i] = sc.nextInt();
//倒序添加元素
b[N - 1 - i] = a[i];
}
int[] tmp = new int[N];
//一次归并求逆序对数
mergeCount(a, 0, N - 1, tmp, reOrder, n);
//一次归并求顺序对数
mergeCount(b, 0, N - 1, tmp, order, n);
int m = sc.nextInt();
while (m-- > 0) {
// 2^i 个元素为一组进行翻转
int q = sc.nextInt();
for (int i = 1; i <= q; ++i) {
long temp = order[i];
order[i] = reOrder[i];
reOrder[i] = temp;
}
long count = 0;
for (int i = 1; i <= n; ++i) {
count += reOrder[i];
}
System.out.println(count);
}
}
private static void mergeCount(int[] nums, int left, int right, int[] temp, long[] reOrder, int index) {
if (left >= right) return;
int mid = (left + right) >>> 1;
mergeCount(nums, left, mid, temp, reOrder, index - 1);
mergeCount(nums, mid + 1, right, temp, reOrder, index - 1);
int i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (nums[i] > nums[j]) {
reOrder[index] += (mid + 1 - i);
++j;
} else {
++i;
}
}
merge(nums, left, mid, right, temp);
}
private static void merge(int[] nums, int left, int mid, int right, int[] temp) {
System.arraycopy(nums, left, temp, left, right - left + 1);
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) nums[k++] = temp[i] <= temp[j] ? temp[i++] : temp[j++];
while (i <= mid) nums[k++] = temp[i++];
while (j <= right) nums[k++] = temp[j++];
}
}
发表于 2020-09-22 17:43:16
回复(0)
O(nlogn)可全过
大概思路就是记录所有2^i上的逆序对，只要记录2i-1和另一半2i-1之间的逆序对，例如2341里面
21上有1个
22上一共3个，但是有一个在21中算过了，所以就是2个
计算这个值的过程用O(n2)能过80%，改成merge可以全过
同时，要计算2i下所有可能的组合,即2i-1*2i-1,再乘上2i的个数，即2n-i，得到2n+i-2,在merge的过程中同时还要记录等于的情况，因为这些等于的不管是否翻转都不是逆序对，所以对每一个2i还要减去等于的对数。
然后翻转的时候，假如翻转数字的是x，对于每个2i(x >= i),值都改为上面求出的数 - 原值
逆序对总数就是从1-n求和。
#include<stdio.h>
#include<vector>
using namespace std;
long long n, m, total, sum, offset, num;
vector<long long> count;
vector<long long> l;
vector<long long> l_copy;
vector<long long> max_c;
void mergesort(long long index, long long size)
{
if(size == 0)
{
l_copy[index] = l[index];
return;
}
vector<long long> l_copy2(1<<size);
long long st1 = index, st2 = index + (1 << (size - 1) ), ed1 = st2, ed2 = index + (1 << size);
long long pos = 0, p1 = st1, p2 = st2;
mergesort(st1, size - 1);
mergesort(st2, size - 1);
while(p1 < ed1 && p2 < ed2)
{
if(l_copy[p1] == l_copy[p2]){
long long c1 = 1, c2 = 1;
l_copy2[pos++] = l_copy[p1++];
l_copy2[pos++] = l_copy[p2++];
while(p1 < ed1 && l_copy[p1] == l_copy[p1 - 1]) l_copy2[pos++] = l_copy[p1++], ++c1;
while(p2 < ed2 && l_copy[p2] == l_copy[p2 - 1]) l_copy2[pos++] = l_copy[p2++], ++c2;
max_c[size] -= c1 * c2;
count[size] += (ed1 - p1) * c2;
}
else if(l_copy[p1] < l_copy[p2]){
l_copy2[pos++] = l_copy[p1++];
}
else {
count[size] += ed1 - p1;
l_copy2[pos++] = l_copy[p2++];
}
}
if(p1 == ed1)while(p2 != ed2) l_copy2[pos++] = l_copy[p2++];
else if(p2 == ed2) while(p1 != ed1) l_copy2[pos++] = l_copy[p1++];
for(long long i = st1; i < ed2; ++i) l_copy[i] = l_copy2[i - st1];
}
int main()
{
scanf("%lld", &n);
total = (long long)1 << n;
count.resize(n + 1);
max_c.resize(n + 1);
l.resize(total);
l_copy.resize(total);
for(long long i = 0; i < total; ++i) scanf("%lld", &l[i]);
max_c[0] = 1;
for(long long i = 1; i <= n; ++i) max_c[i] = (long long)1 <<(n + i - 2);//(1 << 2 * (i - 1) ) * ( 1 << (n - i))
mergesort(0, n);
scanf("%lld", &m);
for(long long i = 0; i < m; ++i)
{
scanf("%lld", &num);
sum = 0;
for(long long j = 1; j <= n; ++j)
{
if(j <= num) count[j] = max_c[j] - count[j];
sum += count[j];
}
printf("%lld\n", sum);
}
}
编辑于 2020-04-11 14:46:40
回复(7)
思路差不多就这样，如果注释哪里写错了欢迎指正
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int N = 1 << n;
//正序数组
int[] a = new int[N];
//a 的逆序数组，比如 a = [4,3,2,1], b = [1,2,3,4]
int[] b = new int[N];
/*
order[i] 表示 2^i 的 顺序对个数
reOrder[i] 表示 2^i 的 逆序对个数
比如 i = 1，那么就是每 2 个元素的逆序对的个数，比如 [4,3,2,1]，
有 [2,1] [4,3] 两个逆序对，即 reOrder[1] = 2
比如 i = 2，那么就是每 4 个元素的逆序对的个数，比如 [4,3,2,1],
有 [4,3] [2,1] [4,2] [4,1] [3,2] [3,1] 6 个逆序对，
只不过 [2,1] [4,3] 在 i = 1 的时候算过了，因此有 4 个
即 reOrder[2] = 4
我们可以发现，如果大小为 n 的数组是降序的，
那么逆序对个数为 n * (n - 1) / 2 个
比如 [4,3,2,1]
对于 4 来说，后面有 [3,2,1] 3 个元素小于它，那么逆序对个数为 3
对于 3 来说，逆序对个数为 2
对于 2 来说逆序对个数为 1
如果数组是降序的,那么逆序对个数为
(n - 1) + (n - 2) + ... + 1
= n * (n - 1) / 2
而顺序对的个数为 0，但如果我们将其中两个元素交换位置，
减少了 m 个逆序对的同时就会增加 m 个顺序对
这表示 顺序对的个数 + 逆序对的个数 = n * (n - 1) / 2，
即 顺序对 和 逆序对 是互补的
或者这么说，当数组的逆序对个数为 m， 顺序对的个数为 n
那么数组翻转过后，逆序对和顺序对的个数相互交换
即逆序对的个数变为 n， 顺序对的个数变为 m
因此，当我们对 2^i 个元素进行翻转的时候
实际上就是交换它们的顺序对和逆序对个数
*/
long[] order = new long[n + 1];
long[] reOrder = new long[n + 1];
for (int i = 0; i < N; ++i) {
//正序添加元素
a[i] = sc.nextInt();
//倒序添加元素
b[N - 1 - i] = a[i];
}
//一次归并求逆序对数
mergeSort(a, 0, N - 1, reOrder, n);
//一次归并求顺序对数
mergeSort(b, 0, N - 1, order, n);
int m = sc.nextInt();
while (m-- > 0) {
// 2^i 个元素为一组进行翻转
int q = sc.nextInt();
for (int i = 1; i <= q; ++i) {
long temp = order[i];
order[i] = reOrder[i];
reOrder[i] = temp;
}
long count = 0;
for (int i = 1; i <= n; ++i) {
count += reOrder[i];
}
System.out.println(count);
}
}
private static void mergeSort(int[] arr, int left, int right, long[] reOrder, int index){
if(left < right){
int mid = (left + right) >>> 1;
//归并使得 左右两边保证有序
mergeSort(arr, left, mid, reOrder, index - 1);
mergeSort(arr, mid + 1, right, reOrder, index - 1);
if(arr[mid] > arr[mid + 1]){
mertSort(arr, left, right, mid, reOrder, index);
}
}
}
public static void mertSort(int[] arr, int left, int right, int mid, long[] reOrder, int index) {
//mid 属于左边
int len1 = mid - left + 1;
int len2 = right - mid;
int[] l = new int[len1];
int[] r = new int[len2];
System.arraycopy(arr, left, l, 0, len1);
System.arraycopy(arr, mid + 1, r, 0, len2);
/*
逆序对：l[i] > r[j]
[left, mid) 是有序的，[mid, right] 是有序的
因此，如果 l[i] > r[j]，表示 l[i] 比 [0, j] 这些元素都大
那么逆序对个数对于 l[i] 来说，有 j + 1个
*/
int i = len1 - 1;
int j = len2 - 1;
int k = right;
long c = 0;
while(i >= 0 && j >= 0){
if(l[i] > r[j]){
c += j + 1;
arr[k] = l[i];
i--;
}else{
arr[k] = r[j];
j--;
}
k--;
}
System.arraycopy(r, 0, arr, left, j + 1);
//逆序对个数
reOrder[index] += c;
}
}
发表于 2020-08-28 11:55:41
回复(6)
通过百分之百，先利用归并排序初始化不同间隔的逆序对和顺序对之和，当反转时交换顺序对和逆序对即可。每次查询时将不同间隔的逆序对加起来。总复杂度为O(nm+n*2^n)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1<<20)+50;;
int n,m,q[maxn],a[maxn],v1[maxn],v2[maxn];
ll rev[50],nor[50];
void init(int o,int l,int r,ll rev[],int nums[]){
if(r==l){
return;
}
int mid=(l+r)/2;
init(o-1,l,mid,rev,nums);
init(o-1,mid+1,r,rev,nums);
ll no=0,re=0;
int i=l,j=mid+1,k=l;
for (i=l,j=mid+1,k=l;i<=mid && j<=r;){
if(nums[i]<=nums[j]){
a[k++]=nums[i];
i++;
}
else{
a[k++]=nums[j];
re+=1L*mid+1-i;
j++;
}
}
if(i<=mid){
while (i<=mid){
a[k++]=nums[i++];
}
}
if(j<=r){
while (j<=r){
a[k++]=nums[j++];
}
}
rev[o]+=re;
for (i=l;i<=r;i++){
nums[i]=a[i];
}
}
ll solve(int o){
for (int i=o;i>=0;i--){
swap(nor[i],rev[i]);
}
ll ans=0;
for (int i=0;i<=n;i++){
ans+=rev[i];
}
return ans;
}
int main(){
cin>>n;
int temp;
//vector<int> v1,v2;
for (int i=0;i<(1<<n);i++){
scanf("%d",&temp);
v1[i]=temp;
v2[i]=temp;
}
cin>>m;
for (int i=0;i<m;i++){
scanf("%d",&q[i]);
}
memset(nor,0,sizeof(nor));
memset(rev,0,sizeof(rev));
init(n,0,(1<<n)-1,rev,v1);
reverse(v2,v2+(1<<n));
init(n,0,(1<<n)-1,nor,v2);
for (int i=0;i<m;i++){
cout<<solve(q[i])<<endl;
}
}
发表于 2020-03-04 17:30:23
回复(3)
这题的坑很多，我的通过率从50 到10 到60 到70 到80 到100.。。。主要是要求解不同长度的逆序对和顺序对数量，翻转后将相应的进行交换，注意相等的情况（既不是逆序对也不是顺序对，可以求解翻转后的数组的逆序对来得到原数组的顺序对）。
详情可以参考我的博客。
发表于 2020-04-04 18:03:30
回复(2)
求逆序对问题用归并排序的时间复杂度比暴力算法更低。
假设有一个数组{8，1，2，5，7，4，3，6}
首先归并排序第一次对数组进行分割 8 1 2 5 7 4 3 6
二次分割 8 1 25 74 36
三次分割 8 1 2 5 7 4 3 6
第一次合并 18 25 47 36 reorder[1]=2, order[1]=2
//用reorder[i]来记录第i次合并中存在的逆序对数,order[i]来记录第i次合并中存在的顺序对数。
第二次合并 1258 3467 reorder[2]=5, order[2]=3
第三次合并 12345678 reorder[3]=6, order[3]=10
那么数组{8，1，2，5，7，4，3，6}中存在的逆序对就等于reorder[1]+reorder[2]+reorder[3]=13
将数组{8，1，2，5，7，4，3，6}每2^2个为一组进行翻转{5，2，1，8，6，3，4，7}
首先归并排序第一次对数组进行分割 5 2 1 8 6 3 4 7
二次分割 5 2 18 63 47
三次分割 5 2 1 8 6 3 4 7
第一次合并 25 18 36 47 reorder[1]=2, order[1]=2
第二次合并 1258 3467 reorder[2]=3, order[2]=5
第三次合并 12345678 reorder[3]=6, order[3]=10
那么数组{5，2，1，8，6，3，4，7}中存在的逆序对就等于reorder[1]+reorder[2]+reorder[3]=11
由此我们可以观察到对数组每2^2个进行翻转时，reorder[1]和order[1]进行了互换,reorder[2]和order[2]亦是如此。
所以对数组每2^i个进行翻转时，我们可以把1~i的reorder和order数组元素互换即可继续通过计算reorder数组的累加和来求得数组的逆序对数。
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int N = 1 << n;
int[] a = new int[N];
int[] b = new int[N];//用来存储数组的逆序,对逆序的数组进行一次归并排序可以直接得到order数组
int[] order = new int[n + 1];//为了便于计算，所以设置order下标是1~n，因此数组大小为n+1
int[] reorder = new int[n + 1];
for (int i = 0; i < N; i++)
{
a[i] = sc.nextInt();
b[N - i - 1] = a[i];
}
MergeSort(a, 0, N - 1, reorder, n);//对整个数组进行归并排序，n表示对reorder[1]~reorder[n]进行初始化
MergeSort(b, 0, N - 1, order, n);//对整个逆序数组进行归并排序，完成对order[1]~order[n]的初始化
int m = sc.nextInt();
while(m-- > 0)
{
int count = 0;
int q = sc.nextInt();
for (int i = 1; i <= q; i++) //像之前讲的，将1~q的reorder[i]和order[i]进行互换
{
int temp = reorder[i];
reorder[i] = order[i];
order[i] = temp;
}
for (int i = 1; i <= n; i++)
{
count+= reorder[i];//累加reorder数组，求得对数组中每2^q个元素进行翻转后的逆序对数
}
System.out.println(count);
}
}
public static void MergeSort(int[] a , int left, int right, int[] reorder, int index)
{
if(left < right)
{
int mid = (right + left) / 2;
MergeSort(a, left, mid, reorder,index - 1);
MergeSort(a, mid + 1, right, reorder,index -1);
if(a[mid] > a[mid+1])//如果a[mid]<=a[mid+1]，则原数组有序，不需要合并
Merge(a, left, right,reorder, index);
}
}
public static void Merge(int[] a, int left, int right,int[] reorder, int index)//index表示对reorder[index]进行初始化
{
int mid = (right + left) / 2;
int Length1 = mid - left + 1;
int Length2 = right - mid;
int[] l = new int[Length1];//存储a[left]~a[mid]
int[] r = new int[Length2];//存储a[mid+1]~a[right]
System.arraycopy(a, left, l, 0, Length1);//对l进行初始化
System.arraycopy(a, mid + 1, r, 0, Length2);//对r进行初始化
int i = 0;
int j = 0;
int c= 0;
int k = left;
while(i < Length1 && j < Length2)
{
if(l[i] <= r[j])
{
a[k] = l[i];
i++;
}
else
{
a[k] = r[j];
j++;
c += Length1 - i;//当l[i]>r[j]时，因为l是递增序列，所以l[i]~l[Length1-1]均>r[j]，所以有Length1-i个元素大于r[j]
}
k++;
}
System.arraycopy(l, i, a, k, Length1 - i);//前面归并排序MergeSort中调用Merge合并的条件是a[mid]>a[mid+1],因为当a[mid]<=a[mid+1]时说明原数组有序，无需合并。l[Length1-1]>r[Length2-1],即l数组的最大值大于r数组的最大值，所以当r中的数全部进入a数组后，l数组中仍有剩余。
reorder[index] += c;
}
}
编辑于 2021-03-31 18:01:39
回复(2)
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = 1<<n;
int[] a = new int[k];
int[] b = new int[k];
for(int i=0;i<k;i++){
a[i] = sc.nextInt();
b[k-1-i] = a[i];
}
int m = sc.nextInt();
int[] q = new int[m];
for(int i=0;i<m;i++){
q[i] = sc.nextInt();
}
getAns(n,a,b,m,q);
}
public static void getAns(int n,int[] a,int[] b,int m,int[] q){
int k = a.length;
int[] tmp = new int[k];
long[] reorder = new long[n+1];
long[] order = new long[n+1];
reverse(a,0,k-1,reorder,tmp,n);
reverse(b,0,k-1,order,tmp,n);
for(int i=0;i<m;i++){
int cur = q[i];
for(int j=1;j<=cur;j++){
long temp = reorder[j];
reorder[j] = order[j];
order[j] = temp;
}
long count = 0;
for(int j=1;j<=n;j++){
count+=reorder[j];
}
System.out.println(count);
}
}
public static void reverse(int[] arr,int left,int right,long[] reorder,int[] tmp,int index){
if(left<right){
int mid = (left+right)>>>1;
reverse(arr,left,mid,reorder,tmp,index-1);
reverse(arr,mid+1,right,reorder,tmp,index-1);
if(arr[mid]>arr[mid+1])
reverseCross(arr,left,mid,right,reorder,tmp,index);
}
}
public static void reverseCross(int[] arr,int left,int mid,int right,long[] reorder,int[] tmp,int index){
for(int i=left;i<=right;i++){
tmp[i] = arr[i];
}
int i = left,j = mid+1;
long count = 0;
for(int k=left;k<=right;k++){
if(i==mid+1){
arr[k] = tmp[j];
j++;
}else if(j==right+1){
arr[k] = tmp[i];
i++;
}else if(tmp[i]<=tmp[j]){
arr[k] = tmp[i];
i++;
}else if(tmp[i]>tmp[j]){
arr[k] = tmp[j];
j++;
count+=mid-i+1;
}
}
reorder[index] += count;
}
}
发表于 2020-08-20 21:30:38
回复(0)
考虑翻转，其实每个块内翻转不影响其它块。只需要预先统计每层的单独块内的正逆序对数（记得把非正非逆的不要算，所以就长了两个分治，丑懒得改）。然后询问对于一个块大小的翻转实际对更小的块也翻转了，直接一路异或下去即可，然后只要为0说明这个块大小没翻转过，答案就是逆序对数，否则正序对数。
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
using ll=long long;
int main() {
int n; cin>>n;
vector<ll>a((1<<n)+1);
for(int i=1;i<=1<<n;i++)cin>>a[i];
vector<ll>f(n+1),g(n+1),c((1<<n)+1),b(a);
auto divide=[&](auto divide,int l,int r,int dep)->void{
if(l==r)return;
int mid=l+r>>1;
divide(divide,l,mid,dep-1);
divide(divide,mid+1,r,dep-1);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])c[k++]=a[i++];
else c[k++]=a[j++],f[dep]+=mid-i+1;
}
while(i<=mid)c[k++]=a[i++];
while(j<=r)c[k++]=a[j++];
for(int k=l;k<=r;k++)a[k]=c[k];
};
divide(divide,1,1<<n,n);
a=b;
auto divide1=[&](auto divide1,int l,int r,int dep)->void{
if(l==r)return;
int mid=l+r>>1;
divide1(divide1,l,mid,dep-1);
divide1(divide1,mid+1,r,dep-1);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]<a[j])c[k++]=a[i++],g[dep]+=r-j+1;
else c[k++]=a[j++];
}
while(i<=mid)c[k++]=a[i++];
while(j<=r)c[k++]=a[j++];
for(int k=l;k<=r;k++)a[k]=c[k];
};
divide1(divide1,1,1<<n,n);
vector<int>d(n+1);
int m; cin>>m;
while(m--)
{
int q; cin>>q;
ll ans=0;
for(int i=n;i>=1;i--)
{
if(i<=q)d[i]^=1;
if(d[i])ans+=g[i];
else ans+=f[i];
}
cout<<ans<<"\n";
}
return 0;
}
发表于 2023-03-20 02:46:05
回复(0)
归并解法，写的有点乱，修修补补的，接下来尝试一下线段树解法，主要就是记录顺序对和逆序对的数量，比如0~3，翻转0~1、2~3时，前两个和后两个之间的逆序对，顺序对不变
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> tmp;
vector<pair<ll,ll>> res;
void merge(vector<int>& data, int l, int r)
{
if (l == r) return;
int mid = (l + r) >> 1;
merge(data, l, mid);
merge(data, mid + 1, r);
int i = l, j = mid + 1, pos = l;
int step = r - l + 1, exp = 0;
while ((1 << exp) != step) ++exp;
while (i <= mid && j <= r)
{
if (tmp[i] > tmp[j])
{
data[pos++] = tmp[i++];
res[exp].first += r - j + 1;
}
else if (tmp[i] < tmp[j])
{
data[pos++] = tmp[j++];
res[exp].second += mid - i + 1;
}
else
{
int val = tmp[i];
int ii = i, jj = j;
while (ii <= mid)
{
if (tmp[ii] == val) data[pos++] = tmp[ii++];
else break;
}
while (jj <= r)
{
if (tmp[jj] == val) data[pos++] = tmp[jj++];
else break;
}
res[exp].first += (r - jj + 1)*(ii - i);
res[exp].second += (mid - ii + 1)*(jj - j);
i = ii, j = jj;
}
}
while (i <= mid)
data[pos++] = tmp[i++];
while (j <= r)
data[pos++] = tmp[j++];
while (l <= r)
{
tmp[l] = data[l];
++l;
}
}
int main()
{
int n, m;
cin >> n;
long long num = pow(2, n);
vector<int> numList(num);
for (int i = 0; i < num; ++i)
cin >> numList[i];
tmp = numList;
res.resize(n + 1, { 0,0 });
merge(numList, 0, num - 1);
cin >> m;
int q;
for (int i = 0; i < m; ++i)
{
cin >> q;
ll ret = 0;
for (int j = 1; j <= q; ++j)
{
swap(res[j].first, res[j].second);
ret += res[j].first;
}
for (int j = q + 1; j <= n; ++j)
ret += res[j].first;
cout << ret << endl;
}
return 0;
}
发表于 2020-05-07 15:59:27
回复(0)
//为什么我只能过60% 我写的有什么问题？
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using gg=long long;
void sort(vector<gg>&a,vector<gg>&tmp,vector<gg>&reord,vector<gg>&ord,gg l,gg r,gg id)
{
if(r==l){
return;
}
gg mid=l+((r-l)>>1);
sort(a,tmp,reord,ord,l,mid,id-1);
sort(a,tmp,reord,ord,mid+1,r,id-1);
gg i=l,j=mid+1,k=0;
while(i<=mid && j<=r)
{
if(a[i]>a[j])
{
reord[id]+=mid-i+1;
tmp[k++]=a[j++];
}else {
ord[id]+=r-j+1;
tmp[k++]=a[i++];
}
}
while(i<=mid)
{
tmp[k++]=a[i++];
}
while(j<=r)
{
tmp[k++]=a[j++];
}
for(gg i=l,k=0;i<=r;i++)
{
a[i]=tmp[k++];
}
}
int main() {
gg N;
cin>>N;
gg n=1<<N;
vector<gg>a(n);
for(gg i=0;i<n;i++)
{
cin>>a[i];
}
vector<gg>tmp(n,0);
vector<gg>reord(N+1,0);
vector<gg>ord(N+1,0);
sort(a,tmp,reord,ord,0,n-1,N);
gg m;
cin>>m;
while(m--)
{
gg q;
cin>>q;
gg res=0;
//第q层~1层交换reord~ord;
for(gg i=q;i>=1;i--)
swap(ord[i],reord[i]);
for(gg i=1;i<=N;i++)
res+=reord[i];
cout<<res<<'\n';
}
return 0;
}
// 64 位输出请用 printf("%lld")
编辑于 2023-06-28 00:23:22
回复(0)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN=(1<<20)+5;
ll n,nn,m,a[MAXN],b[MAXN],f[25],z[25],c[MAXN];
void msort(ll a[],ll l,ll r,ll d,ll g[])
{
if(l>=r)
return ;
int mid=l+r>>1;
msort(a,l,mid,d-1,g);
msort(a,mid+1,r,d-1,g);
ll i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]<a[j])
b[k++]=a[i++];
else if(a[i]==a[j])
b[k++]=a[i++];
else
b[k++]=a[j++],g[d]+=mid-i+1;
}
while(i<=mid)
b[k++]=a[i++];
while(j<=r)
b[k++]=a[j++];
for(i=l;i<=r;i++)
a[i]=b[i];
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,j,q,x;
cin>>n;
nn=1<<n;
for(i=1;i<=nn;i++)
cin>>a[i],c[i]=a[i];
msort(a,1,nn,n,f);
reverse(c+1,c+nn+1);
msort(c,1,nn,n,z);
cin>>q;
while(q--)
{
cin>>x;
ll sum=0;
for(i=x;i>=1;i--)
swap(f[i],z[i]);
for(i=1;i<=n;i++)
sum=sum+f[i];
cout<<sum<<endl;
}
return 0;
}
发表于 2022-04-21 22:30:56
回复(0)
import java.util.Scanner;
//主要是逆序对这块用的归并最后几个过不了
public class Main {
static int[] nums = null;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
nums = new int[(int) Math.pow(2,n)];
for (int i = 0; i < nums.length; i++) {
nums[i] = scanner.nextInt();
}
int m = scanner.nextInt();
int[] count = new int[m];
for (int i = 0; i < count.length; i++) {
count[i] = scanner.nextInt();
}
for (int j : count) {
System.out.println(getnums((int) Math.pow(2, j)));
}
}
private static int getnums(int pow) {
int l = 0,r = l+pow-1;
while (l<r){
int flag = r;
while (l<flag){
int a = nums[l];
nums[l] = nums[flag];
nums[flag] = a;
l++;flag--;
}
l = r+1;
r = l+pow-1>=nums.length?nums.length-1:l+pow-1;
}
return reversePairs(nums);
}
public static int reversePairs(int[] nums) {
int len = nums.length;
if (len < 2) {
return 0;
}
int[] copy = new int[len];
for (int i = 0; i < len; i++) {
copy[i] = nums[i];
}
int[] temp = new int[len];
return reversePairs(copy, 0, len - 1, temp);
}
private static int reversePairs(int[] nums, int left, int right, int[] temp) {
if (left == right) {
return 0;
}
int mid = left + (right - left) / 2;
int leftPairs = reversePairs(nums, left, mid, temp);
int rightPairs = reversePairs(nums, mid + 1, right, temp);
if (nums[mid] <= nums[mid + 1]) {
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(nums, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}
private static int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left;
int j = mid + 1;
int count = 0;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
nums[k] = temp[j];
j++;
} else if (j == right + 1) {
nums[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i];
i++;
} else {
nums[k] = temp[j];
j++;
count += (mid - i + 1);
}
}
return count;
}
}
发表于 2022-02-10 19:41:01
回复(0)
WA ，不懂为啥，简单的cdq分治求逆序对。
有巨巨的请告诉我，谢谢。
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n; cin >> n;
int N = 1 << n;
vector<i64> order(n + 1), reorder(n + 1);
vector<int> a(N), b(N), temp(N);
for(int i = 0;i < N; i++) {
int x; cin >> x;
a[i] = b[N - i - 1] = x;
}
function<void(int, int, int)> dfs1 = [&](int l, int r, int stp) {
if(l == r) return ;
int m = (l + r) / 2;
dfs1(l, m, stp - 1);
dfs1(m + 1, r, stp - 1);
int p = l, q = m + 1;
for(int i = l;i <= r; i++) {
if((p <= m && a[p] <= a[q]) || q > r) temp[i] = a[p++];
else order[stp] += p - l, temp[i] = a[q++];
}
for(int i = l;i <= r; i++) a[i] = temp[i];
};
function<void(int, int, int)> dfs2 = [&](int l, int r, int stp) {
if(l == r) return ;
int m = (l + r) / 2;
dfs2(l, m, stp - 1);
dfs2(m + 1, r, stp - 1);
int p = l, q = m + 1;
for(int i = l;i <= r; i++) {
if((p <= m && b[p] <= b[q]) || q > r) temp[i] = b[p++];
else reorder[stp] += p - l, temp[i] = b[q++];
}
for(int i = l;i <= r; i++) b[i] = temp[i];
};
dfs1(0, N - 1, n);
dfs2(0, N - 1, n);
int q; cin >> q;
while(q--) {
int x; cin >> x;
for(int j = 1;j <= x; j++) swap(order[j], reorder[j]);
i64 ans = 0;
cout << accumulate(reorder.begin(), reorder.end(), 0) << '\n';
}
}
发表于 2022-02-01 20:32:37
回复(0)
这是一道挺有难度的问题，我 debug 了挺长时间终于通过了，写个题解分享一下思路吧；
首先，利用归并排序求一个序列中的逆序对数，应该是一个比较经典的问题，这道题需要在这个基础之上做更多的工作。
我们观察逆序对的一些性质，以题目所给的 [1, 3, 4, 2] 为例，有两个逆序对 [3, 2] 和 [4, 2]，而如果我们按照 2 个数一组翻转之后，得到序列为 [3, 1, 2, 4], 这时候，逆序对为 [3, 1], [3, 2]。可以看到，[3, 2] 这个逆序对在翻转前后，是一直存在的，而 [4, 2] 这个原来存在的逆序对翻转之后则不再是逆序对了，同样的原来序列中的 [1, 3] 在翻转之后变成了新的逆序对 [3, 1]。通过上面的分析， 我们可以看到，在按照一定的组距翻转前后，原来是同一个组内的逆序对将消失，原来是同一个组内的顺序对将变成逆序对，原来跨越组间的逆序对将保持不变，还可以想到，原来想等的数对，无论是组间还是组内，都不会发生改变。
根据上面的分析过程，我基于归并排序做了一些改编。在归并排序的过程中，记录下不同层次的归并中找到的逆序对数，相等的序列对数；简单说，用一个reverses数组做记录，reverses[i] 表示在对 2 的 i 次方个数之间做归并操作的时候（也就是对 2 的 i + 1 次方个数最最后一步）存在的逆序对数；用一个 equal 数组最记录，equal[i] 表示在对 2 的 i 次方个数之间做归并操作的时候（也就是对 2 的 i + 1 次方个数最最后一步）存在的相等的数组数目；
于是很容易可以想到，所有的逆序对数为 reverses 数组的和；
当按照某一组距进行翻转的时候，所有小于这个组距的下标对应的 reverses 数组中的值都会变化，也就是原来的逆序对变成顺序对，原来的顺序对变成逆序对；于是我们还应该先计算出所有的数对数目，我的代码中 num_pairs 数组就是这个含义，然后减去 equal 数组中记录的相等的数对，再减去翻转前 reverses 数组中记录的值。完整代码如下：
// 使用归并排序的思想
// 记录下组内的逆序对和组间的逆序对
#include<iostream>
#include<vector>
using namespace std;
void merge_sort(vector<int> &vec, vector<int> &trans, vector<long long> &reverses, vector<long long> &equal, int start, int end, int degree) {
if(end - start == 1) {
return;
}
int mid = start + (end - start) / 2;
merge_sort(vec, trans, reverses, equal, start, mid, degree - 1);
merge_sort(vec, trans, reverses, equal, mid, end, degree - 1);
int l = start, r = mid, ptr = start;
while(l < mid && r < end) {
// 左边比右边大
if(vec[l] > vec[r]) {
reverses[degree] += (long long)(end - r);
trans[ptr++] = vec[l++];
} else if(vec[l] == vec[r]){
int num1 = 0, num2 = 0, tmp = l, t = vec[l];
while(tmp < mid && vec[tmp] == t) {
num1++;
tmp++;
}
while(r < end && vec[r] == t) {
num2++;
trans[ptr++] = vec[r++];
}
equal[degree] += (long long)num1 * (long long)num2;
} else{
trans[ptr++] = vec[r++];
}
}
while(l < mid)
trans[ptr++] = vec[l++];
while(r < end)
trans[ptr++] = vec[r++];
for(int i = start; i < end; ++i)
vec[i] = trans[i];
}
int main() {
int n, m, size, ops;
long long num, res = 0;
cin >> n;
size = 1 << n;
vector<int> vec(size, 0);
vector<int> trans(size, 0);
vector<long long> reverses(n, 0);
vector<long long> equal(n, 0);
vector<long long> num_pairs(n, 0);
for(int i = 0; i < n; ++i) {
num = 1 << i;
num_pairs[i] = num * num * (1 << (n - i - 1));
}
for(int i = 0; i < size; ++i)
cin >> vec[i];
merge_sort(vec, trans, reverses, equal, 0, size, n - 1);
cin >> m;
for(int i = 0; i < m; ++i) {
cin >> ops;
res = 0;
for(int j = ops - 1; j >= 0; --j) {
reverses[j] = num_pairs[j] - reverses[j] - equal[j];
}
for(int j = 0; j < n; ++j)
res += reverses[j];
cout << res << endl;
}
return 0;
}
发表于 2021-09-07 15:09:36
回复(0)
#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
using namespace std;
vector<long long> OrderCnt(21, 0);
vector<long long> reOrderCnt(21, 0);
void MergeSort(vector<long long>& vec, long long begin, long long end, int d) {
assert((end - begin) == (long long)pow(2, d));
if (begin == end || begin == end - 1)
return;
long long mid = (begin + end) / 2;
MergeSort(vec, begin, mid, d - 1);
MergeSort(vec, mid, end, d - 1);
vector<long long> nums(end - begin);
long long i = begin;
long long j = mid;
long long k = 0;
while (i < mid && j < end) {
if (vec[i] < vec[j]) {
OrderCnt[d] += (end - j);
nums[k++] = vec[i++];
}
else if (vec[i] > vec[j]) {
reOrderCnt[d] += (mid - i);
nums[k++] = vec[j++];
}
else if (vec[i] == vec[j]) {
long long tmp = j + 1;
while (tmp < end && vec[tmp] == vec[j])
tmp++;
OrderCnt[d] += (end - tmp);
nums[k++] = vec[i++];
}
}
while (i < mid)
nums[k++] = vec[i++];
while (j < end)
nums[k++] = vec[j++];
k = 0;
for (int i = begin; i < end; i++)
vec[i] = nums[k++];
return;
}
int main() {
int n;
cin >> n;
int len = pow(2, n);
vector<long long> vec(len);
for (long long i = 0; i < len; i++)
cin >> vec[i];
MergeSort(vec, 0, len, n);
long long m, q;
cin >> m;
while (m--) {
cin >> q;
for (int i = 0; i <= q; i++)
swap(OrderCnt[i], reOrderCnt[i]);
long long cnt = 0;
for (int i = 0; i <= n; i++)
cnt += reOrderCnt[i];
cout << cnt << endl;
}
return 0;
}
发表于 2021-07-15 18:09:48
回复(0)
// 这题思想就是找到各个层级顺逆序对 然后在操作的时候交换一下顺逆序对 思路很简单 但是坑点很多
#include<iostream>
#include<string.h>using namespace std;
//找到各个层级的顺逆序对 注意处理值一样的 既不算逆序对也不算顺序对！！！
void findReverse(long long* a, long long start, long long end, long long* reverse, long long* order, long long pos){
if(start == end - 1 || start == end) return;
long long mid = (start + end) / 2;
findReverse(a, start, mid, reverse, order, pos + 1);
findReverse(a, mid, end, reverse, order, pos + 1);
long long cur = 0;
long long cur_reverse = 0;
long long cur_order = 0;
long long left_point = start;
long long right_point = mid;
long long* b = new long long[end - start];
while(left_point < mid && right_point < end){
while(left_point < mid && right_point < end && a[left_point] <= a[right_point]) {
b[cur++] = a[left_point++];
reverse[pos] += cur_reverse;
}
while(left_point < mid && right_point < end && a[left_point] > a[right_point]){
b[cur++] = a[right_point++];
cur_reverse ++;
}
}
if(left_point < mid){
reverse[pos] += cur_reverse * (mid - left_point);
}
// 计算该层级顺序对
cur = 0;left_point = start;
right_point = mid;
while(left_point < mid && right_point < end){
while(left_point < mid && right_point < end && a[left_point] < a[right_point]) {
b[cur++] = a[left_point++];
cur_order++;
}
while(left_point < mid && right_point < end && a[left_point] >= a[right_point]){
b[cur++] = a[right_point++];
order[pos] += cur_order;
}
}
if(right_point < end){
order[pos] += cur_order * (end - right_point);
}
// 合并
while(left_point < mid){b[cur++] = a[left_point++];
}
while(right_point < end){
b[cur++] = a[right_point++];
}
for(long long i = start; i < end; i++){
a[i] = b[i - start];
}
delete[] b;
}
int main(){
int n, m;
cin >> n;
long long* a = new long long[1<<n];
// 数值范围较大 注意使用long long
long long* reverse = new long long[(n+1)];
long long* order = new long long[(n+1)];
memset(a, 0, sizeof(long long)*(1<<n));
memset(reverse, 0, sizeof(long long)*(n+1));
memset(order, 0, sizeof(long long)*(n + 1));
for(long long i = 0; i < (1<<n); i++){
cin >> a[i];
}
findReverse(a, 0, 1<<n, reverse, order, 0);
long long total = 0;
for(long long i = 0; i < n; i++){
total += reverse[i];
}
cin >> m;
long long q;
while(m--){
cin >> q;
// 交换各层逆序对
for(long long j = 1; j <= q; j++){
total -= reverse[n - j];
long long temp = reverse[n - j];
reverse[n - j] = order[n -j];
order[n -j]= temp;
total += reverse[n - j];
}
cout << total << endl;
}
delete[] a;
delete[] reverse;
delete[] order;
return 0;
}
编辑于 2021-04-16 11:23:15
回复(0)
//开始忽略了还有相等情况，直接用对数总和减去逆序对了。实际上考虑相等情况，应该是顺序与逆序交替。
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
//void mergesort(vector<int> &nums,int left,int right,vector<int> &dp,int n);
//dp[i]表示长度为2^i长度左右两侧的归并数目.归并排序。
void mergesort(vector<long long> &nums,int left,int right,vector<long long> &dp,int k) {//归并排序，计算逆序对数量
if(left>=right) return;
int mid=(right+left)/2;
mergesort(nums,left,mid,dp,k-1);
mergesort(nums,mid+1,right,dp,k-1);
int l=left,r=mid+1;
while(l<=mid){
while(r<=right&&nums[l]>nums[r]){
++r;
}
dp[k]+=r-mid-1;
++l;
}
vector<long long> temp(right-left+1);
l=left,r=mid+1;
int p=0;
while(l<=mid||r<=right){
if(l>mid){
temp[p++]=nums[r++];
}
else if(r>right){
temp[p++]=nums[l++];
}
else{
if(nums[l]<nums[r]){
temp[p++]=nums[l++];
}
else{
temp[p++]=nums[r++];
}
}
}
for(int i=0;i<temp.size();++i){
nums[left+i]=temp[i];
}
}
int main(){
int n;
cin>>n;
int len=1<<n;
vector<long long> v(len);
for(int i=0;i<len;++i){
cin>>v[i];
}
vector<long long> dp(n+1,0);
vector<long long> rdp(n+1,0);
vector<long long> rv(v.rbegin(),v.rend());
mergesort(v,0,len-1,dp,n); //计算逆序对。dp[n]表示间隔至少为2^(n-1)的逆序对。对应归并排序每次递归后子序列长度。
mergesort(rv,0,len-1,rdp,n); //计算顺序对，翻转数组则求逆序等于求原数组顺序
// for(int i=0;i<=n;++i){
// cout<<dp[i];
// }
//cout<<endl;
int m;
cin>>m;
int q;
for(int i=0;i<m;++i){
cin>>q;
long long res=0;
for(int i=1;i<=n;++i){
if(i<=q) swap(dp[i],rdp[i]);
res+=dp[i];
// cout<<endl;
}
cout<<res<<endl;
}
return 0;
}
发表于 2021-03-22 14:34:39
回复(0)
有没有用MATLAB的大神，解读一下，就过了40，里面是不是有奇数个的啊，看题目应该都是偶数的。
clear
try
n = input('');
s = input('','s');
m = input('');
k = input('','s');
s = str2num(s);
k = str2num(k);
ss = zeros(m+1,2^n);
ss(1,:) = s;
for i1 = 1 : m
q = zeros(2^(k(i1)),2^n/2^(k(i1)));
q(:) = ss(i1,:);
q = q';
q = q(:,end:-1:1);
q = q';
ss(i1+1,:) = q(:);
end
y = zeros(m+1,1);
for i2 = 1 : 2^n-1
y = y + sum(ss(:,i2+1:end)<ss(:,i2),2);
end
fprintf('%d\n',y(2:end));
catch
end
发表于 2020-08-21 17:02:29
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
