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

本文涉及知识点

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

P3939 数颜色

题目背景

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

题目描述

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

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

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

输入格式

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

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

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

“ $1\ l_j\ r_j\ c_j$ ” ：询问在区间 $l_j,r_j]$ 里有多少只颜色为 $c_j$ 的兔子；
“ $2\ x_j$ ”： $x_j$ 和 $x_j+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 说明】

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

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

【数据范围与约定】

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

特殊性质 1：保证对于所有操作 1，有 $|r_j - l_j| \le 20$ 或 $|r_j - l_j| \le 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 _DEBUGfreopen("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 _DEBUGfreopen("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 _DEBUGfreopen("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 _DEBUGfreopen("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;
}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功