[USACO17FEB]Why Did the Cow Cross the Road III P

考虑我们对每种颜色记录这样一个信息 \((x,y,z)\)，即左边出现的位置，右边出现的位置，该颜色。

于是统计的是\(x < x_2,y > y_2,|z - z2| > k\)的数对数量。

因为\(CDQ\)分治的过程是，第一维事先排序，第二维递归进行，第三维用数据结构统计，所以

上述这个数量是很好处理的。

// Problem: P3658 [USACO17FEB]Why Did the Cow Cross the Road III P

// Contest: Luogu

// URL: https://www.luogu.com.cn/problem/P3658

// Memory Limit: 125 MB

// Time Limit: 1000 ms

//

// Powered by CP Editor (https://cpeditor.org)

#include<iostream>

#include<cstdio>

#include<map>

#include<algorithm>

#define ll long long

#define N 1000010

ll n,k,ans;

ll to[N];

struct P{

	int x,y,z;

}a[N],b[N];

bool operator < (P aa,P bb){

	return aa.x == bb.x ? ((aa.y == bb.y) ? (aa.z < bb.z) : aa.y > bb.y) : aa.x < bb.x;

}

ll t[N];

#define lowbit(x) (x & -x)

inline void add(int x,int u){

	for(int i = x;i <= n;i += lowbit(i))

	t[i] += u;

}

inline ll q(int x){

	x = std::max(x,0);

	x = std::min(n,(ll)x);

	ll ans = 0;

	for(int i = x;i;i -= lowbit(i))

	ans += t[i];

	return ans;

}

//_________BIT

#define mid ((l + r) >> 1)

inline void change(int l,int r){

	if(l == r)return;

	int i = l,j = mid + 1,p = l - 1;

	while(i <= mid && j <= r){if(a[i].y > a[j].y)b[++p] = a[i++];else b[++p] = a[j++];}

	while(i <= mid)b[++p] = a[i++];

	while(j <= r)b[++p] = a[j++];

	for(int k = l;k <= r;++k)

	a[k] = b[k];

}

inline void solve(int l,int r){

	if(l == r)return ;

	solve(l,mid);solve(mid + 1,r);change(l,mid);change(mid + 1,r);

	int i = l,j = mid + 1;

	while(j <= r){

		while(i <= mid && a[i].y > a[j].y)add(a[i++].z,1);

		ans = ans + (ll)q(a[j].z - k - 1) + (ll)q(n) - (ll)q(a[j].z + k);

		++j;

	}

	for(int k = l;k < i;++k)

	add(a[k].z,-1);

}

//————————————————————cdq

int main(){

	scanf("%lld%lld",&n,&k);

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

		ll x;

		scanf("%lld",&x);

		to[x] = i;

	}

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

		ll x;

		scanf("%lld",&x);

		a[i].x = to[x],a[i].y = i,a[i].z = x;

	}

	std::sort(a + 1,a + n + 1);

	solve(1,n);

	std::cout<<ans<<std::endl;

	return 0;

}

巴特西

[USACO17FEB]Why Did the Cow Cross the Road III P

[USACO17FEB]Why Did the Cow Cross the Road III P

最新文章

热门文章