洛谷 CF429D Tricky Function（平面最近点对，分治）
传送门
解题思路
首先看g函数的求法，很显然是个前缀和，于是题目就变成了求(i-j)^2+(s[i]-s[j])^2的最小值，所以就变成了求平面最近点对。
注意这里没有根号，为此还sb般地询问了Candy？大佬。
然后分治求一下就ok了。
欣赏一下cf强大的测试数据吧（满满的全是绿色）：
AC代码
1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<queue> 8 #include<set> 9 #include<map> 10 #include<vector> 11 #include<iomanip> 12 #include<ctime> 13 #include<stack> 14 using namespace std; 15 const int maxn=100005; 16 struct node{ 17 long long x,y; 18 }p[maxn],q[maxn]; 19 bool cmp(const node &a,const node &b){ 20 return a.x<b.x; 21 } 22 long long dis(const node &a,const node &b){ 23 return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); 24 } 25 int n,a[maxn]; 26 long long divide(int l,int r){ 27 if(l==r){ 28 return 1LL<<60; 29 } 30 int mid=(l+r)>>1,p1=l,p2=mid+1,tot=0; 31 int midx=p[mid].x; 32 long long d=min(divide(l,mid),divide(mid+1,r)); 33 while(p1<=mid||p2<=r){ 34 if(p1<=mid&&(p2>r||p[p1].y<p[p2].y)){ 35 q[++tot]=p[p1++]; 36 }else{ 37 q[++tot]=p[p2++]; 38 } 39 } 40 for(int i=1;i<=tot;i++){ 41 p[l+i-1]=q[i]; 42 } 43 tot=0; 44 for(int i=l;i<=r;i++){ 45 if((p[i].x-midx)*(p[i].x-midx)<=d){ 46 q[++tot]=p[i]; 47 } 48 } 49 for(int i=1;i<=tot;i++){ 50 for(int j=i-1;j>0&&(q[i].y-q[j].y)*(q[i].y-q[j].y)<=d;j--){ 51 d=min(d,dis(q[i],q[j])); 52 } 53 for(int j=i+1;j<=tot&&(q[j].y-q[i].y)*(q[j].y-q[i].y)<=d;j++){ 54 d=min(d,dis(q[i],q[j])); 55 } 56 } 57 return d; 58 } 59 int main() 60 { 61 cin>>n; 62 for(int i=1;i<=n;i++){ 63 scanf("%d",&a[i]); 64 p[i].x=i; 65 p[i].y=p[i-1].y+a[i]; 66 } 67 sort(p+1,p+n+1,cmp); 68 cout<<divide(1,n)<<endl; 69 return 0; 70 }