欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-08 17:54:21
...

题目描述

小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;
}