设 Alice 取的位置为 \(i,j,k\) 且 \(i<j<k\)，则 Bob 的最优策略有两种：取 \(n\) 或 \(k\)。为了使 Alice 必胜，必须同时满足 \(a_i+a_j+a_k>a_n,a_i+a_j>a_k\)。枚举 \(i,j\)，显然满足两个条件的 \(k\) 都是一段连续的区间。分别二分算出两个区间的边界，那么区间的交集即为合法的 \(k\)。时间复杂度 \(O(\sum(n^2\log n))\)。
#include<iostream>
#include<cstdio>
#define N 5010
using namespace std;
int n,a[N];
long long ans;
void solve(){ans=0;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){for(int j=i+1;j<=n-1;j++){int l=j+1,r=n,mid,ans1=n,ans2=j+1;if(a[i]+a[j]<=a[j+1])continue;while(l<=r){mid=(l+r)/2;if(a[i]+a[j]+a[mid]>a[n])ans1=mid,r=mid-1;else l=mid+1;}l=j+1,r=n;while(l<=r){mid=(l+r)/2;if(a[i]+a[j]>a[mid])ans2=mid,l=mid+1;else r=mid-1;}if(ans2>=ans1) ans+=ans2-ans1+1;}}cout<<ans<<'\n';
}
int main(){int T;cin>>T;while(T--)solve();return 0;
}