【洛谷P4755】Beautiful Pair

题目

题目链接：https://www.luogu.com.cn/problem/P4755
小 D 有个数列 \(\{a\}\)，当一个数对 \((i,j)(i\le j)\) 满足 \(a_i\) 和 \(a_j\) 的积不大于 \(a_i,a_{i+1},\cdots,a_j\) 中的最大值时，小 D 认为这个数对是美丽的。请你求出美丽的数对的数量。
\(n\leq 10^5\)，\(1\leq a_i\leq 10^9\)。

思路

建出笛卡尔树，对于当前区间 \([l,r]\)，设其中最大值的下标为 \(k\)，只需要计算出有多少 \(i\in[l,k),j\in(k,r]\) 满足 \(a_i\times a_j\leq a_k\)。
考虑枚举区间长度小的那一边，然后问题转化为求一个区间不超过 \(v\) 的数的数量。主席树搞一下就可以了。
时间复杂度 \(O(n\log^2 n)\)。

代码

#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;

const int N=100010,LG=18;
int n,m,tot,a[N],c[N],lg[N],rt[N];
ll ans;
pair<int,int> st[N][LG+1];

void buildst()
{
	for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for (int j=1;j<=LG;j++)
		for (int i=1;i+(1<<j)-1<=n;i++)
			st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}

int findmax(int l,int r)
{
	int k=lg[r-l+1];
	return max(st[l][k],st[r-(1<<k)+1][k]).se;
}

struct SegTree
{
	int tot,lc[N*23],rc[N*23],cnt[N*23];
	
	int update(int now,int l,int r,int k)
	{
		int x=++tot;
		lc[x]=lc[now]; rc[x]=rc[now]; cnt[x]=cnt[now]+1;
		if (l==r) return x;
		int mid=(l+r)>>1;
		if (k<=mid) lc[x]=update(lc[now],l,mid,k);
		if (k>mid) rc[x]=update(rc[now],mid+1,r,k);
		return x;
	}
	
	int query(int nowl,int nowr,int l,int r,int ql,int qr)
	{
		if (ql>qr) return 0;
		if (ql<=l && qr>=r) return cnt[nowr]-cnt[nowl];
		int mid=(l+r)>>1,res=0;
		if (ql<=mid) res+=query(lc[nowl],lc[nowr],l,mid,ql,qr);
		if (qr>mid) res+=query(rc[nowl],rc[nowr],mid+1,r,ql,qr);
		return res;
	}
}seg;

void solve(int l,int r)
{
	if (l>r) return;
	if (l==r) { ans+=(c[a[l]]==1); return; }
	int mid=findmax(l,r);
	solve(l,mid-1); solve(mid+1,r);
	if (c[1]==1) ans+=seg.query(rt[l-1],rt[r],1,tot,1,1);
	if (mid-l<r-mid)
		for (int i=l;i<mid;i++)
		{
			int x=upper_bound(c+1,c+1+tot,c[a[mid]]/c[a[i]])-c-1;
			ans+=seg.query(rt[mid],rt[r],1,tot,1,x);
		}
	else
		for (int i=r;i>mid;i--)
		{
			int x=upper_bound(c+1,c+1+tot,c[a[mid]]/c[a[i]])-c-1;
			ans+=seg.query(rt[l-1],rt[mid-1],1,tot,1,x);
		}
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		c[i]=a[i]; st[i][0]=mp(a[i],i);
	}
	buildst();
	sort(c+1,c+1+n);
	tot=unique(c+1,c+1+n)-c-1;
	c[++tot]=1e9+10;
	for (int i=1;i<=n;i++)
	{
		a[i]=lower_bound(c+1,c+1+tot,a[i])-c;
		rt[i]=seg.update(rt[i-1],1,tot,a[i]);
	}
	solve(1,n);
	printf("%lld",ans);
	return 0;
}