只有最后一个点卡 nlog^3n 的吗/xia

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[500005], b[500005], ls[500005], tot, ans, cnt;
int rt[500005];
map<int, int> mp;
struct PSGT_node{
	int l, r, vl, ls, rs;
};
struct PSGT{
	PSGT_node tr[3000005];
	void build(int u, int l, int r){
		tr[u].l = l;
		tr[u].r = r;
		tr[u].ls = u << 1;
		tr[u].rs = u << 1 | 1;
		tot = max(tot, u);
		if (l == r)
			return;
		int mid = (l + r) >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
	}
	int rebuild(int u, int l, int r, int x){
		if (x < l || x > r)
			return -1;
		tr[++tot].l = l;
		tr[tot].r = r;
		tr[tot].vl = tr[u].vl + 1;
		tr[tot].ls = tr[u].ls;
		tr[tot].rs = tr[u].rs;
		int tmp = tot;
		if (l == r)
			return tmp;
		int mid = (l + r) >> 1;
		if (x <= mid)
			tr[tot].ls = rebuild(tr[u].ls, l, mid, x);
		else
			tr[tot].rs = rebuild(tr[u].rs, mid + 1, r, x);
		return tmp;
	}
	int qry(int u, int v, int l, int r, int k){
		if (l == r)
			return mp[l];
		int mid = (l + r) >> 1;
		if (tr[tr[v].ls].vl - tr[tr[u].ls].vl >= k)
			return qry(tr[u].ls, tr[v].ls, l, mid, k);
		else
			return qry(tr[u].rs, tr[v].rs, mid + 1, r, k - tr[tr[v].ls].vl + tr[tr[u].ls].vl);
	}
}Sgt;
int qrk(int L, int R, int x){
//	x = lower_bound(b + 1, b + cnt + 1, x) - b;
	int l = 1, r = R - L + 1, ans = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (Sgt.qry(rt[L - 1], rt[R], 1, cnt, mid) <= x)
			ans = mid, l = mid + 1;
		else
			r = mid - 1;
	}
//	cout << L << " " << R << " " << x << " " << ans << "\n";
	return ans;
}
void solve(int l, int r){
//	cout << l << " " << r << "\n";
	if (l > r)
		return;
	if (l == r){
		ans += (a[l] == 1);
		return;
	}
	int mx = 0, mid;
	for (int i = l; i <= r; i++){
		if (a[i] > mx)
			mx = a[i], mid = i;
	}
	if (mid - l + 1 <= r - mid){
		for (int i = l; i <= mid; i++)
			ans += qrk(mid, r, a[mid] / a[i]);
	}else
		for (int i = mid; i <= r; i++)
			ans += qrk(l, mid, a[mid] / a[i]);
	solve(l, mid - 1);
	solve(mid + 1, r);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
	cnt = unique(b + 1, b + 1 + n) - b - 1;
	rt[0] = 1;
	Sgt.build(1, 1, cnt);
	for (int i = 1; i <= n; i++){
		int hsh = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
		mp[hsh] = a[i];
		rt[i] = tot + 1;
		Sgt.rebuild(rt[i - 1], 1, cnt, hsh);
	}
	solve(1, n);
	cout << ans; 
	return 0;
}