P1966 火柴排队
很好的逆序对板子题;
求的是(x1-x2)*(x1-x2)的最小值;
x1*x1+x2*x2-2*x1*x2
让x1*x2最大即可;
可以证明将b,c数组排序后,一一对应的状态是最大的;
ac+bd<ad+bc
ac-ad<bc-bd
a*(c-d)<b*(c-d)//c-d<0
a>b(???)
逆序对合并时一定要加等号!!要判断q1是否超出mid!!!(爆零体验);
归并写法
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+;
const int mo=;
struct node
{
int x,id;
}b[maxn];
node c[maxn];
int n;
bool cmp(node qw,node we)
{
return qw.x<we.x;
}
int a[maxn];
int tmp[maxn];
int ans;
void work_sort(int l,int r)
{
if(l==r) return ;
int mid=(l+r)>>;
work_sort(l,mid);
work_sort(mid+,r);
int q1=l,q2=mid+;
for(int i=l;i<=r;i++)
{
if((a[q1]<=a[q2]&&q1<=mid)||q2>r)
{
tmp[i]=a[q1++];
}
else
{
ans+=mid-q1+;
ans%=mo;
tmp[i]=a[q2++];
}
}
for(int i=l;i<=r;i++) a[i]=tmp[i];
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) {scanf("%d",&b[i].x);b[i].id=i;}
for(int i=;i<=n;i++) {scanf("%d",&c[i].x);c[i].id=i;}
sort(b+,b+n+,cmp);
sort(c+,c+n+,cmp);
for(int i=;i<=n;i++)
{
a[b[i].id]=c[i].id;
}
work_sort(,n);
printf("%d\n",ans);
return ;
}
树状数组写法
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+;
const int mo=;
struct node
{
int x,id;
}a[maxn];
node c[maxn];
int n;
int d[maxn];
bool cmp(node qw,node we)
{
return qw.x<we.x;
}
int b[maxn];
void add(int x,int y)
{
for(;x<=n;x+=x&(-x)) b[x]=(b[x]+y)%mo;
} int query(int x)
{
int sum=;
for(;x;x-=x&(-x)) sum=(sum+b[x])%mo;
return sum;
}
int ans;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) {scanf("%d",&a[i].x);a[i].id=i;}
for(int i=;i<=n;i++) {scanf("%d",&c[i].x);c[i].id=i;}
sort(a+,a+n+,cmp);
sort(c+,c+n+,cmp);
for(int i=;i<=n;i++) d[a[i].id]=c[i].id;
for(int i=;i<=n;i++)
{
add(d[i],);
ans+=i-query(d[i]);
ans%=mo;
}
printf("%d",ans);
return ;
}