`2024/3/6
1215.小朋友排队
题意大概是将乱序的数字排成有序递增的，但是只能移动相邻的两个元素。
代码貌似是求逆序对。

pass(不会暂定)

2024/3/7
这个题算是归并排序求逆序数的延伸了，原因是由于我们要求出每个小朋友应该换多少次，而不是求出一共至少需要多少次变为升序。
那么应该求出每个小朋友的交换次数，我们可以知道当前小朋友需要与小朋友前面的比他大的交换，与排在他后面的比他小的交换。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010;
int n;
PII q[N], tmp[N];
int sum[N];
ll res;
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 k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i].x <= q[j].x) {
            sum[q[i].y] += j - (mid + 1);
            //此时j可能不是第二个划分中的第一个了，
            //说明此时mid+1到j之间的都是比q[i]小的
            //这些都要与q[i]换一次位置
            tmp[k++] = q[i++];
        }
        else {
            sum[q[j].y] += mid - i+1;
            //与上面同理
            tmp[k++] = q[j++];
        }
    }
    while (i <= mid) {
        sum[q[i].y] += j - mid - 1;
        tmp[k++] = q[i++];
    }
    while (j <= r) {
        tmp[k++] = q[j++];
    }
     for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        scanf("%d", &q[i].x);
        q[i].y = i;   //保留i的位置，防止待会归并排序时候不知道i原来的位置
    }
    merge_sort(1, n);
    for (int i = 1;i <= n;i++) {
        res += (ll)sum[i] * (sum[i] + 1) / 2;
    }
    cout << res << endl;
}

2024/3/6
1224.交换瓶子
将乱序的数字排成有序递增的，能移动任意两个元素。

我们连接的方式是把我们当前的位置的a[i]连向我们本该在的位置的a[i]，（也可以理解为每个i都连向它的a[i]，乱序的时候）
每一次环内的两个点互相交换，该环就会分裂成两个环，环外的两个点交换，两个环就会合并成为一个环。

pass(代码我也不太会)

两个题有点相似，记录一下，类比学习。`