分治 归并排序和逆序对

板子传送门

对于归并排序，是一种O(n*logn)的一种排序方法，然后归并排序中没有一出现，全部都是l因为他的出发点不一定是 1（当排序右边的时候），对于该次所排序的左右区间，在左右区间的两端的元素分别有序，因为是用的递归，所以是从小区间往大区间来排序的，所以该区间分成的两个区间是一定有序的。

#include<bits/stdc++.h>
using namespace std;
int a[1000],temp[1000];

void midsort(int l,int r)
{
    if(l==r)
        return ;
    int mid=l+r>>1;
    midsort(l,mid);    //该处是从l到mid，因为处理右端时开始的端点不是1
    midsort(mid+1, r);
    int i=l,j=mid+1,k=l;    //该处的k同理上面的l
        while(i<=mid&&j<=r)
        {
            if(a[i]<a[j])
                temp[k++]=a[i++];
            else
                temp[k++]=a[j++];
        }
    while(i<=mid) temp[k++]=a[i++];    //处理剩下的
    while(j<=r) temp[k++]=a[j++];
    for(int i=l;i<=r;i++)
        a[i]=temp[i];
    return ;
}

int main()
{
    std::ios::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    midsort(1,n);
    for(int i=1;i<n;i++)
        cout<<a[i]<<" ";
    cout<<a[n]<<endl;
    return 0;
}

逆序对

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[1000],temp[1000];

ll midsort(int l,int r)
{
    if(l==r)
        return 0;
    int mid=l+r>>1;
    ll ans=midsort(l,mid)+ midsort(mid+1, r);
    int i=l,j=mid+1,k=l;
     while(i<=mid&&j<=r)
        {
            if(a[i]<a[j])
                temp[k++]=a[i++];
            else
            {
                ans+=mid-i+1;
                temp[k++]=a[j++];
            }
        }
    while(i<=mid) temp[k++]=a[i++];
    while(j<=r) temp[k++]=a[j++];         //最后的这一个部分不只是合并最后没走完的数，而且还要合并答案，该处不合并是因为当j有剩余的时候，i已经走到了mid+1，此时根据表达式不更新答案
    for(int i=l;i<=r;i++)
        a[i]=temp[i];
    return ;
}

int main()
{
    std::ios::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    midsort(1,n);
    for(int i=1;i<n;i++)
        cout<<a[i]<<" ";
    cout<<a[n]<<endl;
    return 0;
}

附上一个更新答案的题目

#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define std std::ios::sync_with_stdio(0)
#define mem(a,b) memset(a,b,sizeof(a));
const int INF = 0x3f3f3f3f;

void read(ll& x)
{
	ll f = 1;         //f为符号位
	x = 0;
	char s = getchar();          //读入一个字符
	while (s > '9' || s < '0')      //处理空格。换行什么的，并且读入符号
	{
		if (s == '-')
			f = -1;
		s = getchar();
	}
	while (s >= '0' && s <= '9')     //不断地读入数字字符来计算得到数字
	{
		x = x * 10 + s - '0';
		s = getchar();
	}
	x *= f;               //乘以符号即可得到数字
}

const int maxn = 5e4 + 10;
struct vx
{
	ll v, x;
}a[maxn],temp[maxn];
ll sum[maxn];

ll solve(int l, int r)
{
	if (l == r)
		return 0;
	int mid = l + r >> 1;
	ll ans = solve(l, mid) + solve(mid + 1, r);
	
	sum[l - 1] = 0;

	int i = l, j = mid + 1;

	for (; i <= mid; i++)
		sum[i] = sum[i - 1] + a[i].x;
	i = l, j = mid + 1;
	int k = l;
	while (i <= mid&&j <= r)
	{
		if (a[i].x <a[j].x)
			temp[k++] = a[i++];
		else
		{
			ans += a[j].v * (a[j].x * (i - l) - sum[i - 1] + sum[mid] - sum[i - 1] - a[j].x * (mid - i + 1));
			temp[k++] = a[j++];
		}
	}
	while (i <= mid)
		temp[k++] = a[i++];
	while (j <= r)
	{
		ans += a[j].v * (a[j].x * (i - l) - sum[mid]);
		temp[k++] = a[j++];
	}
	for (i = l; i <= r; i++)
		a[i] = temp[i];
	return ans;
}


int cmp(vx& a, vx& b)
{
	return a.v < b.v;
}
int main()
{
	int n;
	std;
	cin >> n;

	for (int i = 1; i <= n; i++)
		read(a[i].v), read(a[i].x);

	sort(a + 1, a + n + 1, cmp);

	ll ans = solve(1, n);

	cout << ans << '\n';
	return 0;
}

对于该题的表达式有max(a,b)取大值的情况，我们选择直接对该元素进行排序然后就可以化简表达式，然后对于算答案贡献的时候，我一开始的思路是直接强行枚举的，找到第一个左区间的x是大于右区间的时候，利用前缀和进行处理，但是会TLE，而联想到归并排序的时候，也是会处理一个大小于的情况，所以选择使用归并排序来对x进行排序的同时更新答案。