最小最大对

题目描述

给你一个长度为N的由1到N之间的整数组成的整数序列a=(a1,

…,aN)。

求出满足以下条件的整数对(i,j)的数量：

l 1<=i<j<=N

l min(ai,aj)=i

l max(ai,aj)=j

约束条件：

2<=N<=5*10^5

1<=ai<=N(1<=i<=N)

输入均为整数。

输入

N

a1 a2 ... aN

输出

一行，一个整数。

样例输入 复制

4

1 3 2 4

样例输出 复制

2

提示

注：(i,j)=(1,4),(2,3)都满足条件。

样例输入2：

10

5 8 2 2 1 6 7 2 9 10

样例输出2：

8

我的代码如下：样例1输出5

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,i,a[500010],s,ans,j;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n;i++)
		if(a[i]==i)
			s++;
	ans=s*(s-1)/2;
	for(j=1;j<=n;j++){
		i=a[j];
		if(a[i]==j)ans++,cout<<j<<" ";
	}
	cout<<ans;
	return 0;
}