[NOIP2013]火柴排队（逆序对）

题目

思路

逆序对只会猜结论

显然需要先猜个结论：(a)数列第(i)大对应(b)数列第(i)大时平方和有最小值

通过交换法，需证明：((b_i-a_j)^2+(b_j-a_i)^2 > (b_i-a_i)^2+(b_j-a_j),(j<i))

上式化简得：(a_j<a_i)，显然成立

设(pa_i)表示(i)这个数在(a)数列的哪个位置，(pb_i)同理

设数列(b_{pa_i}=pb_i)，由于需要位置对齐，需要(b_{pa_i}=pa_i)，即(b_i=i)

问题变成求b序列经过多少次交换变成有序序列

显然逆序对

Code

#include<bits/stdc++.h>
#define N 200005
#define lowbit(x) ((x)&(-(x)))
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
const ll mod = 99999997; 
int n,b[N],c[N];
struct Node
{
	int a,loc;
}A[N],B[N];

template <class T>
void read(T &x)
{
	char c; int sign=1;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
	while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
bool cmp(Node a,Node b) { return a.a<b.a; }
void update(int x,int v) { for(;x<N;x+=lowbit(x)) c[x]+=v; }
int query(int x) { int ret=0; for(;x;x-=lowbit(x)) ret+=c[x]; return ret; } 
int main()
{
	read(n);
	for(int i=1;i<=n;++i) read(A[i].a),A[i].loc=i;
	for(int i=1;i<=n;++i) read(B[i].a),B[i].loc=i;
	sort(A+1,A+n+1,cmp);
	sort(B+1,B+n+1,cmp);
	for(int i=1;i<=n;++i) b[A[i].loc]=B[i].loc;
	ll ans=0;
	for(int i=n;i>=1;--i)
	{
		ans=(ans+query(b[i]-1))%mod;
		update(b[i],1);
	}
	cout<<ans<<endl;
	return 0;
}