洛谷P4755 Beautiful Pair 笛卡尔树上启发式合并 主席树计数
程序员文章站
2022-05-08 17:57:51
...
https://www.luogu.com.cn/problem/P4755
这题思路挺简单的,写起来有一点长
对整个序列构建笛卡尔树,每个节点大于他的左子树和右子树的所有值,那么就可以对笛卡尔树进行dfs,回溯时启发式合并两个子树,根节点就是最大值,枚举小的那边每个位置a[i],计算出每一个位置所能够接受的a[j]的上限,然后用主席树去另一个区间求区间内满足1-a[j]上限的个数,就是跨过a[u]并以a[u]为最大值的美丽的数对的数量
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxl=1e5+10;
const int inf=2e9;
int n,tot,cnt,root;ll ans;
int a[maxl],b[maxl],rt[maxl];
struct cnode
{
int k,val,fa,ls,rs,l,r;
}ctr[maxl];
struct node
{
int ls,rs,sum;
}tr[maxl*80];
inline void insert(int &k,int x,int l,int r)
{
tr[++cnt]=tr[k];k=cnt;
if(l==r)
{
tr[k].sum++;
return;
}
int mid=(l+r)>>1;
if(x<=mid)
insert(tr[k].ls,x,l,mid);
else
insert(tr[k].rs,x,mid+1,r);
tr[k].sum=tr[tr[k].ls].sum+tr[tr[k].rs].sum;
}
inline void prework()
{
scanf("%d",&n);tot=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[++tot]=a[i];
}
sort(b+1,b+1+tot);
tot=unique(b+1,b+1+tot)-b-1;
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
rt[i]=rt[i-1];
insert(rt[i],a[i],1,tot);
}
}
inline int build()
{
int k;
for(int i=1;i<=n;i++)
{
k=i-1;
while(ctr[k].val<ctr[i].val)
k=ctr[k].fa;
ctr[i].fa=k;
ctr[i].ls=ctr[k].rs;
ctr[ctr[k].rs].fa=i;
ctr[k].rs=i;
}
return ctr[0].rs;
}
inline int qry(int i,int j,int l,int r,int l1,int r1)
{
int mid=(l1+r1)>>1;
if(l1==l && r1==r)
return tr[j].sum-tr[i].sum;
if(r<=mid)
return qry(tr[i].ls,tr[j].ls,l,r,l1,mid);
else if(l>mid)
return qry(tr[i].rs,tr[j].rs,l,r,mid+1,r1);
else
return qry(tr[i].ls,tr[j].ls,l,mid,l1,mid)+
qry(tr[i].rs,tr[j].rs,mid+1,r,mid+1,r1);
}
inline void dfs(int k)
{
int ls=ctr[k].ls,rs=ctr[k].rs,d,llen=0,rlen=0,id;
ctr[k].l=ctr[k].r=ctr[k].k;
if(ls)
dfs(ls),ctr[k].l=ctr[ls].l,llen=ctr[ls].r-ctr[ls].l+1;
if(rs)
dfs(rs),ctr[k].r=ctr[rs].r,rlen=ctr[rs].r-ctr[rs].l+1;
if(llen>=rlen)
{
for(int i=k;i<=ctr[k].r;i++)
{
d=b[a[k]]/b[a[i]];
id=lower_bound(b+1,b+1+tot,d)-b;
if(b[id]>d)
--id;
if(!id) continue;
ans+=qry(rt[ctr[k].l-1],rt[k],1,id,1,tot);
}
}
else
{
for(int i=ctr[k].l;i<=k;i++)
{
d=b[a[k]]/b[a[i]];
id=lower_bound(b+1,b+1+tot,d)-b;
if(b[id]>d)
--id;
if(!id) continue;
ans+=qry(rt[k-1],rt[ctr[k].r],1,id,1,tot);
}
}
}
inline void mainwork()
{
int k;
ctr[0]=cnode{0,inf,0,0,0,0,0};
for(int i=1;i<=n;i++)
ctr[i]=cnode{i,a[i],0,0,0,0,0};
ans=0;
root=build();
dfs(root);
}
inline void print()
{
printf("%lld\n",ans);
}
int main()
{
prework();
mainwork();
print();
return 0;
}
下一篇: Python正则表达式匹配ip地址实例