XTU 1250 Super Fast Fourier Transform

时间:2025-03-15 18:33:01

$2016$长城信息杯中国大学生程序设计竞赛中南邀请赛$H$题

排序,二分。

对$a$数组,$b$数组从小到大进行排序。

统计每一个$a[i]$作为较大值的时候与$b[i]$对答案的贡献。反过来再统计以$b[i]$为较大值时与$a[i]$对答案的贡献。

以前者举例说明:

观察这个:$⌊\sqrt {|a[i] - b[j]|}⌋ $,按照题目中给出的范围,这个东西最大只有$1000$。

也就是说,我们在计算一个$a[i]$与$b[j]$对答案的贡献时候,不用从$1$到$m$枚举$j$,因为肯定是一段一段相同的,所以分段计算即可。二分一下就可以分段计算了。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-; const int maxn=;
int n,m;
int a[maxn],b[maxn]; int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=m;i++) scanf("%d",&b[i]);
sort(a+,a++n); sort(b+,b++m); LL ans=;
for(int i=;i<=n;i++)
{
int L=,R=m,pos=-;
while(L<=R)
{
int mid=(L+R)/;
if(b[mid]<a[i]) L=mid+,pos=mid;
else R=mid-;
}
if(pos==-) continue; int now=, p;
while(now<=pos)
{
int num=(int)(eps+sqrt(1.0*(a[i]-b[now])));
L=now,R=pos;
while(L<=R)
{
int mid=(L+R)/;
int tmp=(int)(eps+sqrt(1.0*(a[i]-b[mid])));
if(tmp<num) R=mid-;
else L=mid+,p=mid;
}
ans=ans+(LL)(p-now+)*(LL)num;
now=p+;
}
} for(int i=;i<=m;i++)
{
int L=,R=n,pos=-;
while(L<=R)
{
int mid=(L+R)/;
if(a[mid]<b[i]) L=mid+,pos=mid;
else R=mid-;
}
if(pos==-) continue; int now=, p;
while(now<=pos)
{
int num=(int)(eps+sqrt(1.0*(b[i]-a[now])));
L=now,R=pos;
while(L<=R)
{
int mid=(L+R)/;
int tmp=(int)(eps+sqrt(1.0*(b[i]-a[mid])));
if(tmp<num) R=mid-;
else L=mid+,p=mid;
}
ans=ans+(LL)(p-now+)*(LL)num;
now=p+;
}
}
cout<<ans<<endl;
}
return ;
}