【线段树二分查找】P3939数颜色|普及+

本文涉及知识点

C++线段树 C++二分查找

P3939 数颜色 题目背景

大样例可在页面底部「附件」中下载。

题目描述

小 C 的兔子不是雪白的，而是五彩缤纷的。每只兔子都有一种颜色，不同的兔子可能有 相同的颜色。小 C 把她标号从 1 到 n n n 的 n n n 只兔子排成长长的一排，来给他们喂胡萝卜吃。 排列完成后，第 i i i 只兔子的颜色是 a i a_i ai​。

俗话说得好，“萝卜青菜，各有所爱”。小 C 发现，不同颜色的兔子可能有对胡萝卜的 不同偏好。比如，银色的兔子最喜欢吃金色的胡萝卜，金色的兔子更喜欢吃胡萝卜叶子，而 绿色的兔子却喜欢吃酸一点的胡萝卜……为了满足兔子们的要求，小 C 十分苦恼。所以，为 了使得胡萝卜喂得更加准确，小 C 想知道在区间 [ l j , r j ] [l_j,r_j] [lj​,rj​] 里有多少只颜色为 c j c_j cj​ 的兔子。

不过，因为小 C 的兔子们都十分地活跃，它们不是很愿意待在一个固定的位置；与此同 时，小 C 也在根据她知道的信息来给兔子们调整位置。所以，有时编号为 x j x_j xj​ 和 x j + 1 x_j+1 xj​+1 的两 只兔子会交换位置。 小 C 被这一系列麻烦事给难住了。你能帮帮她吗？

输入格式

从标准输入中读入数据。 输入第 1 行两个正整数 n n n, m m m。

输入第 2 行 n n n 个正整数，第 i i i 个数表示第 i i i 只兔子的颜色 a i a_i ai​。

输入接下来 m m m 行，每行为以下两种中的一种：

“ 1   l j   r j   c j 1\ l_j\ r_j\ c_j 1 lj​ rj​ cj​” ：询问在区间 [ l j , r j ] [l_j,r_j] [lj​,rj​] 里有多少只颜色为 c j c_j cj​ 的兔子；

“ 2   x j 2\ x_j 2 xj​”： x j x_j xj​ 和 x j + 1 x_j+1 xj​+1 两只兔子交换了位置。

输出格式

输出到标准输出中。

对于每个 1 操作，输出一行一个正整数，表示你对于这个询问的答案。

输入输出样例 #1 输入 #1 6 5 1 2 3 2 3 3 1 1 3 2 1 4 6 3 2 3 1 1 3 2 1 4 6 3 输出 #1 1 2 2 3 说明/提示

【样例 1 说明】

前两个 1 操作和后两个 1 操作对应相同；在第三次的 2 操作后，3 号兔子和 4 号兔子

交换了位置，序列变为 1 2 2 3 3 3。

【数据范围与约定】

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解 决一部分测试数据。 对于所有测试点，有 1 ≤ l j < r j ≤ n , 1 ≤ x j < n 1 \le l_j < r_j \le n,1 \le x_j < n 1≤lj​<rj​≤n,1≤xj​<n。 每个测试点的数据规模及特点如下表：

特殊性质 1：保证对于所有操作 1，有 ∣ r j − l j ∣ ≤ 20 |r_j - l_j| \le 20 ∣rj​−lj​∣≤20 或 ∣ r j − l j ∣ ≤ n − 20 |r_j - l_j| \le n - 20 ∣rj​−lj​∣≤n−20。

特殊性质 2：保证不会有两只相同颜色的兔子。

P3939 数颜色

令颜色的最大值是MC，则每种颜色开一棵线段树，单点更新，动态开点。求和，如果此树是当前颜色，为1，否则为0。 空间复杂度：O(MC+N+M)。不能静态开点，否则内存超限。

代码 核心代码（卡常）

最后几个用例超内存

