Description.
给定一个长度为 \(n(n\le 2\times 10^5)\) 的序列 \(\{a_i\}\)，其中 \(\forall i\in[1,n],a_i\le2.5\times 10^6\)。
找到一组 \((x,y,z,w)\)，使得 \(a_x+a_y=a_z+a_w\)。
Solution1.
完全没想到啊。
首先，我们有个 \(O(n^2)\) 的暴力。
就是枚举 \((a,b)\)，如果出现过，那就直接结束了。
否则就塞入一个桶里，复杂度是 \(O(n^2)\) 的，可以通过此题。
设一个势能函数是 \(\phi(i)\) 桶中还没数的个数。
每一次尝试插入的过程，有以下几种情况：
- 桶中 \(a_i+a_j\) 没出现过，此时 \(\phi(i)\) 自减
- 桶中 \(a_i+a_j\) 出现过了，此时结束
- \(i,j\) 出现过但是有重复不能取，此时最多执行 \(O(n)\) 次。
同时，因为如果 \(\phi(i)\) 已经减少到 \(0\) 了，必会跳到 \(2\) 或 \(3\)。
所以我们证明了复杂度是 \(O(\min(n^2,V))\) 的。
Solution2.
换一个方向，其实本质相同。
我们尝试证明一个结论：在 \(3500\) 个数中必定存在 \(a_x+a_y=a_z+a_w\)。
因为 \(a_x+a_y\) 总个数已经达到 \(3500^2\) 了，必定存在重复。
所以也做完了
Coding.
采用第一种实现方式的弱鸡代码
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了……{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<‘0‘||c>‘9‘;c=getchar()) if(c==‘-‘) f=1;
for(;c>=‘0‘&&c<=‘9‘;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
if(f) x=-x;
}/*}}}*/
int n,a[200005];pair<int,int>p[5000005];
int main()
{
read(n);for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
{
int s=a[i]+a[j];if(!p[s].first) {p[s]=make_pair(i,j);continue;}
int x=p[s].first,y=p[s].second;if(x==i||y==j||x==j||y==i) continue;
return printf("YES\n%d %d %d %d\n",x,y,i,j),0;
}
return puts("NO"),0;
}