題目鏈接：點擊查看
題目大意：給出一個長度為 n 的數(shù)列 a，現(xiàn)在一個數(shù)對 ( i , j ) 如果滿足 a[ i ] * a[ j?] <=max( a[ i ] ~ a[ j ]?)，則稱其為美麗的，求出美麗對的數(shù)量
題目分析：直接統(tǒng)計是比較困難的，但正難則反，我們可以枚舉每個數(shù)作為最大值時，在其管轄的區(qū)間內(nèi)進行統(tǒng)計，對于某個最大值 i 來說，肯定存在著 l[ i ] 和 r[ i ] ，使得 l[ i ] - 1 是 i 左側(cè)首個大于 a[ i ] 的位置，r[ i ] + 1 是 i 右側(cè)首個大于 a[ i ] 的位置，這樣在區(qū)間 [ l[ i ] , r[ i ] ] 中，跨過位置 i 時的最大值一定是 a[ i ] ，于是區(qū)間就被分成了兩段：[ l[ i ] , i ] , [ i , r[ i ] ]，因為乘積運算滿足交換律，所以遍歷長度較小的一段，在另一段中查找符合條件的元素的個數(shù)即可，假設當前枚舉的數(shù)字為 a[ j ] ，最大值為 a[ i ] ，所以需要在區(qū)間內(nèi)查找 [ 1 , a[ i ] / a[ j ] ] 的元素個數(shù)，這顯然是線段樹的功能，不過如果放在區(qū)間上詢問的話，就需要可持久化一下來使用，也就是主席樹了，對于上述找 l[ i ] 和 r[ i ] 的過程，可以用笛卡爾樹來完成，然后 dfs 一遍統(tǒng)計答案就好了
代碼：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int a[N];LL ans;
/*主席樹*/
struct Node1
{int l,r;int sum;
}tree[N*35];int cnt,root[N];void update(int num,int &k,int l,int r)
{tree[cnt++]=tree[k];k=cnt-1;tree[k].sum++;if(l==r)return;int mid=l+r>>1;if(num<=mid)update(num,tree[k].l,l,mid);elseupdate(num,tree[k].r,mid+1,r);
}int query(int i,int j,int L,int R,int l,int r)//i：左端點根節(jié)點編號，j：右端點根節(jié)點編號，l,r:目標區(qū)間，L,R:當前區(qū)間
{if(l>r)return 0;if(R<l||L>r)return 0;if(L>=l&&R<=r)return tree[j].sum-tree[i].sum;int mid=L+R>>1;return query(tree[i].l,tree[j].l,L,mid,l,r)+query(tree[i].r,tree[j].r,mid+1,R,l,r);
}
/*主席樹*/
/*笛卡爾樹*/
struct Node2
{int l,r,val;
}t[N];stack<int>s;void insert(int x)
{while(s.size()&&t[s.top()].val<t[x].val)s.pop();t[x].l=t[s.top()].r;//x->lsont[s.top()].r=x;//fa->x(rson)s.push(x);
}
/*笛卡爾樹*/
void dfs(int k,int l,int r)
{if(k==0)//特判一下根 {if(t[k].l)dfs(t[k].l,l,r);if(t[k].r)dfs(t[k].r,l,r);return;}if(k-l<=r-k)//遍歷左區(qū)間 for(int i=l;i<=k;i++)ans+=query(root[k-1],root[r],1,inf,1,t[k].val/t[i].val);else//遍歷右區(qū)間 for(int i=k;i<=r;i++)ans+=query(root[l-1],root[k],1,inf,1,t[k].val/t[i].val);if(t[k].l)dfs(t[k].l,l,k-1);if(t[k].r)dfs(t[k].r,k+1,r);
}void init()
{t[0].val=inf;t[0].l=t[0].r=0;s.push(0);root[0]=0;tree[0].l=tree[0].r=tree[0].sum=0;cnt=1;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);init();int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&t[i].val);insert(i);root[i]=root[i-1];update(t[i].val,root[i],1,inf);}dfs(0,1,n);printf("%lld\n",ans);return 0;
}
?
總結(jié)
以上是生活随笔 為你收集整理的洛谷 - P4755 Beautiful Pair(笛卡尔树+主席树) 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔 推薦給好友。