#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 T = int> vector<T> Read() { int n; scanf("%d", &n); vector<T> ret(n); for (int i = 0; i < n; i++) { cin >> ret[i]; } 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 = 12 * 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; } inline void write(char ch) { *m_p++ = ch; } inline void ToFile() { fwrite(puffer, 1, m_p - puffer, stdout); } private: char puffer[N], * m_p; }; template<int N = 12 * 1'000'000> class CInBuff { public: inline CInBuff() { fread(buffer, 1, N, stdin); } inline int Read() { int x(0), f(0); while (!isdigit(*S)) f |= (*S++ == '-'); while (isdigit(*S)) x = (x << 1) + (x << 3) + (*S++ ^ 48); return f ? -x : x; } private: char buffer[N], * S = buffer; }; template<class TSave, class TRecord > class CSingeUpdateLineTree { protected: virtual void OnInit(TSave& save, int iSave) = 0; virtual void OnQuery(TSave& ans, const TSave& cur) = 0; virtual void OnUpdate(TSave& save, int iSave, const TRecord& update) = 0; virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0; }; template<class TSave, class TRecord > class CVectorSingUpdateLineTree : public CSingeUpdateLineTree<TSave, TRecord> { public: CVectorSingUpdateLineTree(int iEleSize, TSave tDefault) :m_iEleSize(iEleSize), m_save(iEleSize * 4, tDefault), m_tDefault(tDefault) { } void Update(int index, TRecord update) { Update(1, 0, m_iEleSize - 1, index, update); } TSave Query(int leftIndex, int leftRight) { TSave ans; Query(1, 0, m_iEleSize - 1, leftIndex, leftRight); return ans; } void Init() { Init(1, 0, m_iEleSize - 1); } TSave QueryAll() { return m_save[1]; } protected: int m_iEleSize; void Init(int iNodeNO, int iSaveLeft, int iSaveRight) { if (iSaveLeft == iSaveRight) { this->OnInit(m_save[iNodeNO], iSaveLeft); return; } const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; Init(iNodeNO * 2, iSaveLeft, mid); Init(iNodeNO * 2 + 1, mid + 1, iSaveRight); this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight); } void Query(TSave& ans, int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) { if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) { this->OnQuery(ans, m_save[iNodeNO]); return; } if (iSaveLeft == iSaveRight) {//没有子节点 return; } const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; if (mid >= iQueryLeft) { Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight); } if (mid + 1 <= iQueryRight) { Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight); } } void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) { if (iSaveLeft == iSaveRight) { this->OnUpdate(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); } this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight); } vector<TSave> m_save; const TSave m_tDefault; }; template<class TSave, class TRecord > class CTreeSingeLineTree : public CSingeUpdateLineTree<TSave, TRecord> { protected: struct CTreeNode { int Cnt()const { return m_iMaxIndex - m_iMinIndex + 1; } int m_iMinIndex; int m_iMaxIndex; TSave data; CTreeNode* m_lChild = nullptr, * m_rChild = nullptr; }; CTreeNode* m_root; TSave m_tDefault; public: CTreeSingeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault) { m_tDefault = tDefault; m_root = CreateNode(iMinIndex, iMaxIndex); } void Init() { Init(m_root); } void Update(int index, TRecord update) { Update(m_root, index, update); } TSave QueryAll() { return m_root->data; } TSave Query(int leftIndex, int leftRight) { TSave ans = m_tDefault; Query(ans, m_root, leftIndex, leftRight); return ans; } protected: void Query(TSave& ans, CTreeNode* node, int iQueryLeft, int iQueryRight) { if ((node->m_iMinIndex >= iQueryLeft) && (node->m_iMaxIndex <= iQueryRight)) { this->OnQuery(ans, node->data); return; } if (1 == node->Cnt()) {//没有子节点 return; } CreateChilds(node); const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2; if (mid >= iQueryLeft) { Query(ans, node->m_lChild, iQueryLeft, iQueryRight); } if (mid + 1 <= iQueryRight) { Query(ans, node->m_rChild, iQueryLeft, iQueryRight); } } void Init(CTreeNode* node) { if (1 == node->Cnt()) { this->OnInit(node->data, node->m_iMinIndex); return; } CreateChilds(node); Init(node->m_lChild); Init(node->m_rChild); this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data, node->m_iMinIndex, node->m_iMaxIndex); } void Update(CTreeNode* node, int iUpdateNO, TRecord update) { if ((iUpdateNO < node->m_iMinIndex) || (iUpdateNO > node->m_iMaxIndex)) { return; } if (1 == node->Cnt()) { this->OnUpdate(node->data, node->m_iMinIndex, update); return; } CreateChilds(node); Update(node->m_lChild, iUpdateNO, update); Update(node->m_rChild, iUpdateNO, update); this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data, node->m_iMinIndex, node->m_iMaxIndex); } void CreateChilds(CTreeNode* node) { if (nullptr != node->m_lChild) { return; } const int iSaveLeft = node->m_iMinIndex; const int iSaveRight = node->m_iMaxIndex; const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; node->m_lChild = CreateNode(iSaveLeft, mid); node->m_rChild = CreateNode(mid + 1, iSaveRight); } CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) { CTreeNode* node = new CTreeNode; node->m_iMinIndex = iMinIndex; node->m_iMaxIndex = iMaxIndex; node->data = m_tDefault; return node; } }; typedef int TSave; typedef int TRecord; class CMyLineTree : public CTreeSingeLineTree<TSave, TRecord> { public: using CTreeSingeLineTree<TSave, TRecord>::CTreeSingeLineTree; protected: virtual void OnInit(TSave& save, int iSave) {} virtual void OnQuery(TSave& ans, const TSave& cur) { ans += cur; } virtual void OnUpdate(TSave& save, int iSave, const TRecord& update) { save += update; } virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) { par = left + r; } }; class Solution { public: vector<int> Ans(vector<int>& a, vector<tuple<int, int, int>>& que) { const int N = a.size(); int M = *max_element(a.begin(), a.end()); vector<CMyLineTree*> lineTrees; for (int i = 0; i <= M; i++) { lineTrees.emplace_back(new CMyLineTree(1, N, 0)); } for (int i = 1; i <= N; i++) { lineTrees[a[i - 1]]->Update(i, 1); } vector<int> ans; for (const auto& [left, r, c] : que) { if (0 != r) { if (c > M) { ans.emplace_back(0); } else { ans.emplace_back(lineTrees[c]->Query(left, r)); } } else { lineTrees[a[left - 1]]->Update(left, -1); lineTrees[a[left]]->Update(left + 1, -1); swap(a[left - 1], a[left]); lineTrees[a[left - 1]]->Update(left, 1); lineTrees[a[left]]->Update(left + 1, 1); } } return ans; } }; int main() { #ifdef _DEBUG freopen("a.in", "r", stdin); #endif // DEBUG int n,q; cin >> n >> q; auto a = Read<int>(n); vector<tuple<int, int, int>> que(q); int kind; for (int i = 0; i < q; i++) { cin >> kind >> get<0>(que[i]) ; if (1 == kind) { cin >> get<1>(que[i]) >> get<2>(que[i]); } } #ifdef _DEBUG /*printf("T=%d,", T);*/ /*Out(a, "a="); Out(que, "que=");*/ #endif // DEBUG auto res = Solution().Ans(a,que); for (const auto& i : res) { cout << i << endl; } return 0; } 优化

