ABC 166 E This Message Will Self-Destruct in 5s

2020-05-03 22:39:05


题目大意:

给定数列 $A_i$,求满足 $A_i+A_j=i-j\ \ (i\gt j)$ 的 $(i,j)$ 个数。

我们发现,等号两边都有关于 $i$ 的项和关于 $j$ 的项,很乱。我们整理一下:

给定数列 $A_i$,求满足 $i-A_i=j+A_j\ \ (i\gt j)$ 的 $(i,j)$ 个数。

这个时候思路就很清晰了。

具体的,就是扫一遍 $A_i$,然后求满足 $i-A_i=j+A_j\ \ (i>j)$ 的 $j$ 的个数,最后加起来就好了。

不难发现,现在复杂度还是 $O(N^2)$ 的。我们可以开个桶记录一下,具体的,就是查询完 $i$ 后,将桶中 $i+A_i$ 对应的数加上 $1$,查询的时候只需要查询 $i-A_i$ 对应的值就好了(注意先后顺序)。不难发现,普通的桶肯定是不行的,我们可以考虑使用 map

这样复杂度就是 $O(n\log n)$ 了,轻松通过此题。

#include<cstdio>
#include<map>
using std::map;
#define int long long
map<int,int> m;int a[(int)2*(int)1e6+1],n,ans;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    m[a[1]+1]++;
    for(int i=2;i<=n;i++){
        ans+=m[i-a[i]],m[a[i]+i]++;
    }
    printf("%lld\n",ans);
}