题意：两排火柴，定义$cost=sum_{i=1}^{n}(b_i-a_i)^2$其中$b_i,a_i$为火柴的高度，
每相邻两个火柴可以交换，问最少经过几次交换，可以使cost最小（高度无重复）
输出最小交换次数。
思路：很明显，把两个序列排序，这样的对应求得的cost一定是最小的（也就是离散化后对应数都相等）
那么，问题转化为了：给你一个初始序列和一个目标序列，每次交换相邻两个元素，问最小交换次数。。。
离散化后，相当于给你一个乱序，把它变成升序。。。逆序对啊。。。
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define int long long #define olinr return #define _ 0 #define love_nmr 0 #define DB double int c[105050]; struct node { int id; int data; friend bool operator < (const node &x,const node &y) { return x.data<y.data; } }; int s[105050]; int n; inline int lowbit(int x) { return ((x)&(-x)); } inline void add(int pos) { for(int i=pos;i<=n;i+=lowbit(i)) c[i]++; } inline int query(int pos) { int re=0; for(int i=pos;i;i-=lowbit(i)) re+=c[i]; return re; } inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } int ans; node a[105050]; node b[105050]; signed main() { n=read(); for(int i=1;i<=n;i++) { a[i].data=read(); a[i].id=i; } for(int i=1;i<=n;i++) { b[i].data=read(); b[i].id=i; } sort(a+1,a+n+1); sort(b+1,b+n+1); for(int i=1;i<=n;i++) s[a[i].id]=b[i].id; for(int i=1;i<=n;i++) { add(s[i]); ans+=i-query(s[i]); ans%=99999997; } put(ans%99999997); olinr ~~(0^_^0)+love_nmr; }