修改模板，牺牲简洁性或通用性来提升性质。作为工程师很反感。如果某个颜色没被查询，则不为此颜色建树。一种颜色最后一次查询时，delete。此方法不可行，还是内存超限。

#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 T = int> vector<T> Read() { int n; scanf("%d", &n); vector<T> ret(n); for (int i = 0; i < n; i++) { cin >> ret[i]; } 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 = 12 * 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; } inline void write(char ch) { *m_p++ = ch; } inline void ToFile() { fwrite(puffer, 1, m_p - puffer, stdout); } private: char puffer[N], * m_p; }; template<int N = 12 * 1'000'000> class CInBuff { public: inline CInBuff() { fread(buffer, 1, N, stdin); } inline int Read() { int x(0), f(0); while (!isdigit(*S)) f |= (*S++ == '-'); while (isdigit(*S)) x = (x << 1) + (x << 3) + (*S++ ^ 48); return f ? -x : x; } private: char buffer[N], * S = buffer; }; template<class TSave, class TRecord > class CSingeUpdateLineTree { protected: virtual void OnInit(TSave& save, int iSave) = 0; virtual void OnQuery(TSave& ans, const TSave& cur) = 0; virtual void OnUpdate(TSave& save, int iSave, const TRecord& update) = 0; virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0; }; template<class TSave, class TRecord > class CVectorSingUpdateLineTree : public CSingeUpdateLineTree<TSave, TRecord> { public: CVectorSingUpdateLineTree(int iEleSize, TSave tDefault) :m_iEleSize(iEleSize), m_save(iEleSize * 4, tDefault), m_tDefault(tDefault) { } void Update(int index, TRecord update) { Update(1, 0, m_iEleSize - 1, index, update); } TSave Query(int leftIndex, int leftRight) { TSave ans; Query(1, 0, m_iEleSize - 1, leftIndex, leftRight); return ans; } void Init() { Init(1, 0, m_iEleSize - 1); } TSave QueryAll() { return m_save[1]; } protected: int m_iEleSize; void Init(int iNodeNO, int iSaveLeft, int iSaveRight) { if (iSaveLeft == iSaveRight) { this->OnInit(m_save[iNodeNO], iSaveLeft); return; } const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; Init(iNodeNO * 2, iSaveLeft, mid); Init(iNodeNO * 2 + 1, mid + 1, iSaveRight); this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight); } void Query(TSave& ans, int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) { if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) { this->OnQuery(ans, m_save[iNodeNO]); return; } if (iSaveLeft == iSaveRight) {//没有子节点 return; } const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; if (mid >= iQueryLeft) { Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight); } if (mid + 1 <= iQueryRight) { Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight); } } void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) { if (iSaveLeft == iSaveRight) { this->OnUpdate(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); } this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight); } vector<TSave> m_save; const TSave m_tDefault; }; template<class TSave, class TRecord > class CTreeSingeLineTree : public CSingeUpdateLineTree<TSave, TRecord> { protected: struct CTreeNode { int Cnt()const { return m_iMaxIndex - m_iMinIndex + 1; } int m_iMinIndex; int m_iMaxIndex; 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; TSave m_tDefault; public: CTreeSingeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault) { m_tDefault = tDefault; m_root = CreateNode(iMinIndex, iMaxIndex); } void Init() { Init(m_root); } void Update(int index, TRecord update) { Update(m_root, index, update); } TSave QueryAll() { return m_root->data; } TSave Query(int leftIndex, int leftRight) { TSave ans = m_tDefault; Query(ans, m_root, leftIndex, leftRight); return ans; } ~CTreeSingeLineTree() { delete m_root; } protected: void Query(TSave& ans, CTreeNode* node, int iQueryLeft, int iQueryRight) { if ((node->m_iMinIndex >= iQueryLeft) && (node->m_iMaxIndex <= iQueryRight)) { this->OnQuery(ans, node->data); return; } if (1 == node->Cnt()) {//没有子节点 return; } CreateChilds(node); const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2; if (mid >= iQueryLeft) { Query(ans, node->m_lChild, iQueryLeft, iQueryRight); } if (mid + 1 <= iQueryRight) { Query(ans, node->m_rChild, iQueryLeft, iQueryRight); } } void Init(CTreeNode* node) { if (1 == node->Cnt()) { this->OnInit(node->data, node->m_iMinIndex); return; } CreateChilds(node); Init(node->m_lChild); Init(node->m_rChild); this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data, node->m_iMinIndex, node->m_iMaxIndex); } void Update(CTreeNode* node, int iUpdateNO, TRecord update) { if ((iUpdateNO < node->m_iMinIndex) || (iUpdateNO > node->m_iMaxIndex)) { return; } if (1 == node->Cnt()) { this->OnUpdate(node->data, node->m_iMinIndex, update); return; } CreateChilds(node); Update(node->m_lChild, iUpdateNO, update); Update(node->m_rChild, iUpdateNO, update); this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data, node->m_iMinIndex, node->m_iMaxIndex); } void CreateChilds(CTreeNode* node) { if (nullptr != node->m_lChild) { return; } const int iSaveLeft = node->m_iMinIndex; const int iSaveRight = node->m_iMaxIndex; const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; node->m_lChild = CreateNode(iSaveLeft, mid); node->m_rChild = CreateNode(mid + 1, iSaveRight); } CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) { CTreeNode* node = new CTreeNode; node->m_iMinIndex = iMinIndex; node->m_iMaxIndex = iMaxIndex; node->data = m_tDefault; return node; } }; typedef int TSave; typedef int TRecord; class CMyLineTree : public CTreeSingeLineTree<TSave, TRecord> { public: using CTreeSingeLineTree<TSave, TRecord>::CTreeSingeLineTree; protected: virtual void OnInit(TSave& save, int iSave) {} virtual void OnQuery(TSave& ans, const TSave& cur) { ans += cur; } virtual void OnUpdate(TSave& save, int iSave, const TRecord& update) { save += update; } virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) { par = left + r; } }; class Solution { public: vector<int> Ans(vector<int>& a, vector<tuple<int, int, int>>& que) { const int N = a.size(); int M = *max_element(a.begin(), a.end()); vector<int> queCnt(M + 1); for (int i = 0; i < que.size(); i++) { const int c = get<2>(que[i]); if (c > M) { continue; } queCnt[c]++; } vector<CMyLineTree*> lineTrees(M + 1); for (int i = 0; i <= M; i++) { if (0 == queCnt[i])continue; lineTrees[i] = new CMyLineTree(1, N, 0); } for (int i = 1; i <= N; i++) { if (nullptr == lineTrees[a[i - 1]]) { continue; } lineTrees[a[i - 1]]->Update(i, 1); } auto Update = [&](int color, int x, int val) { if (nullptr == lineTrees[color]) { return; } lineTrees[color]->Update(x, val); }; vector<int> ans; for (const auto& [left, r, c] : que) { if (0 != r) { if ((c > M) || (nullptr == lineTrees[c])) { ans.emplace_back(0); } else { ans.emplace_back(lineTrees[c]->Query(left, r)); queCnt[c]--; if (0 == queCnt[c]) { delete lineTrees[c]; lineTrees[c] = nullptr; } } } else { Update(a[left - 1], left, -1); Update(a[left], left + 1, -1); swap(a[left - 1], a[left]); Update(a[left - 1], left, 1); Update(a[left], left + 1, 1); } } return ans; } }; int main() { #ifdef _DEBUG freopen("a.in", "r", stdin); #endif // DEBUG int n,q; cin >> n >> q; auto a = Read<int>(n); vector<tuple<int, int, int>> que(q); int kind; for (int i = 0; i < q; i++) { cin >> kind >> get<0>(que[i]) ; if (1 == kind) { cin >> get<1>(que[i]) >> get<2>(que[i]); } } #ifdef _DEBUG /*printf("T=%d,", T);*/ /*Out(a, "a="); Out(que, "que=");*/ #endif // DEBUG auto res = Solution().Ans(a,que); for (const auto& i : res) { cout << i << endl; } return 0; } delete在洛谷用部分用 int main() { vector<int*> v(300); for (int i = 0; i < 300; i++) { v[i] = new int[1024 * 1024]; if (i >= 10) { delete v[i - 10]; v[i - 10] = nullptr; } } return 0; }

