归并排序
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
int n;
PII a[N]; //a[i]={身高,编号}
LL cnt[N]; //cnt[i]表示编号为i的小朋友交换次数
PII temp[N];
void merge(int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge(l, mid), merge(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (a[i] <= a[j])
{
//相对于i来说,j 前面的数都比它小, j 前面的数都和 i 交换过
cnt[a[i].y] += j - mid - 1;
temp[k++] = a[i++];
}
else {
//相对于j来说,i 后面的数都比它大, i 后面的数都和 j 交换
cnt[a[j].y] += mid - i + 1;
temp[k++] = a[j++];
}
while (i <= mid)
{
cnt[a[i].y] += j - mid - 1;
temp[k++] = a[i++];
}
while (j <= r) temp[k++] = a[j++];
for (int i = l, j = 0; i <= r; i++, j++) a[i] = temp[j];
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) scanf("%d", &a[i].x), a[i].y = i;
merge(0, n - 1);
LL res = 0;
for (int i = 0; i < n; i++) res += (1 + cnt[i]) * cnt[i] / 2;
cout << res;
}
树状数组
树状数组保存的并不是这个数,而是这个数出现的次数。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], tr[N];
long long cnt[N];
int lowbit(int x)
{
return x & -x;
}
void add(int k, int x)
{
for (int i = k; i < N; i += lowbit(i)) tr[i]++;
}
int quary(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i]++;
}
for (int i = 1; i <= n; i++)
{
add(a[i], 1);
cnt[i] += i - quary(a[i]); //比这个数大的个数
//i是当前树中的数量,quary(a[i])返回树中小于等于a[i]的数的数量
}
memset(tr, 0, sizeof tr);
for (int i = n; i; i--)
{
add(a[i], 1);
cnt[i] += quary(a[i] - 1); //比这个数小的个数
}
long long res = 0;
for (int i = 1; i <= n; i++) res += cnt[i] * (cnt[i] + 1) / 2;
cout << res;
}
有个疑问,希望朋友们可以帮忙答疑解惑;
归并排序代码这部分:
while (i <= mid && j <= r)
if (a[i] <= a[j])
{
//相对于i来说,j 前面的数都比它小, j 前面的数都和 i 交换过
cnt[a[i].y] += j - mid - 1;
temp[k] = a[i];
}
如果a[i] == a[j];那么j以及前面比i小的数的个数应该为j - (mid+1) +1 - 1 = j - mid - 1;
如果a[i] < a[j];那么j以及j前面比i小的数的个数不应该为j - mid吗? 这两种情况不用分开讨论吗?
这段代码是归并排序算法中的一个关键部分,它同时进行排序和计算每个小朋友的交换次数。在归并排序过程中,数组被分为两部分:左半部分(l..mid)和右半部分(mid+1..r),分别是已经排序好的两个子数组。变量i和j分别追踪左半部分和右半部分当前要考虑的元素,k用于构造归并后的数组。
这段代码的逻辑细节如下:
cpp
if (a[i] <= a[j])
{
// 相对于i来说,j 前面的数都比它小, j 前面的数都和 i 交换过
cnt[a[i].y] += j - mid - 1;
temp[k] = a[i];
}
else {
// 相对于j来说,i 后面的数都比它大, i 后面的数都和 j 交换
cnt[a[j].y] += mid - i + 1;
temp[k] = a[j];
}
if (a[i] <= a[j]):当左边子数组的当前元素(身高)小于或等于右边子数组的当前元素时,意味着从左边数组中选取元素是正确的,因为它已经比右边所有未处理的元素小。
cnt[a[i].y] += j - mid - 1;:计算交换次数。a[i].y是原始编号,j是右边数组的当前指针位置,mid + 1是右边数组的开始位置,所以j - mid - 1意味着到目前为止右边数组有多少元素已经被跳过,也就是小朋友i已经被交换了多少次。
else:当右边子数组的当前元素小于左边子数组的当前元素时,由于我们需要将较小的元素移动到正确的位置,但这个元素应该在左边数组的i之前,所以我们将它记入temp数组,并且更新交换次数。
cnt[a[j].y] += mid - i + 1;:同样是计算交换次数。i是左边数组的指针,mid是左边数组的结束位置,所以mid - i + 1是左边数组剩余未处理元素的数量,这些都需要和j交换位置,也即j将移动过这么多的小朋友。
然后两种情况都会移动k索引,并更新相应子数组的指针(i或j)。这样,通过每次移动,我们都能通过递增方式计算每一个小朋友因为排序操作而产生的不高兴次数。这个过程在子数组被完全处理之前会重复进行。
最终,这个合并的过程不但将数组排序,还统计了每次因排序引起的小朋友的位置交换次数,从而可以用来计算他们的不高兴程度。
佬 为什么归并排序中cnt[i] !=cnt[a[i].y]
个人理解:如果是cnt[i]的话,把次数记录在下标i的元素上,在归并排序上,原本下标为i的元素会被改变位置,那么在后面的操作上就不对应了,
用pair,把元素与与次数绑定在一次,改变位置就一起改变
if (a[i] <= a[j])
{
//相对于i来说,j 前面的数都比它小, j 前面的数都和 i 交换过
cnt[a[i].y] += j - mid - 1;
temp[k] = a[i];
}大佬这个怎么理解,a[i]<=a[j]了为什么还会有交换呀
求逆序对的话,只要mid - i + 1;就行了,现在一个逆序对涉及两个小朋友,会使两人数值都增加,mid - i + 1是j交换的次数,那一次交换的同时,i也交换了,所以要算上 j - mid - 1,这是i的交换次数
嗷嗷 感谢大佬
在归并排序的这个应用场景中,cnt[]数组是用来跟踪交换次数的,但它记录的是基于小朋友原始编号的交换次数,而不是基于当前遍历到的位置。这就是为什么cnt[i](表示当前位置i的交换次数)和cnt[a[i].y](表示初始编号为a[i].y的小朋友的交换次数)不同的原因。
数组a[]中的每个元素都是一个pair[HTML_REMOVED]类型,它包含两个信息:身高和编号。a[i].x代表身高,而a[i].y代表小朋友的原始编号(即他们输入时的次序)。
当你在排序和计算交换次数时,你是在按身高重新排列a[]数组,但是交换次数要记录在原始编号上,因为我们最终要计算的是每个小朋友相对于原始位置移动的次数。这就是为什么我们需要使用cnt[a[i].y],它确保我们更新的是正确的交换次数,而不是基于当前位置的交换次数。
此外,cnt[]数组的索引和小朋友的编号是一一对应的,即对于任意小朋友,他们身高排序之前的位置(编号)即是cnt[]数组中的索引。归并排序过程中,我们通过更新a[i].y这个编号对应的交换次数来得到正确的计数。这保证了不管小朋友被移到了什么位置,我们都能跟踪到他们的交换次数,并在最终计算中使用这个数据。
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int N=1e6+10;
int arr[N],t[N];
int temp[N];
int n;
long long sum=0;
void merge_sort(int l,int r)
{
if(l>=r)return;
int mid=l+r>>1;
merge_sort(l,mid);
merge_sort(mid+1,r);
int k=l;
int res=l;
int ans=mid+1;
while(res<=mid&&ans<=r)
{
if(arr[res]<=arr[ans])
{
t[res]+=ans-(mid+1);
temp[k]=arr[res];
}
else {
t[ans]+=mid-res+1;
temp[k]=arr[ans];
}
}
while(res<=mid)
{
t[res]+=r-(mid+1)+1;
temp[k]=arr[res];
}
while(ans<=r)temp[k]=arr[ans];
for(int i=l;i<=r;i)
arr[i]=temp[i];
}
int main(){
cin>>n;
for(int i=0;i[HTML_REMOVED]>arr[i];
merge_sort(0,n-1);
for(int i=0;i<n;i)
sum+=(t[i]+1)*t[i]/2;
cout<<sum<<endl;
}我这个有什么问题吗
%%%
%%%