本文涉及知识点
C++线段树(Segment Tree）一：正确性证明、模板及封装类及样例
P9290 [ROI 2018] Decryption
题目背景
译自 ROI 2018 Day2 T1. Расшифровка (Decryption)。
题目描述
研究表明，汉字的顺序并不一定能影响阅读。科学家们对数列进行了类似的研究。
给一个正整数数列，若数列首项为数列中所有数的最小值，末项为数列中的最大值，则我们称这是个正确的数列。例如，序列 [ 1 , 3 , 2 , 4 ] [1, 3, 2, 4] [1,3,2,4] 和 [ 1 , 2 , 1 , 2 ] [1, 2, 1, 2] [1,2,1,2] 是正确的，但序列
[ 1 , 3 , 2 ] [1, 3, 2] [1,3,2] 不是。
给出长度为 n 的序列 [ a 1 , a 2 , … , a n ] [a_1, a_2, \ldots, a_n] [a1,a2,…,an]。对于该序列的某个片段 [ a l , a l + 1 , … , a r ] [a_l, a_{l+1}, \ldots, a_r] [al,al+1,…,ar], 若该片段的首项为该片段中的最小值，末项为该片段中的最大值，则我们称这是个正确的片段。
对于给定的序列，请求出该序列至少需要被分成多少段，才能使得每个片段均为正确的片段。序列 [ 2 , 3 , 1 , 1 , 5 , 1 ] [2, 3, 1, 1, 5, 1] [2,3,1,1,5,1] 可以分为三个正确的段： [ 2 , 3 ] [2, 3] [2,3] 和 [ 1 , 1 , 5 ] [1, 1, 5] [1,1,5] 和 [ 1 ] [1] [1]。
需要编写一个程序，该程序按给定的顺序确定可以划分的最小正确段数。
输入格式
第一行一个整数 n n n。
接下来一行 n n n 个数，分别为 a 1 , a 2 , … , a n a_1,a_2,\ldots,a_n a1,a2,…,an。
输出格式
输出可以划分的最小正确段数。
输入输出样例 #1
输入 #1
5
5 4 3 2 1
输出 #1
5
输入输出样例 #2
输入 #2
4
1 3 2 4
输出 #2
1
输入输出样例 #3
输入 #3
6
2 3 1 1 5 1
输出 #3
3
说明/提示
- 子任务 1（30 分）， 1 ≤ n ≤ 500 1 \leq n \leq 500 1≤n≤500。
- 子任务 2（30 分）， 1 ≤ n ≤ 5000 1 \leq n \leq 5000 1≤n≤5000。
- 子任务 3（40 分）， 1 ≤ n ≤ 3 × 1 0 5 1 \leq n \leq3 \times 10^5 1≤n≤3×105。
对于所有数据， 1 ≤ n ≤ 3 × 1 0 5 1 \leq n \leq3 \times 10^5 1≤n≤3×105， 1 ≤ a i ≤ 1 0 9 1\leq a_i \leq 10^9 1≤ai≤109。
单调栈 线段树
大致思路：枚举j，求所有使得nums[ i ⋯ j i\cdots j i⋯j]合法的i。
性质一：k从小到大将nums[k]入栈sta1。当栈顶元素nums[m]>nums[k]出栈。k入栈。
如果m出栈，则 ∀ , j ≥ k \forall,j \ge k ∀,j≥k,nums[m ⋯ j ] \cdots j] ⋯j]一定非法。因为nums[m]> nums[k]。
性质二：k从小到大将nums[k]入栈sta2。当栈顶元素 ≤ \le ≤nums[k]时，出栈。nums[sta2.top() ⋯ \cdots ⋯ k-1]都 ≤ \le ≤nums[k]。 ∀ , i ≤ s t a 2. t o p ( ) \forall,i \le sta2.top() ∀,i≤sta2.top(),nums[ i ⋯ j ] i\cdots j] i⋯j]一定非法。因为sta2.top 大于 nums[j]。
性质三：为了避免处理边界，sta2初始包括一个元素-1。符合以下条件的nums[ i ⋯ j ] i \cdots j] i⋯j]一档合法。
一， i > s t a 2. t o p ( ) i > sta2.top() i>sta2.top()。二，i ∈ s t a 1 \in sta1 ∈sta1。
符合条件一，则nums[j]一定是最大值。符合条件二，说明nums[i]是最小值，否则出栈了。
sg[i]记录nums长度为i的前缀的最少段数。如果m从sta1出栈，则sg[m]= INT_MAX/2。
dp[i+1] = sg[sta2.top()+1 ⋯ \cdots ⋯i]的最小值+1。
线段树
单点更新 区间查询 静态开点。
回调类型：设置 最小值。
代码
核心代码
#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<list>
#include <bitset>
using namespace std;
template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
in >> pr.first >> pr.second;
return in;
}
template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t);
return in;
}
template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
return in;
}
template<class T1, class T2, class T3, class T4, class T5 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);
return in;
}
template<class T1, class T2, class T3, class T4, class T5, class T6 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5, T6>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t);
return in;
}
template<class T = int>
vector<T> Read() {
int n;
cin >> n;
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
vector<T> ret;
T tmp;
while (cin >> tmp) {
ret.emplace_back(tmp);
if ('\n' == cin.get()) { break; }
}
return ret;
}
template<class T = int>
vector<T> Read(int n) {
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}
template<int N = 1'000'000>
class COutBuff
{
public:
COutBuff() {
m_p = puffer;
}
template<class T>
void write(T x) {
int num[28], sp = 0;
if (x < 0)
*m_p++ = '-', x = -x;
if (!x)
*m_p++ = 48;
while (x)
num[++sp] = x % 10, x /= 10;
while (sp)
*m_p++ = num[sp--] + 48;
AuotToFile();
}
void writestr(const char* sz) {
strcpy(m_p, sz);
m_p += strlen(sz);
AuotToFile();
}
inline void write(char ch)
{
*m_p++ = ch;
AuotToFile();
}
inline void ToFile() {
fwrite(puffer, 1, m_p - puffer, stdout);
m_p = puffer;
}
~COutBuff() {
ToFile();
}
private:
inline void AuotToFile() {
if (m_p - puffer > N - 100) {
ToFile();
}
}
char puffer[N], * m_p;
};
template<int N = 1'000'000>
class CInBuff
{
public:
inline CInBuff() {}
inline CInBuff<N>& operator>>(char& ch) {
FileToBuf();
ch = *S++;
return *this;
}
inline CInBuff<N>& operator>>(int& val) {
FileToBuf();
int x(0), f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x << 1) + (x << 3) + (*S++ ^ 48);
val = f ? -x : x; S++;//忽略空格换行
return *this;
}
inline CInBuff& operator>>(long long& val) {
FileToBuf();
long long x(0); int f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x << 1) + (x << 3) + (*S++ ^ 48);
val = f ? -x : x; S++;//忽略空格换行
return *this;
}
template<class T1, class T2>
inline CInBuff& operator>>(pair<T1, T2>& val) {
*this >> val.first >> val.second;
return *this;
}
template<class T1, class T2, class T3>
inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
return *this;
}
template<class T1, class T2, class T3, class T4>
inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
return *this;
}
template<class T = int>
inline CInBuff& operator>>(vector<T>& val) {
int n;
*this >> n;
val.resize(n);
for (int i = 0; i < n; i++) {
*this >> val[i];
}
return *this;
}
template<class T = int>
vector<T> Read(int n) {
vector<T> ret(n);
for (int i = 0; i < n; i++) {
*this >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> Read() {
vector<T> ret;
*this >> ret;
return ret;
}
private:
inline void FileToBuf() {
const int canRead = m_iWritePos - (S - buffer);
if (canRead >= 100) { return; }
if (m_bFinish) { return; }
for (int i = 0; i < canRead; i++)
{
buffer[i] = S[i];//memcpy出错
}
m_iWritePos = canRead;
buffer[m_iWritePos] = 0;
S = buffer;
int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
if (readCnt <= 0) { m_bFinish = true; return; }
m_iWritePos += readCnt;
buffer[m_iWritePos] = 0;
S = buffer;
}
int m_iWritePos = 0; bool m_bFinish = false;
char buffer[N + 10], * S = buffer;
};
template<class TSave, class TSet >
class ISegmentTreeCall
{
public:
virtual void OnUnion(TSave& unionVal, const TSave& leftVal, const TSave& rVal, int leftIndex, int mid, int rIndex) = 0;
};
template<class TSave, class TSet >
class ISingleSegmentTreeCall : public ISegmentTreeCall<TSave, TSet>
{
public:
virtual void OnUpdateLeaf(TSave& save, int iSaveIndex, const TSet& update) = 0;
};
template<class TSave, class TSet >
class IRangleSegmentTreeCall : public ISingleSegmentTreeCall<TSave, TSet>
{
public:
virtual void OnUnionSet(TSet& oldBuff, const TSet& newBuff) = 0;
virtual void OnUpdateBranch(TSave& save, int iLeftIndex, int iRightIndex, const TSet& update) = 0;
};
template<class TSave, class TSet >
class CSegmentTree {
public:
CSegmentTree(ISegmentTreeCall<TSave, TSet>& call, TSave tDefault)
:m_call(call), m_tDefault(tDefault) {}
TSave Query(int left, int r) {
return Query(left, r, m_tDefault);
}
TSave Query(int left, int r, TSave tDefault) {
TSave ans = tDefault;
std::function<void(const TSave&, const int&, const int&)> fun = [&](const TSave& cur, const int& leftIndex, const int& rIndex) {
m_call.OnUnion(ans, ans, cur, left, leftIndex - 1, rIndex);
};
Enum(left, r, fun);
return ans;
}
virtual void Enum(int leftIndex, int leftRight, std::function<void(const TSave&, const int&, const int&)>& fun) = 0;
virtual TSave QueryAll() = 0;
protected:
ISegmentTreeCall<TSave, TSet>& m_call;
const TSave m_tDefault;
};
template<class TSave = int, class TSet = int >
class CSetMinSegmentTreeCall :public IRangleSegmentTreeCall <TSave, TSet> {
public:
virtual void OnUpdateLeaf(TSave& save, int iSaveIndex, const TSet& update)
{
save = update;
}
virtual void OnUnion(TSave& unionVal, const TSave& leftVal, const TSave& rVal, int leftIndex, int mid, int rIndex) {
unionVal = min(leftVal, rVal);
}
virtual void OnUnionSet(TSet& oldBuff, const TSet& newBuff) {
oldBuff = newBuff;
}
virtual void OnUpdateBranch(TSave& save, int iLeftIndex, int iRightIndex, const TSet& update) {
save = update;
}
};
template<class TSave, class TSet >
class CSingeSegmentTree :public CSegmentTree<TSave, TSet>
{
public:
CSingeSegmentTree(ISingleSegmentTreeCall<TSave, TSet>& call, TSave tDefault)
:m_call(call), CSegmentTree<TSave, TSet>(call, tDefault) {}
virtual void Update(int index, TSet update) = 0;
protected:
ISingleSegmentTreeCall<TSave, TSet>& m_call;
};
template<class TSave, class TSet >
class CSingeTreeSegmentTree : public CSingeSegmentTree<TSave, TSet>
{
protected:
struct CTreeNode
{
TSave data;
CTreeNode* m_lChild = nullptr, * m_rChild = nullptr;
~CTreeNode() {
delete m_lChild; m_lChild = nullptr;
delete m_rChild; m_rChild = nullptr;
}
};
CTreeNode* m_root;
const int m_iMinIndex, m_iMaxIndex;
public:
CSingeTreeSegmentTree(int iMinIndex, int iMaxIndex, ISingleSegmentTreeCall<TSave, TSet>& call, TSave tDefault) :CSingeSegmentTree<TSave, TSet>(call, tDefault)
, m_iMinIndex(iMinIndex), m_iMaxIndex(iMaxIndex) {
m_root = CreateNode();
}
void Update(int index, TSet update) override {
if ((index < m_iMinIndex) || (index > m_iMaxIndex)) { return; }
Update(m_root, m_iMinIndex, m_iMaxIndex, index, update);
}
TSave QueryAll() override {
return m_root->data;
}
//void OnQuery(TSave& ans, const TSave& cur, const int& iSaveLeft, const int& iSaveRight);
void Enum(int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun)override {
if (max(iQueryLeft, m_iMinIndex) > min(iQueryRight, m_iMaxIndex)) { return; }//和根节点没交集
Enum(m_root, m_iMinIndex, m_iMaxIndex, iQueryLeft, iQueryRight, fun);
}
~CSingeTreeSegmentTree() {
delete m_root;
}
protected:
void Enum(CTreeNode* node, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) {
if ((iQueryLeft <= iSaveLeft) && (iSaveRight <= iQueryRight)) {
fun(node->data, iSaveLeft, iSaveRight);
return;
}
CreateChilds(node);
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (mid >= iQueryLeft) {
Enum(node->m_lChild, iSaveLeft, mid, iQueryLeft, iQueryRight, fun);
}
if (mid + 1 <= iQueryRight) {
Enum(node->m_rChild, mid + 1, iSaveRight, iQueryLeft, iQueryRight, fun);
}
}
void Update(CTreeNode* node, int iSaveLeft, int iSaveRight, int iUpdateNO, TSet update) {
if (iSaveLeft == iSaveRight) {
CSingeSegmentTree<TSave, TSet>::m_call.OnUpdateLeaf(node->data, iUpdateNO, update);
return;
}
CreateChilds(node);
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (iUpdateNO <= mid)
{
Update(node->m_lChild, iSaveLeft, mid, iUpdateNO, update);
}
else {
Update(node->m_rChild, mid + 1, iSaveRight, iUpdateNO, update);
}
CSingeSegmentTree<TSave, TSet>::m_call.OnUnion(node->data, node->m_lChild->data, node->m_rChild->data, iSaveLeft, mid, iSaveRight);
}
CTreeNode* CreateNode() {
CTreeNode* node = new CTreeNode;
node->data = this->m_tDefault;
return node;
}
void CreateChilds(CTreeNode* node) {
if (nullptr != node->m_lChild) { return; }
node->m_lChild = CreateNode();
node->m_rChild = CreateNode();
}
};
template<class TSave, class TSet >
class CSingleVectorSegmentTree : public CSingeSegmentTree<TSave, TSet>
{
public:
CSingleVectorSegmentTree(int iEleSize, ISingleSegmentTreeCall<TSave, TSet>& call, TSave tDefault) :
m_iEleSize(iEleSize), CSingeSegmentTree<TSave, TSet>(call, tDefault), m_save(iEleSize * 4, tDefault) {
}
void Update(int index, TSet update) override {
if ((index < 0) || (index >= m_iEleSize)) { return; }
Update(1, 0, m_iEleSize - 1, index, update);
}
TSave QueryAll() override {
return m_save[1];
}
virtual void Enum(int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) override {
if (max(iQueryLeft, 0) > min(iQueryRight, m_iEleSize - 1)) { return; }//和根节点没交集
Enum(1, 0, m_iEleSize - 1, iQueryLeft, iQueryRight, fun);
}
void swap(CSingleVectorSegmentTree& o) {
m_save.swap(o.m_save);
}
protected:
const int m_iEleSize;
/* void Init(std::function<void(TSave&, const int&)> fun, int iNodeNO, int iSaveLeft, int iSaveRight)
{
if (iSaveLeft == iSaveRight) {
fun(m_save[iNodeNO], iSaveLeft);
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
Init(fun, iNodeNO * 2, iSaveLeft, mid);
Init(fun, iNodeNO * 2 + 1, mid + 1, iSaveRight);
this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
}*/
void Enum(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight, std::function<void(const TSave&, const int&, const int&)>& fun) {
if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
fun(m_save[iNodeNO], iSaveLeft, iSaveRight);
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (mid >= iQueryLeft) {
Enum(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight, fun);
}
if (mid + 1 <= iQueryRight) {
Enum(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight, fun);
}
}
void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TSet update) {
if (iSaveLeft == iSaveRight)
{
CSingeSegmentTree<TSave, TSet>::m_call.OnUpdateLeaf(m_save[iNodeNO], iSaveLeft, update);
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (iUpdateNO <= mid) {
Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
}
else {
Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
}
CSegmentTree<TSave, TSet>::m_call.OnUnion(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, mid, iSaveRight);
}
vector<TSave> m_save;
};
class Solution {
public:
int Ans(vector<int>& nums) {
const int N = nums.size();
vector<int> sta1 = { -1 }, sta2 = { -1 };
CSetMinSegmentTreeCall<int, int> call;
CSingleVectorSegmentTree<int, int> sg(N + 1, call, INT_MAX / 2);
sg.Update(0, 0);
for (int i = 0;i < N;i++) {
while ((-1 != sta1.back()) && (nums[sta1.back()] > nums[i])) {
sg.Update(sta1.back(), INT_MAX / 2);
sta1.pop_back();
}
while ((-1 != sta2.back()) && (nums[sta2.back()] <= nums[i])) {
sta2.pop_back();
}
const int cur = sg.Query(sta2.back() + 1, i) + 1;
sg.Update(i + 1, cur);
sta1.emplace_back(i);
sta2.emplace_back(i);
}
return sg.Query(N, N);
}
};
int main() {
#ifdef _DEBUG
freopen("a.in", "r", stdin);
#endif // DEBUG
ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
auto nums = Read<int>();
#ifdef _DEBUG
/*printf("T=%d,", T);*/
Out(nums, "nums=");
//Out(que, "que=");
#endif // DEBUG
auto res = Solution().Ans(nums);
cout << res << "\r\n";
return 0;
}
单元测试
vector<int> nums;
TEST_METHOD(TestMethod11)
{
nums = { 5,4,3,2,1 };
auto res = Solution().Ans(nums);
AssertEx(5, res);
}
TEST_METHOD(TestMethod12)
{
nums = { 1,3,2,4 };
auto res = Solution().Ans(nums);
AssertEx(1, res);
}
TEST_METHOD(TestMethod13)
{
nums = { 2,3,1,1,5,1 };
auto res = Solution().Ans(nums);
AssertEx(3, 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++**实现。