实验了两次，都是一个样例22M，其它样例1M 以内。

再次优化

20个节点，只用向量。超过20个节点用动态线段树。 优化前，有7个超过或接近256M，优化后最高占用60M内存，其它最多20M。线段树的节点越多，公共祖先越多。

#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 T = int> vector<T> Read() { int n; scanf("%d", &n); vector<T> ret(n); for (int i = 0; i < n; i++) { cin >> ret[i]; } 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(); } 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 = 12 * 1'000'000> class CInBuff { public: inline CInBuff() { fread(buffer, 1, N, stdin); } inline int Read() { int x(0), f(0); while (!isdigit(*S)) f |= (*S++ == '-'); while (isdigit(*S)) x = (x << 1) + (x << 3) + (*S++ ^ 48); return f ? -x : x; } private: char buffer[N], * S = buffer; }; template<class TSave, class TRecord > class CSingeUpdateLineTree { protected: virtual void OnInit(TSave& save, int iSave) = 0; virtual void OnQuery(TSave& ans, const TSave& cur) = 0; virtual void OnUpdate(TSave& save, int iSave, const TRecord& update) = 0; virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0; }; template<class TSave, class TRecord > class CVectorSingUpdateLineTree : public CSingeUpdateLineTree<TSave, TRecord> { public: CVectorSingUpdateLineTree(int iEleSize, TSave tDefault) :m_iEleSize(iEleSize), m_save(iEleSize * 4, tDefault), m_tDefault(tDefault) { } void Update(int index, TRecord update) { Update(1, 0, m_iEleSize - 1, index, update); } TSave Query(int leftIndex, int leftRight) { TSave ans; Query(1, 0, m_iEleSize - 1, leftIndex, leftRight); return ans; } void Init() { Init(1, 0, m_iEleSize - 1); } TSave QueryAll() { return m_save[1]; } protected: int m_iEleSize; void Init(int iNodeNO, int iSaveLeft, int iSaveRight) { if (iSaveLeft == iSaveRight) { this->OnInit(m_save[iNodeNO], iSaveLeft); return; } const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; Init(iNodeNO * 2, iSaveLeft, mid); Init(iNodeNO * 2 + 1, mid + 1, iSaveRight); this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight); } void Query(TSave& ans, int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) { if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) { this->OnQuery(ans, m_save[iNodeNO]); return; } if (iSaveLeft == iSaveRight) {//没有子节点 return; } const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; if (mid >= iQueryLeft) { Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight); } if (mid + 1 <= iQueryRight) { Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight); } } void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) { if (iSaveLeft == iSaveRight) { this->OnUpdate(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); } this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight); } vector<TSave> m_save; const TSave m_tDefault; }; template<class TSave, class TRecord > class CTreeSingeLineTree : public CSingeUpdateLineTree<TSave, TRecord> { protected: struct CTreeNode { int Cnt()const { return m_iMaxIndex - m_iMinIndex + 1; } int m_iMinIndex; int m_iMaxIndex; 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; TSave m_tDefault; public: CTreeSingeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault) { m_tDefault = tDefault; m_root = CreateNode(iMinIndex, iMaxIndex); } void Init() { Init(m_root); } void Update(int index, TRecord update) { Update(m_root, index, update); } TSave QueryAll() { return m_root->data; } TSave Query(int leftIndex, int leftRight) { TSave ans = m_tDefault; Query(ans, m_root, leftIndex, leftRight); return ans; } ~CTreeSingeLineTree() { delete m_root; } protected: void Query(TSave& ans, CTreeNode* node, int iQueryLeft, int iQueryRight) { if ((node->m_iMinIndex >= iQueryLeft) && (node->m_iMaxIndex <= iQueryRight)) { this->OnQuery(ans, node->data); return; } if (1 == node->Cnt()) {//没有子节点 return; } CreateChilds(node); const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2; if (mid >= iQueryLeft) { Query(ans, node->m_lChild, iQueryLeft, iQueryRight); } if (mid + 1 <= iQueryRight) { Query(ans, node->m_rChild, iQueryLeft, iQueryRight); } } void Init(CTreeNode* node) { if (1 == node->Cnt()) { this->OnInit(node->data, node->m_iMinIndex); return; } CreateChilds(node); Init(node->m_lChild); Init(node->m_rChild); this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data, node->m_iMinIndex, node->m_iMaxIndex); } void Update(CTreeNode* node, int iUpdateNO, TRecord update) { if ((iUpdateNO < node->m_iMinIndex) || (iUpdateNO > node->m_iMaxIndex)) { return; } if (1 == node->Cnt()) { this->OnUpdate(node->data, node->m_iMinIndex, update); return; } CreateChilds(node); Update(node->m_lChild, iUpdateNO, update); Update(node->m_rChild, iUpdateNO, update); this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data, node->m_iMinIndex, node->m_iMaxIndex); } void CreateChilds(CTreeNode* node) { if (nullptr != node->m_lChild) { return; } const int iSaveLeft = node->m_iMinIndex; const int iSaveRight = node->m_iMaxIndex; const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; node->m_lChild = CreateNode(iSaveLeft, mid); node->m_rChild = CreateNode(mid + 1, iSaveRight); } CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) { CTreeNode* node = new CTreeNode; node->m_iMinIndex = iMinIndex; node->m_iMaxIndex = iMaxIndex; node->data = m_tDefault; return node; } }; typedef int TSave; typedef int TRecord; class CMyLineTree : public CTreeSingeLineTree<TSave, TRecord> { public: using CTreeSingeLineTree<TSave, TRecord>::CTreeSingeLineTree; protected: virtual void OnInit(TSave& save, int iSave) {} virtual void OnQuery(TSave& ans, const TSave& cur) { ans += cur; } virtual void OnUpdate(TSave& save, int iSave, const TRecord& update) { save += update; } virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) { par = left + r; } }; class Solution { public: vector<int> Ans(vector<int>& a, vector<tuple<int, int, int>>& que) { const int N = a.size(); int M = *max_element(a.begin(), a.end()); vector<int> colorCnt(M + 1); for (const auto& i : a) { colorCnt[i]++; } vector<CMyLineTree*> lineTrees(M + 1); vector<vector<int>> v(M + 1); for (int i = 0; i <= M; i++) { if (colorCnt[i] <= 20) { continue; } lineTrees[i] = new CMyLineTree(1, N, 0); } for (int i = 1; i <= N; i++) { if (colorCnt[a[i - 1]] <= 20) { v[a[i - 1]].emplace_back(i); continue; } lineTrees[a[i - 1]]->Update(i, 1); } auto Update = [&](int color, int x, int val) { if (colorCnt[color] <= 20) { if (-1 == val) { for (auto& i : v[color]) { if (x == i) { i = -1; break; } } } else { for (auto& i : v[color]) { if (-1 == i) { i = x; break; } } } } else { lineTrees[color]->Update(x, val); } }; vector<int> ans; for (const auto& [left, r, c] : que) { if (0 != r) { if (c > M) { ans.emplace_back(0); } else if (colorCnt[c] <= 20) { auto it1 = lower_bound(v[c].begin(), v[c].end(), left); auto it2 = upper_bound(v[c].begin(), v[c].end(), r); ans.emplace_back(it2 - it1); } else { ans.emplace_back(lineTrees[c]->Query(left, r)); } } else { Update(a[left - 1], left, -1); Update(a[left], left + 1, -1); swap(a[left - 1], a[left]); Update(a[left - 1], left, 1); Update(a[left], left + 1, 1); } } return ans; } }; int main() { #ifdef _DEBUG freopen("a.in", "r", stdin); #endif // DEBUG int n,q; cin >> n >> q; auto a = Read<int>(n); vector<tuple<int, int, int>> que(q); int kind; for (int i = 0; i < q; i++) { cin >> kind >> get<0>(que[i]) ; if (1 == kind) { cin >> get<1>(que[i]) >> get<2>(que[i]); } } #ifdef _DEBUG /*printf("T=%d,", T);*/ /*Out(a, "a="); Out(que, "que=");*/ #endif // DEBUG auto res = Solution().Ans(a,que); COutBuff bf; for (const auto& i : res ) { bf.write(i); bf.write('\n'); } return 0; } 二分查找

