T1 算术

题意

给定长度为 \(n\) 的数列 \(a\)，求有多少 \((i,j)\) 满足 \(j<i,a_ia_j<a_i+a_j\)。

Solution

简单的在草稿本上写一写就可以发现一些特别的规律。

在这道题中特殊的数只有 \(1\)，不难发现，\(1\) 与任意数都可以符合题目要求。以 \(1\) 作为分界线，对大于 \(1\) 和小于 \(1\) 的数进行讨论，简单的举几个特例就可以发现规律。

令 \(cnt1\) 记录从数列头到当前位置 \(i\) 的 \(1\) 的个数，\(cntP\) 为大于 \(1\) 的个数，\(cntN\) 为小于 \(1\) 的个数。

• 若 \(a_i=1\)，则 \(a_i\) 会对答案贡献 \(i-1\)（因为显然 \(1\) 与当前数之前的任何数都可以满足题目要求）

• 若 \(a_i>1\)，则 \(a_i\) 会对答案贡献 \(cnt1+cntN\)（\(1\) 肯定可以与 \(a_i\) 组合，此外与负数和 \(0\) 组合也是符合题意的）

• 若 \(a_i<1\)，则 \(a_i\) 会对答案贡献 \(cnt1+cntP\)（与大于 \(1\) 的情况类似）

你甚至可以不需要数组就可以做这道题。

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
#define int long long
using namespace std;
void read(auto &k)
{
	k=0;auto flag=1;char b=getchar();
	while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
	while (isdigit(b)) {k=k*10+b-48;b=getchar();}
	k*=flag;
}
void write(auto k) {if (k<0){putchar('-');write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
void writewith(auto k,char c) {write(k),putchar(c);}
const int _SIZE=1e6;
int n,ans;
int valCur,cnt1=0,cntP=0,cntN=0;//cnt1 counts the number 1, cntP counts positive number greater than 1
//cntN counts number less than 1
signed main()
{
	read(n);
	for (int i=1;i<=n;i++)
	{
		read(valCur);
		if (valCur==1) cnt1++,ans+=i-1;
		else if (valCur>1) cntP++,ans+=cnt1+cntN;
		else cntN++,ans+=cnt1+cntP;
	}
	writewith(ans,'\n');
	return 0;
}