「LGR-049」洛谷7月月賽 D.Beautiful Pair

題目大意 : 給出長度為 $n$ 的序列，求滿足 $i \leq j$ 且 $a_i \times a_j \leq \max(a_i..a_j) $ 的點對$(i, j)$的數量

$n \leq 10^5 \ 1 \leq a_i \leq 10^9$

[「LGR-049」洛谷7月月賽 D.Beautiful Pair](https://www.luogu.org/problemnew/show/P4755)

題目大意 : 給出長度為 \(n\) 的序列，求滿足 \(i \leq j\) 且 $a_i \times a_j \leq \max(a_i..a_j) $ 的點對\((i, j)\)的數量

\(n \leq 10^5 \ 1 \leq a_i \leq 10^9\)

解題思路 :

直接枚舉某一端點貌似很難維護極值，不妨對于每一個極值 \(a_k\)，求 $ \max(a_i..a_j) \leq a_k$ 且 \(i \leq k \leq j\) 的點對數

考慮一個每一個點能作為\(\max\)統治的區間可以用單調棧求，并建構出笛卡爾樹

此時對于每一個 \(a_k\) 答案由兩部分産生:

1. 點對 \((i, j)\) 滿足 \(i = k\) 或 $j = k $，這一部分答案比較簡單，就是統治區間内 \(1\) 的個數
2. 點對 \((i, j)\) 滿足 \(i \neq k\) 且 \(j \neq k\) ，此時答案等價于點 \(k\) 在笛卡爾樹上的節點的左右子樹中各取一個組成合法點對的方案數

第一種情況可以直接字首和計算，在此不多做讨論，主要看第二種情況

由于是樹上的子樹問題，我們很容易想到用 \(dsu \ on\ tree\) 的做法來解決

不了解 \(dsu \ on \ tree\) 的可以戳這裡的連結

枚舉子樹大小較小的子樹，用樹狀數組維護較大的子樹産生的貢獻

對于較小子樹中的點 \(u\) ，能與其組成合法點對的點 \(x\) 要滿足 \(\frac{maxval}{a_u} \leq a_x\)，直接用樹狀數組統計字首和即可

/*program by mangoyang*/
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int f = 0, ch = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
#define N (500005)
#define int ll
int a[N], b[N], n, ans;
namespace Ls{
	int s[N]; int lens = 0;
	inline int calc(int x){
		int res = upper_bound(s + 1, s + lens + 1, x) - s - 1;
		return res;
	}
	inline void Realmain(){
		for(int i = 1; i <= n; i++) s[i] = a[i];
		sort(s + 1, s + n + 1);
		lens = unique(s + 1, s + n + 1) - s - 1;
	}
}
struct Fenwick{
	int s[N];
	inline int lowbit(int x){ return x & -x; }
	inline void add(int x, int v){
		for(int i = x; i <= n; i += lowbit(i)) s[i] += v;
	}
	inline int query(int x){
		int ans = 0;
		for(int i = x; i; i -= lowbit(i)) ans += s[i];
		return ans;
	}
}Bit;
namespace Treap{
	int sz[N], ch[N][2], s[N], l[N], r[N], st[N], top;
	inline void Getsize(int u){
		sz[u] = 1; 
		int ls = ch[u][0], rs = ch[u][1];
		if(ls) Getsize(ls), sz[u] += sz[ls];
		if(rs) Getsize(rs), sz[u] += sz[rs];
		if(!u) sz[u] = 0;
	}
	inline void Add(int u){
		Bit.add(b[u], 1);
		if(ch[u][0]) Add(ch[u][0]);
		if(ch[u][1]) Add(ch[u][1]);
	}
	inline void Clear(int u){
		Bit.add(b[u], -1);
		if(ch[u][0]) Clear(ch[u][0]);
		if(ch[u][1]) Clear(ch[u][1]);
	}
	inline int Count(int u, int val){
		int pos = Ls::calc(val / a[u]);
		int res = Bit.query(pos);
		if(ch[u][0]) res += Count(ch[u][0], val);
		if(ch[u][1]) res += Count(ch[u][1], val);
		return res;
	}
	inline void solve(int u){
		int p = sz[ch[u][0]] > sz[ch[u][1]] ? 0 : 1;
		int ms = ch[u][p], ls = ch[u][p^1];
		if(ls) solve(ls), Clear(ls);
		if(ms) solve(ms); 
		if(ls) ans += Count(ls, a[u]);
		if(u){ if(ls) Add(ls); Bit.add(b[u], 1); } 
	}
	inline void Build(){
		for(int i = 1; i <= n; i++){
			while(a[st[top]] <= a[i] && top) r[st[top--]] = i - 1;
			int f = st[top]; l[i] = f + 1;
			ch[i][0] = ch[f][1], ch[f][1] = i, st[++top] = i; 
		}
		for(int i = 1; i <= n; i++) if(!r[i]) r[i] = n;
	}
	inline void Realmain(){
		Build(), Getsize(0), solve(0);
		for(int i = 1; i <= n; i++) s[i] = s[i-1] + (a[i] == 1 ? 1 : 0);
		for(int i = 1; i <= n; i++) ans += s[r[i]] - s[l[i]-1];
		cout << ans << endl;
	}
}
main(){
	read(n);
	for(int i = 1; i <= n; i++) read(a[i]);
	Ls::Realmain();
	for(int i = 1; i <= n; i++) b[i] = Ls::calc(a[i]);
	Treap::Realmain();
	return 0;
}