【树状数组 C++二分查找】P7333 [JRKSJ R1] JFCA|普及+

本文涉及的基础知识点

C++二分查找
树状数组
本博文代码打包下载

[JRKSJ R1] JFCA

题目描述

给出一个环，上面有 $n$ 个点，每个相邻的点对之间的距离为 $1$。

每个点有两个属性 $a_i$ 和 $b_i$，对于点 $i$，定义 $f_i$ 为它与满足 $a_j\ge b_i$ 的最近的点 $j$ 与 $i$ 在环上距离较短一边的长度，其中 $i\ne j$。如果没有满足条件的 $j$，其 $f_i=-1$。

输入格式

输入共 $3$ 行。
第 $1$ 行 $1$ 个整数 $n$ 。
第 $2$ 行 $n$ 个整数，其中第 $i$ 个表示 $a_i$，意义同上。
第 $3$ 行 $n$ 个整数，其中第 $i$ 个表示 $b_i$，意义同上。

输出格式

输出 $1$ 行 $n$ 个整数，其中第 $i$ 个表示 $f_i$，意义同上。

样例 #1

样例输入 #1

3
1 2 3
3 2 1

样例输出 #1

1 1 1

样例 #2

样例输入 #2

5
5 4 3 5 6
7 6 5 4 3

样例输出 #2

-1 2 1 1 1

样例 #3

样例输入 #3

5
1 1 2 1 1
2 2 2 2 2

样例输出 #3

2 1 -1 1 2

提示

对于 $20\%$ 的数据，$1\le n\le 10^3$；
对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le a_i,b_i\le 10^9$。

我们对于测试点 $4$ 至 $11$ 采用捆绑测试。

样例 1 解释

对于 $i=1$，$a_3=3=b_1=3$, $1$ 和 $3$ 的距离是 $1$，所以 $f_1=1$。
对于 $i=2$，$a_3=3>b_2=2$, $2$ 和 $3$ 的距离是 $1$，所以 $f_2=1$。
对于 $i=3$，$a_2=2>b_3=1$, $2$ 和 $3$ 的距离是 $1$，所以 $f_3=1$。

$\text{upd2021.3.30}$：增加一组 hack 数据，卡掉了@wu0615 的提交。

二分查找+树状数组

树状数组tree记录a的最大值。
通过i枚举a,b
Check函数参数范围：[1,n]
二分类型：寻找首端
返回值：Check(二分的返回值)?二分返回值：-1
a[i+1…i+mid]和[i-mid,i-1]的最大值是否大于等于b[i]。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>

#include <bitset>
using namespace std;



template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {
	vector<T> ret(n);
	for(int i=0;i<n;i++) {
		scanf(pFormat, &ret[i]);	
	}
	return ret;
}

