【单调栈/离散化/树状数组】 Beautiful Pair 洛谷P4755

题目描述

小D有个数列 {a}\{a\}{a} ，当一个数对 (i,j)(i≤j)(i,j)(i\le j)(i,j)(i≤j) 满足 aia_iai​ 和 aja_jaj​ 的积不大于 ai,ai+1,⋯,aja_i,a_{i+1},\cdots,a_jai​,ai+1​,⋯,aj​ 中的最大值时，小D认为这个数对是美丽的.请你求出美丽的数对的数量。

输入输出格式

输入格式：

 

第一行输入一个整数 nnn ，表示元素个数。 第二行输入 nnn 个整数 a1,a2,a3,⋯,ana_1,a_2,a_3,\cdots,a_na1​,a2​,a3​,⋯,an​ ，为所给的数列。

 

输出格式：

 

输出一个整数，为美丽的数字对数。

 

输入输出样例

输入样例#1： 复制

4
1 3 9 3

输出样例#1： 复制

5

输入样例#2： 复制

5
1 1 2 1 1

输出样例#2： 复制

14

说明

样例1解释

五种可行的数对为(1,1)(1,2)(1,3)(1,4)(2,4)。

样例2解释

只有数对(3,3)不可行。

1≤n≤1051\le n\le{10}^51≤n≤105

1≤ai≤1091\le a_i\le{10}^91≤ai​≤109

 

#include <bits/stdc++.h>
using namespace std;

const int mn = 100010;

int a[mn], b[mn];
stack<int>s;
int L[mn], R[mn];
vector<int>v[mn];
int len;
int bit[mn];
void add(int i, int t) 	// 树状数组的更新 使i项起加上t
{
	while (i <= len + 1)
	{
		bit[i] += t;
		i += i & -i;
	}
}
int sum(int i) 	// 树状数组求前i项和
{
	int s = 0;
	while (i > 0)
	{
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		b[i] = a[i];
	}

	/// O(n)单调栈分别确定以i为最大值时的左右区间范围
	for (int i = 1; i <= n; i++)
	{
		while (!s.empty() && a[i] > a[s.top()]) /// >= ×
			s.pop();
		if (s.empty())
			L[i] = 1;
		else
			L[i] = s.top() + 1;
		s.push(i);
	}
	while (!s.empty())
		s.pop();
	for (int i = n; i >= 1; i--)
	{
		while (!s.empty() && a[i] >= a[s.top()])
			s.pop();
		if (s.empty())
			R[i] = n;
		else
			R[i] = s.top() - 1;
        s.push(i);
	}
	while (!s.empty())
		s.pop();

	for (int i = 1; i <= n; i++)
	{
		if (i <= (L[i] + R[i]) / 2) 	// 左区间较小 枚举较小的区间
		{
			for (int j = L[i]; j <= i; j++) // 计算右区间情况
			{
				v[i - 1].push_back(-a[i] / a[j]);
				v[R[i]].push_back(a[i] / a[j]);
			}
		}
		else 	// 右区间较小
		{
			for (int j = i; j <= R[i]; j++) // 枚举右区间
			{
				v[L[i] - 1].push_back(-a[i] / a[j]);
				v[i].push_back(a[i] / a[j]);
			}
		}
	}

	/// 离散化 使10亿纵坐标减小为最多20w
	sort(b + 1, b + n + 1);
	len = unique(b + 1, b + n + 1) - (b + 1);
	for (int i = 1; i <= n; i++)
		a[i] = upper_bound(b + 1, b + len + 1, a[i]) - (b + 1);

    /// 下标为数字大小 a数组记录该大小的数字的多少
    /// a[i] 存储高度为i的数字有几个
    /// 树状数组记录数量和 下标为高度
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		add(a[i], 1);
		int sz = v[i].size();
		for (int j = 0; j < sz; j++)
		{
			int t = upper_bound(b + 1, b + len + 1, abs(v[i][j])) - (b + 1);
			if (v[i][j] < 0)
				ans -= sum(t);
			else
				ans += sum(t);
		}
    }
	printf("%d\n", ans);

	return 0;
}