Analysis
不妨先忽略图论，考虑在一条链上选多组点使得每一组点 \(i,j\) 均满足 \(i-j=a_i-a_j\) 。由于没有规定我们选多少组，因此 \(a_i+a_j > 0\) 均对答案产生正贡献，都可以选。
问题是如果一个数可以与多个数匹配，我们该选哪个呢？显然我们贪心地选择贡献最大的。
朴素的做法是将数组从小到大排序，然后倒着搜数组。对于搜到的每个数找它前面有没有可以与其配对的数，如果有多个则取贡献最大的。但是这样复杂度太大，无法接受。
如何优化呢？
不妨换个思路，要求 \(i-j=a_i-a_j\) ，移向得 \(a_i-i=a_j-j\) 。因此 \(a_i-i\) 相同的数都可以任意配对。显然我们优先满足较大的两个数配对，然后再考虑小的。我们只需要对于每一组 \(a_i-i\) 都对其 \(a_i\) 从大到小排序贪心选择即可。
具体实现的时候可以使用 map ，排序可以使用 vector 。考察 STL 熟练度。
代码如下。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#define int long long
using namespace std;
const int N = 500005;
const int INF = 0x3f3f3f3f;
map<int,vector<int> >Edge;
int n;
int a[N];
int T;
bool cmp(int a,int b){return a > b;}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--)
{
int ans = 0;
Edge.clear();
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],Edge[a[i]-i].push_back(a[i]);
for(auto it:Edge)
{
vector <int> v = it.second;
sort(v.begin(),v.end(),cmp);
int a = INF,b = INF;
for(auto i:v)
{
if(a == INF) a =i;
else
{
b = i;
if(a+b > 0)
{
ans += a+b;
a = b = INF;
}
}
}
}
cout<<ans<<endl;
}
}