题解：AT_arc120_c [ARC120C] Swaps 2

· · 题解

前言

闲来无事，写一篇今天校内打模拟赛的题的题解。

简要题意

给一个初始序列以及一个目标序列，每次操作可以选择相邻两个位置交换数值并且向左移动的数加一、向右移动的数减一。求将原序列变成目标序列最少操作次数。

题解

首先可以发现当一个数加一的时候其下标减一，所以不论如何操作所有的 i+a_i 一定都是定值，对于 i+a_i 相同的数不管最后放在哪里都不会影响结果，所以可以对每个不同的 i+a_i 考虑最后的去向。

因为题目要求最小的操作数，所以对于相同的 i+a_i，将原位置与目标位置一一对应一定不劣。于是我们用队列维护每个权值从而确定原位置对应的目标位置。

确定好每个点的终点后我们还要思考如何操作。考虑如果有两个数需要向左边移动，我先将右边的移动到目标位置可能会对靠左的数增加不必要的贡献。所以我们考虑钦定一个移动顺序，我是从左往右考虑终点的，先将终点在最左端的数移动到目标位置，然后再考虑左数第二个，以此类推。

最后就要考虑每完成一次移动对序列的影响。我们将每个数需要移动的距离预处理出来，规定向右为正，反之为负。当我们每次将一个数移动到左边时，我们会将路过的位置上的数向右移一步。这是一个区间加，于是随便用啥东西维护一下即可，时间复杂度 O(n\log n)。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e5 + 5;

int n, a[N], b[N], pos[N], id[N], c[N];
ll res;

map < int , queue < int > > mp;

#define ls x << 1
#define rs ls | 1
ll t[N << 2], tg[N << 2];

inline void upd(int x){t[x] = t[ls] + t[rs];}
void bld(int x, int l, int r){
    if(l == r)return t[x] = c[l], void();
    int mid = l + r >> 1;
    bld(ls, l, mid), bld(rs, mid + 1, r);
}
void pd(int x, int l, int r){
    if(! tg[x])return; int mid = l + r >> 1;
    tg[ls] += tg[x]; tg[rs] += tg[x];
    t[ls] += (mid - l + 1) * tg[x];
    t[rs] += (r - mid) * tg[x];
    tg[x] = 0;
}
void mdf(int x, int l, int r, int ql, int qr, int y){
    if(ql <= l and r <= qr)return tg[x] += y, t[x] += y * (r - l + 1), void();
    int mid = l + r >> 1; pd(x, l, r);
    if(ql <= mid)mdf(ls, l, mid, ql, qr, y);
    if(mid < qr)mdf(rs, mid + 1, r, ql, qr, y);
    upd(x);
}
int qry(int x, int l, int r, int pos){
    if(l == r)return t[x]; int mid = l + r >> 1; pd(x, l, r);
    return pos <= mid ? qry(ls, l, mid, pos) : qry(rs, mid + 1, r, pos);
}

bool cmp(int x, int y){return pos[x] < pos[y];}

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> a[i], mp[a[i] + i].push(i);
    for(int i = 1; i <= n; ++i){
        cin >> b[i];
        if(mp[i + b[i]].empty())return puts("-1"), 0;
        pos[i] = mp[i + b[i]].front(); c[i] = pos[i] - i;
        id[i] = i; mp[i + b[i]].pop();
    }
//  for(int i = 1; i <= n; ++i)cout << c[i] << endl;
    sort(id + 1, id + 1 + n, cmp);
    bld(1, 1, n);
    for(int i = 1; i <= n; ++i){
        int x = qry(1, 1, n, id[i]); res += - x;
        if(id[i] > 1)mdf(1, 1, n, 1, id[i] - 1, - 1);
    }
    cout << res;
    return 0;
}