用有序集合记录各颜色的下标，然后二分查找。 本题非常巧，可以用向量代替。本题不需要增加、删除向量元素，只需要修改，且修改后依然游戏。 令x的颜色是c,x+1的颜色是c2。 it 指向v[c][x] ，(*it)++ it2指向v[c2][x+1] ,(*it)–。 注意：c1和c2相等，忽略。

代码 #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 T = int> vector<T> Read() { int n; scanf("%d", &n); vector<T> ret(n); for (int i = 0; i < n; i++) { cin >> ret[i]; } 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(); } 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 = 12 * 1'000'000> class CInBuff { public: inline CInBuff() { fread(buffer, 1, N, stdin); } inline int Read() { int x(0), f(0); while (!isdigit(*S)) f |= (*S++ == '-'); while (isdigit(*S)) x = (x << 1) + (x << 3) + (*S++ ^ 48); return f ? -x : x; } private: char buffer[N], * S = buffer; }; template<class TSave, class TRecord > class CSingeUpdateLineTree { protected: virtual void OnInit(TSave& save, int iSave) = 0; virtual void OnQuery(TSave& ans, const TSave& cur) = 0; virtual void OnUpdate(TSave& save, int iSave, const TRecord& update) = 0; virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0; }; template<class TSave, class TRecord > class CVectorSingUpdateLineTree : public CSingeUpdateLineTree<TSave, TRecord> { public: CVectorSingUpdateLineTree(int iEleSize, TSave tDefault) :m_iEleSize(iEleSize), m_save(iEleSize * 4, tDefault), m_tDefault(tDefault) { } void Update(int index, TRecord update) { Update(1, 0, m_iEleSize - 1, index, update); } TSave Query(int leftIndex, int leftRight) { TSave ans; Query(1, 0, m_iEleSize - 1, leftIndex, leftRight); return ans; } void Init() { Init(1, 0, m_iEleSize - 1); } TSave QueryAll() { return m_save[1]; } protected: int m_iEleSize; void Init(int iNodeNO, int iSaveLeft, int iSaveRight) { if (iSaveLeft == iSaveRight) { this->OnInit(m_save[iNodeNO], iSaveLeft); return; } const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; Init(iNodeNO * 2, iSaveLeft, mid); Init(iNodeNO * 2 + 1, mid + 1, iSaveRight); this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight); } void Query(TSave& ans, int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) { if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) { this->OnQuery(ans, m_save[iNodeNO]); return; } if (iSaveLeft == iSaveRight) {//没有子节点 return; } const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; if (mid >= iQueryLeft) { Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight); } if (mid + 1 <= iQueryRight) { Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight); } } void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) { if (iSaveLeft == iSaveRight) { this->OnUpdate(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); } this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight); } vector<TSave> m_save; const TSave m_tDefault; }; template<class TSave, class TRecord > class CTreeSingeLineTree : public CSingeUpdateLineTree<TSave, TRecord> { protected: struct CTreeNode { int Cnt()const { return m_iMaxIndex - m_iMinIndex + 1; } int m_iMinIndex; int m_iMaxIndex; 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; TSave m_tDefault; public: CTreeSingeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault) { m_tDefault = tDefault; m_root = CreateNode(iMinIndex, iMaxIndex); } void Init() { Init(m_root); } void Update(int index, TRecord update) { Update(m_root, index, update); } TSave QueryAll() { return m_root->data; } TSave Query(int leftIndex, int leftRight) { TSave ans = m_tDefault; Query(ans, m_root, leftIndex, leftRight); return ans; } ~CTreeSingeLineTree() { delete m_root; } protected: void Query(TSave& ans, CTreeNode* node, int iQueryLeft, int iQueryRight) { if ((node->m_iMinIndex >= iQueryLeft) && (node->m_iMaxIndex <= iQueryRight)) { this->OnQuery(ans, node->data); return; } if (1 == node->Cnt()) {//没有子节点 return; } CreateChilds(node); const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2; if (mid >= iQueryLeft) { Query(ans, node->m_lChild, iQueryLeft, iQueryRight); } if (mid + 1 <= iQueryRight) { Query(ans, node->m_rChild, iQueryLeft, iQueryRight); } } void Init(CTreeNode* node) { if (1 == node->Cnt()) { this->OnInit(node->data, node->m_iMinIndex); return; } CreateChilds(node); Init(node->m_lChild); Init(node->m_rChild); this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data, node->m_iMinIndex, node->m_iMaxIndex); } void Update(CTreeNode* node, int iUpdateNO, TRecord update) { if ((iUpdateNO < node->m_iMinIndex) || (iUpdateNO > node->m_iMaxIndex)) { return; } if (1 == node->Cnt()) { this->OnUpdate(node->data, node->m_iMinIndex, update); return; } CreateChilds(node); Update(node->m_lChild, iUpdateNO, update); Update(node->m_rChild, iUpdateNO, update); this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data, node->m_iMinIndex, node->m_iMaxIndex); } void CreateChilds(CTreeNode* node) { if (nullptr != node->m_lChild) { return; } const int iSaveLeft = node->m_iMinIndex; const int iSaveRight = node->m_iMaxIndex; const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; node->m_lChild = CreateNode(iSaveLeft, mid); node->m_rChild = CreateNode(mid + 1, iSaveRight); } CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) { CTreeNode* node = new CTreeNode; node->m_iMinIndex = iMinIndex; node->m_iMaxIndex = iMaxIndex; node->data = m_tDefault; return node; } }; class Solution { public: vector<int> Ans(vector<int>& a, vector<tuple<int, int, int>>& que) { const int N = a.size(); int M = *max_element(a.begin(), a.end()); vector<vector<int>> v(M + 1); for (int i = 1; i <= N; i++) { v[a[i - 1]].emplace_back(i); } vector<int> ans; for (const auto& [left, r, c] : que) { if (0 != r) { if (c > M) { ans.emplace_back(0); } else { auto it1 = lower_bound(v[c].begin(), v[c].end(), left); auto it2 = upper_bound(v[c].begin(), v[c].end(), r); ans.emplace_back(it2 - it1); } } else { const auto c1 = a[left - 1]; const auto c2 = a[left]; if (c1 == c2) { continue; } auto it1 = lower_bound(v[c1].begin(), v[c1].end(), left); auto it2 = lower_bound(v[c2].begin(), v[c2].end(), left + 1); (*it1)++; (*it2)--; swap(a[left - 1], a[left]); } } return ans; } }; int main() { #ifdef _DEBUG freopen("a.in", "r", stdin); #endif // DEBUG int n,q; cin >> n >> q; auto a = Read<int>(n); vector<tuple<int, int, int>> que(q); int kind; for (int i = 0; i < q; i++) { cin >> kind >> get<0>(que[i]) ; if (1 == kind) { cin >> get<1>(que[i]) >> get<2>(que[i]); } } #ifdef _DEBUG /*printf("T=%d,", T);*/ /*Out(a, "a="); Out(que, "que=");*/ #endif // DEBUG auto res = Solution().Ans(a,que); COutBuff bf; for (const auto& i : res ) { bf.write(i); bf.write('\n'); } return 0; } 扩展阅读 我想对大家说的话工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙，那算法就是他的是睛失败+反思=成功 成功+反思=成功 视频课程

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

测试环境

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