欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.10.30T3 Beautiful Pair(分治)

程序员文章站 2022-04-02 21:27:37
...

题目链接:Luogu4755

题解:

这题是个很好的分治练习题。

一看数据范围就知道肯定要固定式子里的一项,用O(1)O(1)O(logn)O(log n)的复杂度统计此情况的答案,而区间变化时,最大值很容易变化,所以我们考虑怎样固定最大值:

首先考虑,如果直接选出区间最大值,有多少区间的最大值是它呢,当然是横跨它的所有区间了,不横跨它的区间又自成子问题,所以想到分治做法:找到区间最大值的位置,位置左右分别递归求解,然后统计横跨这个位置的符合条件的区间个数。

怎么统计呢,当前最大值设为Maxv,枚举一边的点i,另一边选择的区间的另一个端点的取值当然就是0~Maxva[i]\lfloor \frac{Maxv}{a[i]} \rfloor,用主席树统计就可以了.

但是因为最大值点不像二分点那样稳定,轻易就会被卡掉。但我们可以将计就计,利用它的不稳定性,规定只枚举区间长度小的一边,这样如果数据想卡我们,我们反而跑得更快。

严格可以这样证明复杂度,当每一个点对复杂度做贡献,它所在区间一定比上一次至少短了一半,加上主席树(找最大值位置用St表O(1)O(1)),复杂度为O(nlog2n)O(nlog^2n)

代码:

#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;
}
相关标签: 数学