求调玄关，启发式+树状数组 TLE on #18 #19

#include <bits/stdc++.h>
#define PII pair <int, int>
#define LL long long
#define DB double
#define ST string

#define fr(x, y, z) for(int x = (y); x <= (z); x ++ )
#define dfr(x, y, z) for(int x = (y); x >= (z); x -- )

using namespace std;

const int N = 300010, INF = 1e9 + 7;
int T, n, k, a[N];

int fa[N][30], mx[N][30], _log[N];
int get(int x, int y)
{
	int len = y - x + 1;
	int Lmax = mx[x][_log[len]];
	int Rmax = mx[y - (1 << _log[len]) + 1][_log[len]]; 
	
//	printf("%d %d %d %d %d %d %d\n", x, y, len, _log[len], Lmax, Rmax, a[Lmax] > a[Rmax] ? Lmax : Rmax);
	
	return a[Lmax] > a[Rmax] ? Lmax : Rmax;
}

int cnt;
vector <PII> v[N];
void work(int l, int r)
{
	if(l > r) return ;
	
	int p = get(l, r);

	if(p - l < r - p)
	{
		dfr(i, p, l)
		{
			v[p - 1].push_back({a[p] / a[i], -1});
			v[r].push_back({a[p] / a[i], 1});
			
//			printf("%d -> [%d, %d](<= %d)\n", i, p, r, a[p] / a[i]);
		}
	} 
	else
	{
		fr(i, p, r)
		{
			v[l - 1].push_back({a[p] / a[i], -1});
			v[p].push_back({a[p] / a[i], 1});
			
//			printf("[%d, %d] -> %d(<= %d)\n", l, p, i, a[p] / a[i]);
		}
	}
	
//	printf("[%d, %d] -> [%d, %d], [%d, %d]\n", l, r, l, p - 1, p + 1, r);
	
	work(l, p - 1);
	work(p + 1, r);
}

map <int, LL> t;
void insert(int x)
{ while(x < INF) t[x] ++ , x += (x & -x); }

int query(int x)
{
	LL res = 0;
	while(x) res += t[x], x -= (x & -x);
	return res; 
}

signed main()
{
	scanf("%d", &n);
	fr(i, 1, n) scanf("%d", &a[i]);
	fr(i, 2, n) _log[i] = _log[i / 2] + 1;
	
	// 维护 RMQ 
	fr(i, 0, n) fa[i][0] = i, mx[i][0] = i;  
	
	fr(j, 1, 20) fr(i, 1, n)
	{
		if(i + (1 << j) - 1 > n) { fa[i][j] = N; continue; }
		
		fa[i][j] = fa[fa[i][j - 1] + 1][j - 1];
		
		int l = mx[i][j - 1], r = mx[fa[i][j - 1] + 1][j - 1];
		if(a[l] < a[r]) mx[i][j] = r;
		else mx[i][j] = l;
	}
	
	work(1, n);
	
//	memcpy(b, a, sizeof a);
//	sort(b + 1, b + 1 + n);
//	fr(i, 1, n) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
//	fr(i, 1, n) printf("%d%c", a[i], " \n"[i == n]); 

	LL res = 0;
	fr(i, 1, n)
	{
		insert(a[i]);
		for(PII j : v[i]) res += 1ll * query(j.first) * j.second;
	}
	
	printf("%lld\n", res);
	
    return 0;
}

/*
2
5 3
2 3 2 2 5
10 4
1 5 4 3 6 2 10 8 4 5
*/