P4755 Beautiful Pair

题目

做法

\(i≤x≤j,a[i]<\frac{a[x]}{a[j]}\)

考虑\(a[x]\)的贡献，单调栈预处理\(L,R\)能作为最大值的区间

枚举一端点，仅需另一端点满足条件即可，启发式枚举端点

另一端点丢到树状数组里随便乱搞，由于是一个区间的要差分一下

My complete code

#include<bits/stdc++.h>

#include<vector>

using namespace std;

typedef long long LL;

const LL maxn=1e5+9;

struct node{

	LL val,x;

}que[maxn]; vector<LL> Q[maxn];

LL n,cnt;

LL L[maxn],R[maxn],a[maxn],b[maxn];

inline void Fir_LR(){

	LL tail(0);

	for(LL i=1;i<=n;++i){

		while(tail && que[tail].val<a[i]) --tail;

		L[i]=(tail?que[tail].x+1:1);

		que[++tail]=(node){a[i],i};

	}

	tail=0;

	for(LL i=n;i>=1;--i){

		while(tail && que[tail].val<=a[i]) --tail;

		R[i]=(tail?que[tail].x-1:n);

		que[++tail]=(node){a[i],i};

	}

}

inline void Fir_Q(){

	for(LL i=1;i<=n;++i)

		if(i-L[i]<=R[i]-i){

			for(LL j=L[i];j<=i;++j)

				Q[R[i]].push_back(a[i]/a[j]),

				Q[i-1].push_back(-a[i]/a[j]);

		}else{

			for(LL j=i;j<=R[i];++j)

				Q[i].push_back(a[i]/a[j]),

				Q[L[i]-1].push_back(-a[i]/a[j]);

		}

}

struct Tree_k{

	LL tree[maxn];

	inline LL Lowbit(LL x){ return x&-x; }

	inline void Add(LL x,LL val){

		for(;x<=cnt;x+=Lowbit(x)) tree[x]+=val;

	}

	inline LL Query(LL x){

		LL ret(0);

		for(;x;x-=Lowbit(x)) ret+=tree[x]; return ret;

	}

}Tk;

inline void Fir_S(){

	LL ret(0);

	for(LL i=1;i<=n;++i){

		Tk.Add(a[i],1);

		for(LL j=0;j<Q[i].size();++j){

			LL val(Q[i][j]);

			LL x(abs(val)>=b[cnt]?cnt:upper_bound(b+1,b+1+cnt,abs(val))-b-1);

			ret+=(val>0?1:-1)*Tk.Query(x);

		}

	}

	cout<<ret;

}

int main(){

	cin>>n;

	for(LL i=1;i<=n;++i) cin>>a[i],b[i]=a[i];

	Fir_LR();

	Fir_Q();

	sort(b+1,b+1+n), cnt=unique(b+1,b+1+n)-b-1;

	for(LL i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;//,cout<<a[i]<<' ';cout<<endl;

	Fir_S();

}

巴特西

P4755 Beautiful Pair

题目

做法

My complete code

最新文章

热门文章