2018.10.30T3 Beautiful Pair(分治)
程序员文章站
2022-04-02 21:27:37
...
题目链接:Luogu4755
题解:
这题是个很好的分治练习题。
一看数据范围就知道肯定要固定式子里的一项,用或的复杂度统计此情况的答案,而区间变化时,最大值很容易变化,所以我们考虑怎样固定最大值:
首先考虑,如果直接选出区间最大值,有多少区间的最大值是它呢,当然是横跨它的所有区间了,不横跨它的区间又自成子问题,所以想到分治做法:找到区间最大值的位置,位置左右分别递归求解,然后统计横跨这个位置的符合条件的区间个数。
怎么统计呢,当前最大值设为Maxv,枚举一边的点i,另一边选择的区间的另一个端点的取值当然就是0~,用主席树统计就可以了.
但是因为最大值点不像二分点那样稳定,轻易就会被卡掉。但我们可以将计就计,利用它的不稳定性,规定只枚举区间长度小的一边,这样如果数据想卡我们,我们反而跑得更快。
严格可以这样证明复杂度,当每一个点对复杂度做贡献,它所在区间一定比上一次至少短了一半,加上主席树(找最大值位置用St表),复杂度为
代码:
#include <iostream>
#include <stdio.h>
using namespace std;
#define N 100050
const int Len=1e9;
struct Node{
Node* l;
Node* r;
int val;
Node(){l=r=NULL;val=0;}
};
Node* NewNode(){return new Node();}
int n;
int ai[N],St_v[N][20],St_p[N][20],Log[N];
Node* Rt[N];
void update(Node* bef,Node* o,int l,int r,int k)
{
if(bef==NULL) bef=Rt[0];
// printf("%d %d %d %d %d\n",bef==NULL,o==NULL,l,r,k);
o->val=bef->val+1;
if(l==r) return;
int mid=((l+r)>>1);
if(k<=mid){
if(o->l==NULL) o->l=NewNode();
o->r=bef->r;
update(bef->l,o->l,l,mid,k);
}
else{
if(o->r==NULL) o->r=NewNode();
o->l=bef->l;
update(bef->r,o->r,mid+1,r,k);
}
}
int query(Node* bef,Node* o,int l,int r,int le,int ri)
{
if(bef==NULL) bef=Rt[0];
if(le<=l && r<=ri)
return o->val-bef->val;
int mid=((l+r)>>1),ret=0;
if(le<=mid && o->l!=NULL)
ret+=query(bef->l,o->l,l,mid,le,ri);
if(ri>mid && o->r!=NULL)
ret+=query(bef->r,o->r,mid+1,r,le,ri);
return ret;
}
inline int find(int l,int r){
int a=Log[r-l+1];
if(St_v[l][a]>St_v[r-(1<<a)+1][a])
return St_p[l][a];
return St_p[r-(1<<a)+1][a];
}
long long Solve(int l,int r)
{
if(l>r) return 0;
if(l==r) return ai[l]<=1;
int Max_p=find(l,r),Max_v=ai[Max_p];
long long ret=0;
ret+=Solve(l,Max_p-1);
ret+=Solve(Max_p+1,r);
if(Max_p-l<r-Max_p){
for(int i=l;i<=Max_p;i++){
if(ai[i]==0) ret+=r-Max_p+1;
else ret+=query(Rt[Max_p-1],Rt[r],0,Len,0,Max_v/ai[i]);
}
}
else{
for(int i=Max_p;i<=r;i++){
if(ai[i]==0) ret+=Max_p-l+1;
else ret+=query(Rt[l-1],Rt[Max_p],0,Len,0,Max_v/ai[i]);
}
}
return ret;
}
void Test_St(){
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++)
printf("%d ",find(i,j));
printf("\n");
}
}
void Test_Tree(){
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
cout<<query(Rt[i-1],Rt[j],0,Len,2,4)<<" ";
cout<<endl;
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<=n;i++)
Rt[i]=NewNode();
int np=0;
for(int i=1;i<=n;i++){
Log[i]=np;
if(i==(1<<(np+1)))
np++;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&ai[i]);
St_v[i][0]=ai[i];
St_p[i][0]=i;
update(Rt[i-1],Rt[i],0,Len,ai[i]);
}
for(int a=1;a<=18;a++)
for(int i=1;i+(1<<a)-1<=n;i++)
{
if(St_v[i][a-1]<St_v[i+(1<<(a-1))][a-1]){
St_v[i][a]=St_v[i+(1<<(a-1))][a-1];
St_p[i][a]=St_p[i+(1<<(a-1))][a-1];
}
else{
St_v[i][a]=St_v[i][a-1];
St_p[i][a]=St_p[i][a-1];
}
}
printf("%lld\n",Solve(1,n));
return 0;
}
上一篇: 二维空间点到直线垂足计算公式推导及Java实现——学习笔记
下一篇: 重建二叉树
推荐阅读
-
UVA 10245(The Closest Pair Problem)分治
-
luoguP4755 Beautiful Pair
-
【单调栈/离散化/树状数组】 Beautiful Pair 洛谷P4755
-
洛谷P4755 Beautiful Pair 笛卡尔树上启发式合并 主席树计数
-
洛谷 - P4755 Beautiful Pair(笛卡尔树+主席树)
-
洛谷 P4755 Beautiful Pair —— 主席树+笛卡尔树
-
洛谷4755 Beautiful Pair (分治)
-
洛谷4755 Beautiful Pair 分治 主席树 离散化
-
分治&线段树练习——洛谷P4755 Beautiful Pair
-
洛谷p4755 Beautiful Pair