前置知识
归并排序（一维偏序）
推荐写法：https://www.cnblogs.com/didiao233/p/17986130 第1题 归并排序 查看测评数据信息
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1-1e9 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
输入/输出例子1
输入：
5
3 1 2 4 5
输出：
1 2 3 4 5
样例解释
无
一维偏序：归并（T1）
看一下讲义就行，这是根据讲义写出的代码，可能有点抽象。
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n, a[N], tmp[N], tmp2[N];
void merge(int L, int R)
{
if (L>=R) return ;
int mid=L+R>>1, m=0, m2=0, idx=0, idx2=0;
merge(L, mid);
merge(mid+1, R);
for (int i=L; i<=mid; i++) tmp[++m]=a[i];
for (int i=mid+1; i<=R; i++) tmp2[++m2]=a[i];
tmp[++m]=tmp2[++m2]=2e9, idx=idx2=1;
for (int i=L; i<=R; i++)
{
if (tmp[idx]<tmp2[idx2]) a[i]=tmp[idx++];
else a[i]=tmp2[idx2++];
}
}
int main()
{
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%d", &a[i]);
merge(1, n);
for (int i=1; i<=n; i++) printf("%d ", a[i]);
return 0;
}
逆序对（二维偏序）
推荐写法：https://www.cnblogs.com/didiao233/p/17986130 第2题 逆序对 查看测评数据信息
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
1≤n≤100000，
数列中的元素的取值范围 [1,1e9]。
输出格式
输出一个整数，表示逆序对的个数。
输入/输出例子1
输入：
6
2 3 4 5 6 1
输出：
5
样例解释
无
二维偏序：逆序对（T2）
i<j 且 a[i]>a[j]
分3类，左，右，跨越左右
左，右很好求，分成子问题去求就好了，关键在于如何求跨越左右的影响？
我们就看左边对右边的影响就行了，因为此时默认满足了i<j的条件，只用考虑满足 a[i]>a[j] 即可。
此时，经过不断归并，左边的数经过排序会单调递增，右边的数也会单调递增。
所以在双指针的时候顺带判断一下即可。
只要当前的数a[i]>a[j]，那么i后面的数也满足这个条件，所以答案+=mid-i+1即可。
同上，看讲义写出来的：
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n, a[N], tmp[N], tmp2[N];
long long merge(int L, int R)
{
if (L>=R) return 0;
int mid=L+R>>1, m=0, m2=0, idx=0, idx2=0;
long long res=merge(L, mid)+merge(mid+1, R);
for (int i=L; i<=mid; i++) tmp[++m]=a[i];
for (int i=mid+1; i<=R; i++) tmp2[++m2]=a[i];
tmp[++m]=tmp2[++m2]=2e9, idx=idx2=1;
for (int i=L; i<=R; i++)
{
if (tmp[idx]<=tmp2[idx2]) a[i]=tmp[idx++];
else a[i]=tmp2[idx2++], res+=mid-(L+idx-1)+1;
}
return res;
}
int main()
{
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%d", &a[i]);
printf("%lld", merge(1, n));
// for (int i=1; i<=n; i++) printf("%d ", a[i]);
return 0;
}
距离（二维偏序进阶）
第3题 距离 查看测评数据信息
高一小z刚学习物理的匀速直线运动，所以他来到机房做一道关于匀速直线运动的信息学题目，在一条无限长的直线上有n个点，每个点有如下属性：
（1）第i个点在数轴上的位置是d(i)
（2）每个点有一个初始的速度v(i)
（3）每个点有一个运动的方向，当v(i)为正数时，代表点i从初始位置向右进行匀速直线运动，反之则向左进行匀速直线运动。如t秒后，i点所在的位置是d（i）+v（i）*t
令f（i，j）表示i点和j点在任意时刻可能存在的距离的最小值。
现在请帮小z求出所有的f(i,j)的总和（其中1<=i<j<=n）
输入格式
第一行一个整数n，表示数轴上有n个点（2<=n<=2e5）
第二行n个整数，x(1),x(2),x(3),...x(n-1),x(n)
第三行n个整数，v(1),v(2),v(3),...v(n-1),v(n)
1<=x(i)<=1e8
-1e8<=v(i)<=1e8
输出格式
一个整数，表示最大值
输入/输出例子1
输入：
3
1 3 2
-100 2 3
输出：
3
样例解释
无
可以先考虑分类。也就是追得上和追不上的问题。
d[i]<d[j] && v[i]>v[j]，追得上。答案：0
d[i]<d[j] && v[i]<=v[j] 追不上，答案： d[j]-d[i]
d[i]>d[j] && v[i]>=v[j]，这里是和上面的情况一样的，相当于是d，v都取反，计算答案也取反了，不用再单独去算。
也就转换成了求二维偏序。
按v排序，v[i]<=v[j] 的条件就满足了。
对于d[i]<d[j]的条件，分类就行了
1.左边
2.右边
3.跨越左右
考虑第3类，同T2。
因为归并的时候已经让左边，右边变成单调递增的了，所以在求这个条件的时候用双指针即可。
如果d[i]<d[j]，那么对于j后面的数，此时的i也满足的！
所以答案+=R-j+1（用前缀和优化，也就是d[j]-d[i] + d[j+1]-d[i]这样）
如果按照此写法，排序的时候记得按w为第二关键字排序，否则会进不去计算res的条件
if (a[i].x<=a[j].x) res+=(s[R]-s[j-1])-a[i].x*(R-j+1), tmp[++m]=a[i++].x;
或者说换一种思路：找第一个d[i]>d[j]，那么对于i前面的数肯定都<d[j]，所以答案+=i-L+1（用前缀和优化，同上。）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct node
{
ll x;
int v;
}a[N];
int n, tmp[N], m=0;
ll s[N];
bool cmp(node a, node b)
{
if (a.v==b.v) return a.x<b.x;
return a.v<b.v;
}
ll cdq(int L, int R)
{
if (L>=R) return 0;
int mid=L+R>>1, i=0, j=0;
ll res=cdq(L, mid)+cdq(mid+1, R);
for (int i=L; i<=R; i++) s[i]=s[i-1]+a[i].x;
m=0, i=L, j=mid+1;
while (i<=mid && j<=R)
{
if (a[i].x<=a[j].x) res+=(s[R]-s[j-1])-a[i].x*(R-j+1), tmp[++m]=a[i++].x;
else tmp[++m]=a[j++].x;
}
while (i<=mid) tmp[++m]=a[i++].x;
while (j<=R) tmp[++m]=a[j++].x;
for (int i=L, j=1; i<=R, j<=m; i++, j++) a[i].x=tmp[j];
return res;
}
int main()
{
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%lld", &a[i].x);
for (int i=1; i<=n; i++) scanf("%d", &a[i].v);
sort(a+1, a+1+n, cmp);
printf("%lld", cdq(1, n));
return 0;
}
/*
2
2 1
2 2
*/
标签：输出,数列,int,分治,mid,整数,CDQ,逆序 From： https://www.cnblogs.com/didiao233/p/18449152