题解：AT_abc417_c [ABC417C] Distance Indicators

题意

给定一个长度为 $N(1 \le N \le 2 \times 10 ^ 5)$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$。 找出有多少对整数 $(i,j)(1 \le i < j \le N)$ 满足 $j-i=A_i+A_j$。

分析

首先可以想到时间复杂度为 $O (N ^ 2)$ 的暴力做法，在 $2 \times 10 ^ 5$ 的情况下显然会因为超时而无法通过，

分析条件，可以发现原式 $j - i = A_i + A_j$ 可以通过加法交换律与加法性质（既加一个数等于减这个数的相反数）得到等价的新式 $j - i = A_j - ( - A_i)$。

得到新式后，又可以根据新式推导出第二个式子 $j - A_j = i + A_i$，这样就可以把问题简化成有多少对整数 $(i,j)$ 满足 $j - A_j = i + A_i$，而 $j - A_j$ 和 $i + A_i$ 这两种值是可以预处理出来的，于是便有了以下代码。

code

#define ll long long
ll a[10000000];
ll miat[10000000],minu[10000000];//上文提到的 "i+Ai" 与 "j-Aj"
map<ll,queue<ll>>mp;
int n;
int main(){
  	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		miat[i]=i+a[i];//存储当前位置的"i+Ai"
		minu[i]=i-a[i];//存储当前位置的"j-Aj"
		mp[minu[i]].push(i);//把位置i加入代表minu[i]的队列
	}
	ll ans=0;
	for(int i=1;i<=n;i++){//从左向右枚举i点
		if(mp[miat[i]].empty()){
			mp.erase(miat[i]);//删除已经为空的队列，节省空间
			continue;
		}
		ans+=mp[miat[i]].size();//加上i之后所有j-Aj等于i+A[i]的值的总数
		mp[minu[i]].pop();//在i所在的队列弹出i，说明之后的位置不会再统计到i
	}
	cout<<ans;
}