template<class T = int>
vector<T> Read( const char* pFormat = "%d") {
	int n;
	scanf("%d", &n);
	vector<T> ret;
	T d;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

string ReadChar(int n) {
	string str;
	char ch;
	while (n--) {
		do
		{
			scanf("%c", &ch);
		} while (('\n' == ch));
			str += ch;
	}
	return str;
}
template<class T1,class T2>
void ReadTo(pair<T1, T2>& pr) {
	cin >> pr.first >> pr.second;
}

template<class T = int, T def = INT_MIN>
class CTreeArrMax
{
public:
	CTreeArrMax(int iEleSize) :m_iMax(iEleSize) {
		m_aMax.assign(iEleSize + 1, def);
		m_aRangMax.assign(iEleSize + 1, def);
	}
	void Modify(int indexBase0, T value)
	{
		indexBase0++;
		if (value <= m_aMax[indexBase0])
		{
			return;
		}
		m_aMax[indexBase0] = value;
		while (indexBase0 <= m_iMax)
		{
			m_aRangMax[indexBase0] = max(m_aRangMax[indexBase0], value);
			indexBase0 += BitLower(indexBase0);
		}
	}
	T Query(int leftBas0, int rBase0)
	{
		leftBas0++;
		rBase0++;
		leftBas0 = max(1, leftBas0);
		rBase0 = min(m_iMax, rBase0);
		T iMax = def;
		while (rBase0 >= leftBas0)
		{
			const int pre = rBase0 - BitLower(rBase0);
			if (pre + 1 >= leftBas0)
			{
				iMax = max(iMax, m_aRangMax[rBase0]);
				rBase0 = pre;
			}
			else
			{
				iMax = max(iMax, m_aMax[rBase0]);
				rBase0--;
			}
		}
		return iMax;
	}
protected:
	int BitLower(int x)
	{
		return x & (-x);
	}
	const int m_iMax;
	vector<T> m_aMax, m_aRangMax;
};

template<class INDEX_TYPE>
class CBinarySearch
{
public:
	CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex) :m_iMin(iMinIndex), m_iMax(iMaxIndex) {}
	template<class _Pr>
	INDEX_TYPE FindFrist(_Pr pr)
	{
		auto left = m_iMin - 1;
		auto rightInclue = m_iMax;
		while (rightInclue - left > 1)
		{
			const auto mid = left + (rightInclue - left) / 2;
			if (pr(mid))
			{
				rightInclue = mid;
			}
			else
			{
				left = mid;
			}
		}
		return rightInclue;
	}
	template<class _Pr>
	INDEX_TYPE FindEnd(_Pr pr)
	{
		INDEX_TYPE leftInclude = m_iMin;
		INDEX_TYPE right = m_iMax + 1;
		while (right - leftInclude > 1)
		{
			const auto mid = leftInclude + (right - leftInclude) / 2;
			if (pr(mid))
			{
				leftInclude = mid;
			}
			else
			{
				right = mid;
			}
		}
		return leftInclude;
	}
protected:
	const INDEX_TYPE m_iMin, m_iMax;
};

class Solution {
public:
	vector<int> Ans(vector<int>& a, vector<int>& b) {
		const int N = a.size();
		CTreeArrMax<int> tree(N);
		auto Max = [&](int left, int r) {
			left = (left + N) % N;
			r = (r + N) % N;
			if (left <= r) { return tree.Query(left, r); };
			const auto ret = max(tree.Query(left, N - 1), tree.Query(0, r));
			return ret;
		};
		for (int i = 0; i < N; i++) {
			tree.Modify(i, a[i]);
		}
		vector<int> ans(N);
		for (int i = 0; i < N; i++) {
			auto Check = [&](int mid)
			{
				return (Max(i + 1, i + mid) >= b[i]) || (Max(i - mid, i - 1) >= b[i]);
			};
			ans[i] = CBinarySearch(1, N - 1).FindFrist(Check);
			if (!Check(ans[i])) { ans[i] = -1; }
		}
		return ans;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	int n;	
	cin >> n;
	auto a = Read<int>(n);
	auto b = Read<int>(n);
	auto res = Solution().Ans(a,b);
	for(auto& i :res)
	{
		cout << i << " ";
	}	
#ifdef _DEBUG			
		Out(a, "a=");
		Out(b, "b=");
#endif			
	return 0;
}

单元测试

	vector<int> a,b;
		TEST_METHOD(TestMethod11)
		{
			a = { 1,2,3 },b = { 3,2,1 };
			auto res = Solution().Ans(a, b);
			AssertEx({ 1,1,1 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			a = { 5,4,3,5,6 },b = { 7,6,5,4,3 };
			auto res = Solution().Ans(a, b);
			AssertEx({ -1, 2, 1, 1 ,1 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			a = { 1,1,2,1,1 },b = { 2,2,2,2,2 }	;
			auto res = Solution().Ans(a, b);
			AssertEx({ 2, 1 ,- 1 ,1 ,2 }, res);
		}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。