AtCoder Regular Contest 120 C - Swaps 2(树状数组)

2023-12-26 15:25:15

Score : 500 $500$ points

Problem Statement

Given are two sequences of length N $N$ each: A=(A1,A2,A3,…,AN) $A = (A_{1}, A_{2}, A_{3}, \dots, A_{N})$ and B=(B1,B2,B3,…,BN) $B = (B_{1}, B_{2}, B_{3}, \dots, B_{N})$ .
Determine whether it is possible to make A $A$ equal B $B$ by repeatedly doing the operation below (possibly zero times). If it is possible, find the minimum number of operations required to do so.

Choose an integer i $i$ such that 1≤i<N $1 \leq i < N$ , and do the following in order:
- swap Ai $A_{i}$ and Ai+1 $A_{i + 1}$ ;
- add 1 $1$ to Ai $A_{i}$ ;
- subtract 1 $1$ from Ai+1 $A_{i + 1}$ .

Constraints

2≤N≤2×105 $2 \leq N \leq 2 \times 10^{5}$
0≤Ai≤109 $0 \leq A_{i} \leq 10^{9}$
0≤Bi≤109 $0 \leq B_{i} \leq 10^{9}$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N $N$ 
A1 $A_{1}$  A2 $A_{2}$  A3 $A_{3}$  … $\dots$  AN $A_{N}$ 
B1 $B_{1}$  B2 $B_{2}$  B3 $B_{3}$  … $\dots$  BN $B_{N}$

Output

If it is impossible to make A $A$ equal B $B$ , print -1.
Otherwise, print the minimum number of operations required to do so.

Sample Input 1

3
3 1 4
6 2 0

Sample Output 1

We can match A $A$ with B $B$ in two operations, as follows:

First, do the operation with i=2 $i = 2$ , making A=(3,5,0) $A = (3, 5, 0)$ .
Next, do the operation with i=1 $i = 1$ , making A=(6,2,0) $A = (6, 2, 0)$ .

We cannot meet our objective in one or fewer operations.

Sample Input 2

3
1 1 1
1 1 2

Sample Output 2

-1

In this case, it is impossible to match A $A$ with B $B$ .

Sample Input 3

5
5 4 1 3 2
5 4 1 3 2

Sample Output 3

A $A$ may equal B $B$ before doing any operation.

Sample Input 4

6
8 5 4 7 4 5
10 5 6 7 4 1

Sample Output 4

给出两个数组，每个数组有 n 个数，可以进行如下操作：
将 a 数组中的 a[i]->a[i]+1 与 a[i+1]->a[i+1]-1 然后再交换位置，问最少需要多少次操作可以将 a 数组变为 b 数组

先看一下第 4 组样例该怎么做，

\[8,5,4,7,4,5 \]

想让第一个数变为 10，我们可以让 7 移动到第一个位置上来，也可以让最后一个 5 移动到第一个位置上来，但是就这一步而言让 7 过来是最优的，而 7 前面的 8 5 4，分别要减去 1；
所以现在的思路有了，对于 b 数组中的每一个位置 j，我们只要找到 a 数组中 $a[i]+i-j=b[j]$ 的第一个 $a[i]$ 即可，时间复杂度 $O(n^2)$

这样是远远不够的，我们需要更快速地方法，我们将上式做一个变化

\[a[i]+i=b[j]+j \]

这个式子就很漂亮，这样将 a 和 b 数组同时变为 $(a[i]+i)$ ，
$(b[i]+i)$ 的形式，这样 a ,b 数组就分别变为了

\[9 ,7 ,7 ,11 ,9 ,11 \]

\[11,7,9,11,9,7 \]

这个问题，两个数组相同，求交换多少次可以变成另一个数组，这不就是求 ‘逆序对’ 吗


const int N = 3e5 + 5;

    ll n, m, _;
    int i, j, k;
    int a[N];
    int b[N], c[N];
    map<int, vector<int>> mp;

void add(int x)
{
    for(; x <= n; x += lowbit(x)){
        c[x] ++;
    }
}

int ask(int x)
{
    int ans = 0;
    for(; x; x -= lowbit(x)){
        ans += c[x];
    }
    return ans;
}

signed main()
{
    //IOS;
    while(~ sd(n)){
        rep(i, 1, n) sd(a[i]);
        rep(i, 1, n) sd(b[i]);
        ll ok = 0;
        per(i, 1, n){
            a[i] += i;
            b[i] += i;
            mp[b[i]].pb(i);
            ok += a[i] - b[i];
        }
        rep(i, 1, n){
            int tmp = a[i];
            if(mp[a[i]].empty()){
                ok = 1;
                break;
            }
            a[i] = *mp[a[i]].rbegin();
            mp[tmp].pop_back();
        }
        if(ok){
            puts("-1");
            break;
        }
        ll ans = 0;
        per(i, 1, n){
            ans += ask(a[i]);
            add(a[i]);
        }
        pll(ans);
    }
    return 0;
}

码农公寓