C++ 代码
/*
任意时刻的逆序对直接统计肯定慢,可以根据前缀和统计
(最后)剩下k-1个元素的时刻的逆序对,
肯定包含在剩下k个元素的时刻的逆序对数量之中
只要统计最后第k个(逆序时间戳)要删除的元素与前后元素形成的逆序对数量即可
求前缀和即可
如何求最后第k个(逆序时间戳)与左右元素形成的逆序对数量呢?
利用三维偏序思想(CDQ分治){编号,数值,时间戳}
编号本身就是左小右大,数值大小关系,累计晚删除点
在对数值归并排序(升序)过程中统计每个点与晚删除点的逆序对
双指针算法完成O(n),BIT(logn)
分成两种情况
我(j)在右半边,看左半边(i)有多少个比我大的(时间戳比我小才统计(BIT))
我(i)在左半边,看右半边(j)有多少个比我小的(时间戳比我小才统计(BIT))
统计完之后归并(当前区间按照数值升序),方便后面双指针讨论大小关系
比如 左半 1 3 5 7,右半是2 4 6 8
先统计右半2 4 6 8,对于每个数值,看左半有哪几个比我大的
对于8,左半没有比8大的
对于6,左半有7大
对于4,左半有7、5大
对于2,左半有7、5、3大
注意,不是有几个大的就是逆序对数量,
如果比自己大但早于自己被删除,就不能统计在内
只有比自己晚删除的才能统计在内
所以要将满足条件的数值的逆序时间戳放入BIT
看比我晚删除的有几个,才可以累计到我被删除前与我形成逆序对的数量之中
(下面统计左半,与右半相似 )
后统计左半1 3 5 7,对于每个数值,看右半有哪几个比我小的
对于1,左半没有比1小的
对于3,左半有2小
对于5,左半有1、3小
对于7,左半有1、3、5小
注意,不是有几个小的就是逆序对数量,
如果比自己小但早于自己被删除,就不能统计在内
只有比自己晚删除的才能统计在内
所以要将满足条件的数值的逆序时间戳放入BIT
看比我晚删除的有几个,才可以累计到我被删除前与我形成逆序对的数量之中
*/
#include<...>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
struct Info{
int a, t, res;
//当前数值
//删除时间(递减)
//该元素删除前与剩余元素形成的逆序对数量
} q[N], w[N]; //原始信息、归并临时使用
int tr[N], pos[N]; //树状数组,删除元素的下标
LL ans[N]; //逆序对数量可能超过整型范围
int lowbit(int x){
return x & -x;
}
void add(int x, int v){
for(int i = x; i < N; i += lowbit(i)) tr[i] += v;
}
int query(int x){
int ret = 0;
for(int i = x; i; i -= lowbit(i)) ret += tr[i];
return ret;
}
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 i = mid, j = r;
while(i >= l && j > mid){
if(q[i].a > q[j].a) add(q[i].t, 1), i--;
else q[j].res += query(q[j].t - 1), j--;
//累计严格小于q[j].t的个数
//(将来删除的,而且在j的左侧的,值比j的值大的数量)
}
while(j > mid) q[j].res += query(q[j].t - 1), j--;
//将没有走完的j依次走完(累计答案)
for(int k = mid; k > i; k--) add(q[k].t, -1); //清空BIT
}//我(j)在右半边,看左半边(i)有多少个比我大的(时间戳比我小才统计(BIT))
{
int i = l, j = mid + 1;
while(i <= mid && j <= r){
if(q[i].a > q[j].a) add(q[j].t, 1), j++;
else q[i].res += query(q[i].t - 1), i++;
//累计严格小于q[i].t的个数
//(将来删除的,而且在i的右侧的,值比i的值小的数量)
}
while(i <= mid) q[i].res += query(q[i].t - 1), i++;
//将没有走完的i依次走完(累计答案)
for(int k = mid + 1; k < j; k++) add(q[k].t, -1); //清空BIT
}//我(i)在左半边,看右半边(j)有多少个比我小的(时间戳比我小才统计(BIT))
{
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r){
if(q[i].a < q[j].a) w[k++] = q[i++];
else w[k++] = q[j++];
}
while(i <= mid) w[k++] = q[i++];
while(j <= r) w[k++] = q[j++];
for(int i = l, k = 0; i <= r; i++, k++) q[i] = w[k];
} //merge,虽然以上分治处理已经nlogn了,这里其实可以sort,
//但变成n可以稍微减少用时,防止卡常
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &q[i].a); //原始信息(数值)
pos[q[i].a] = i; //记录该数值所在位置
}
for(int i = 1, j = n; i <= m; i++){
int a;
scanf("%d", &a); //要删除的数值
q[pos[a]].t = j--;
//递减时间戳(为了方便统计序列中时间戳小的前缀数量(BIT))
}
for(int i = 1, j = n - m; i <= n; i++){
if(q[i].t) continue;
q[i].t = j--;
} //题中没有要求删除的数字也给一个时间戳(输出时只输出前m个)
merge_sort(1, n);
//对元素升序,期间根据时间戳BIT累计与当前元素形成的逆序对
//根据删除时间点涉及元素计算与剩余元素的逆序对
//(左边比我大,或者,右边比我小)
for(int i = 1; i <= n; i++) ans[q[i].t] = q[i].res;
//这里按照删除时间顺序记录到ans数组,方便求前缀和
for(int i = 2; i <= n; i++) ans[i] += ans[i - 1];
//根据递减时间戳,最后k个时间形成的逆序对总数
//就是k时间戳时的逆序对数量
//比如原始序列是1 5 3 4 2,删除要求是5 1 4 2
//假设3是最后一个离开队伍的,则删除顺序是5 1 4 2 3
//删除顺序5 1 4 2 3离开队伍的时间戳为5 4 3 2 1(逆序赋值)
//(5戳)数字5离开时与其形成逆序对数量为0(左比我大) + 3(右比我小)= 3
//(4戳)数字1离开时与其形成逆序对数量为0(左比我大) + 0(右比我小)= 0
//(3戳)数字4离开时与其形成逆序对数量为0(左比我大) + 1(右比我小)= 1
//(2戳)数字2离开时与其形成逆序对数量为1(左比我大) + 0(右比我小)= 1
//(1戳)数字3离开时与其形成逆序对数量为0(左比我大) + 0(右比我小)= 0
//k-1 ~ 1 戳时的逆序对数量,在k戳时肯定存在
//则k戳时的答案,就是1 ~ k戳时的逆序对数量之和
//利用前缀和求值
for(int i = n; i > n - m; i--){
printf("%lld\n", ans[i]);
} //输出n戳、n-1戳、……,前m个时间戳时候的答案
return 0;
}