P1966 火柴排队

树状数组的简单练习题目

题目要求最小化 \(\sum(a_i-b_i)^2\) 可以转化成 a数组中第K大的数要和b数组中第K大的数在同一个位置，所以先做一手离散化

然后令\(pos[brr[i]] = i\) pos数组中存储的是 b数组值所对应的位置

\(new[i] = pos[arr[i]]\) new数组中存储的是 a数组值在b数组值中对应的位置

\(对new[i]求逆序对\)

假设 $b[i] = $ {\(5,3,4,2,1\)}

有 \(a[i] =\) {\(4,3,5,2,1\)}

\(pos[i]=\) {\(5,4,2,3,1\)}

\(new[i]=\) {\(3,2,1,4,5\)}

最后就是要把这个顺序给他升序一下 使得\(new[i] = i\) 说明此时a数组完全等于b数组

这个操作次数就等于new序列的逆序对个数

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iostream>
#define lowbit(a) a&(-a)
using namespace std;
const int maxn = 1e5+5;
const int mod = 1e8-3;
int N;
long long arr[500005], brr[500005], Trarr[500005], sorting[2][500005], Newarr[500005], pos[500005];
;
void add(int x, long long val){
    while(x <= N){
        Trarr[x] += val;
        x += lowbit(x);
    }
    return;
}
long long getsum(int x){
    long long ans = 0;
    while(x){
        ans += Trarr[x];
        x -= lowbit(x);
    }
    return ans;
}
signed main(){
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    scanf("%d", &N);
    for(int i = 1; i <= N; i++) scanf("%lld", &arr[i]);
    for(int i = 1; i <= N; i++){
        scanf("%lld", &brr[i]);
        sorting[0][i] = arr[i];
        sorting[1][i] = brr[i];
    }
    sort(sorting[0]+1, sorting[0]+1+N);
    sort(sorting[1]+1, sorting[1]+1+N);
    int lena = unique(sorting[0]+1, sorting[0]+1+N) - sorting[0] - 1;
    int lenb = unique(sorting[1]+1, sorting[1]+1+N) - sorting[1] - 1;
    for(int i = 1; i <= N; i++){
        arr[i] = lower_bound(sorting[0]+1, sorting[0]+1+lena, arr[i]) - sorting[0];
        brr[i] = lower_bound(sorting[1]+1, sorting[1]+1+lenb, brr[i]) - sorting[1];
        pos[brr[i]] = i;
    }
    for(int i = 1; i <= N; i++) Newarr[i] = pos[arr[i]];
    long long ans = 0;
    for(long long i = 1; i <= N; i++){
        add(Newarr[i], 1);
        ans = (ans + (i-getsum(Newarr[i]))) % mod;
    }
    printf("%lld", ans);
end:
    cerr << "Time Used: " << clock() - c1 << "ms" << endl;
    return 0; 
}