CF1324D Pair of Topics

好像题解里都是树状数组(起码我翻到的是

说一种cdq分治的（这应该算是cdq分治了

用cdq比较简单，所以可以作为一个练手题

cdq分治其实是一种模糊的思想，处理\([l,r]\)区间内，有多少\((i,j)\)满足某种条件

这里假设\(i<j\)，我们取一个\(mid=\frac{i+j}{2}\)

\(i<j\leq mid\)，问题转换到区间\([l,mid]\)上解决
\(mid<i<j\)，问题转换到区间\([mid+1,r]\)上解决
\(i\leq mid <j\)，注意这里才是真正干活的地方，前面两种情况都是甩锅给更小的区间

然后具体看下这个题

条件是\(a_i+a_j>b_i+b_j(i<j)\)

可以转化为\(a_i-b_i>b_j-a_j(i<j)\)，其实就是把和\(i,j\)有关的项分别放在不等号两边

考虑\(i\leq mid<j\)的情况，则\(i<j\)这个条件已经没用了

开两个数组\(x,y\)，分别存\(a_i-b_i(l\leq i\leq mid)\)和\(b_j-a_j(mid<j\leq r)\)的值

然后给它们排个序

从小到大考虑x中元素，有几个y中元素比它小

具体实现用一个cnt变量，表示对于当前的x中的元素，有几个比它小的y中元素，然后每次\(ans=ans+cnt\)，，然后用两个指针分别指向x和y中当前的值就行了

每次对区间排序的复杂度是\(O(r-l+1)\)的，每个区间被排序\(\log n\)次（每次把一个区间分成它的一半，因此最多递归\(\log n\)层，每层）

画张丑陋的图理解一下

所以总时间复杂度\(O(n \log^2 n)\)

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline int read(){

	int x=0,y=1;

	char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

int n;

int a[200006],b[200006];

int x[200006],y[200006];

LL work(int l,int r){

	if(l==r) return 0;

	int mid=(l+r)>>1;

	x[0]=y[0]=0;

	for(reg int i=l;i<=mid;i++) x[++x[0]]=a[i]-b[i];

	for(reg int i=mid+1;i<=r;i++) y[++y[0]]=b[i]-a[i];

	std::sort(x+1,x+1+x[0]);std::sort(y+1,y+1+y[0]);

	reg int posl=1,posr=1,cnt=0;

	reg LL ans=0;

	for(;posl<=x[0];posl++){

		for(;posr<=y[0]&&y[posr]<x[posl];posr++) cnt++;

		ans+=cnt;

	}

	return ans+work(l,mid)+work(mid+1,r);

}

int main(){

	n=read();

	for(reg int i=1;i<=n;i++) a[i]=read();

	for(reg int i=1;i<=n;i++) b[i]=read();

	std::printf("%lld",work(1,n));

	return 0;

}

巴特西

CF1324D Pair of Topics

最新文章

热门文章