正題

題目鏈接:https://www.luogu.com.cn/problem/P4755

---

題目大意

$n$個數(shù)字的一個序列，求有多少個點對$i,j$滿足$a_i\times a_j\le max\{a_k\}(k\in [l,r])$

---

解題思路

如果構(gòu)建一棵笛卡爾樹的話那么兩個點之間的$max$就在笛卡爾樹的$LCA$位置。

所以對于每個位置維護一個線段樹，然后每次暴力枚舉小的那棵子樹在大子樹的線段樹中查詢即可。然后線段樹合并或者啟發(fā)式合并上去就好了。

建笛卡爾樹的時候用$\text{RMQ}$查詢區(qū)間最大值然后遞歸下去就好了。

當(dāng)然因為是乘法所以小的那個值域不會超過$\sqrt{10^9}$所以也可以樹狀數(shù)組+啟發(fā)式合并。

這里寫的是線段樹的做法，時間復(fù)雜度都是$O(n{\log }^{2}n)$

注意$1$要特判就好了

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10,L=20; int n,a[N],lg[N],f[N][L+1],inf; long long ans; struct Seg_Tree{int cnt,w[N<<6],ls[N<<6],rs[N<<6];void Change(int &x,int L,int R,int pos,int val){if(!x)x=++cnt;w[x]+=val;if(L==R)return;int mid=(L+R)>>1;if(pos<=mid)Change(ls[x],L,mid,pos,val);else Change(rs[x],mid+1,R,pos,val);return;}int Ask(int x,int L,int R,int l,int r){if(!x||l>r)return 0;if(L==l&&R==r)return w[x];int mid=(L+R)>>1;if(r<=mid)return Ask(ls[x],L,mid,l,r);if(l>mid)return Ask(rs[x],mid+1,R,l,r);return Ask(ls[x],L,mid,l,mid)+Ask(rs[x],mid+1,R,mid+1,r);}int Merge(int x,int y,int L,int R){if(!x||!y)return x+y;int mid=(L+R)>>1;w[x]+=w[y];if(L==R)return x;ls[x]=Merge(ls[x],ls[y],L,mid);rs[x]=Merge(rs[x],rs[y],mid+1,R);return x;} }T; int Ask(int l,int r){int z=lg[r-l+1];int x=f[l][z],y=f[r-(1<<z)+1][z];return (a[x]>=a[y])?x:y; } int solve(int l,int r){if(l>r)return 0;int x=Ask(l,r),ls,rs;ls=solve(l,x-1);rs=solve(x+1,r);if(ls)ans+=T.Ask(ls,1,inf,1,1);if(rs)ans+=T.Ask(rs,1,inf,1,1);if(x-l<=r-x){for(int i=l;i<x;i++)ans+=T.Ask(rs,1,inf,1,a[x]/a[i]);}else{for(int i=x+1;i<=r;i++)ans+=T.Ask(ls,1,inf,1,a[x]/a[i]);}ls=T.Merge(ls,rs,1,inf);T.Change(ls,1,inf,a[x],1);return ls; } int main() {// printf("%d\n",sizeof(T)>>20);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);inf=max(inf,a[i]);ans+=(a[i]==1);f[i][0]=i;}inf=1e9;for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++){int x=f[i][j-1],y=f[i+(1<<j-1)][j-1];if(a[x]>=a[y])f[i][j]=x;else f[i][j]=y;}solve(1,n);printf("%lld",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4755-Beautiful Pair【笛卡尔树,线段树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。