建设银行个人网站打不开,网站表单点击切换,wordpress更改固定链接,做网站互联网公司本文涉及知识点
C线段树 C二分查找
P3939 数颜色
题目背景
大样例可在页面底部「附件」中下载。
题目描述
小 C 的兔子不是雪白的#xff0c;而是五彩缤纷的。每只兔子都有一种颜色#xff0c;不同的兔子可能有 相同的颜色。小 C 把她标号从 1 到 n n n 的 n n n 只兔…本文涉及知识点
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_j1 xj1 的两 只兔子会交换位置。 小 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_j1 xj1 两只兔子交换了位置。
输出格式
输出到标准输出中。
对于每个 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≤ljrj≤n,1≤xjn。 每个测试点的数据规模及特点如下表 特殊性质 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(MCNM)。不能静态开点否则内存超限。
代码
核心代码卡常
最后几个用例超内存
#include iostream
#include sstream
#include vector
#includemap
#includeunordered_map
#includeset
#includeunordered_set
#includestring
#includealgorithm
#includefunctional
#includequeue
#include stack
#includeiomanip
#includenumeric
#include math.h
#include climits
#includeassert.h
#includecstring
#includelist#include bitset
using namespace std;templateclass T1, class T2
std::istream operator (std::istream in, pairT1, T2 pr) {in pr.first pr.second;return in;
}templateclass T1, class T2, class T3
std::istream operator (std::istream in, tupleT1, T2, T3 t) {in get0(t) get1(t) get2(t);return in;
}templateclass T1, class T2, class T3, class T4
std::istream operator (std::istream in, tupleT1, T2, T3, T4 t) {in get0(t) get1(t) get2(t) get3(t);return in;
}templateclass T int
vectorT Read() {int n;scanf(%d, n);vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateclass T int
vectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateint N 12 * 1000000
class COutBuff
{
public:COutBuff() {m_p puffer;}templateclass Tvoid 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;
};templateint N 12 * 1000000
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;
};templateclass 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;
};templateclass TSave, class TRecord
class CVectorSingUpdateLineTree : public CSingeUpdateLineTreeTSave, 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);}vectorTSave m_save;const TSave m_tDefault;
};templateclass TSave, class TRecord
class CTreeSingeLineTree : public CSingeUpdateLineTreeTSave, 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 CTreeSingeLineTreeTSave, TRecord
{
public:using CTreeSingeLineTreeTSave, 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:vectorint Ans(vectorint a, vectortupleint, int, int que) {const int N a.size();int M *max_element(a.begin(), a.end());vectorCMyLineTree* 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);}vectorint 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 Readint(n);vectortupleint, int, int que(q);int kind;for (int i 0; i q; i) {cin kind get0(que[i]) ;if (1 kind) {cin get1(que[i]) get2(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
#includemap
#includeunordered_map
#includeset
#includeunordered_set
#includestring
#includealgorithm
#includefunctional
#includequeue
#include stack
#includeiomanip
#includenumeric
#include math.h
#include climits
#includeassert.h
#includecstring
#includelist#include bitset
using namespace std;templateclass T1, class T2
std::istream operator (std::istream in, pairT1, T2 pr) {in pr.first pr.second;return in;
}templateclass T1, class T2, class T3
std::istream operator (std::istream in, tupleT1, T2, T3 t) {in get0(t) get1(t) get2(t);return in;
}templateclass T1, class T2, class T3, class T4
std::istream operator (std::istream in, tupleT1, T2, T3, T4 t) {in get0(t) get1(t) get2(t) get3(t);return in;
}templateclass T int
vectorT Read() {int n;scanf(%d, n);vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateclass T int
vectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateint N 12 * 1000000
class COutBuff
{
public:COutBuff() {m_p puffer;}templateclass Tvoid 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;
};templateint N 12 * 1000000
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;
};templateclass 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;
};templateclass TSave, class TRecord
class CVectorSingUpdateLineTree : public CSingeUpdateLineTreeTSave, 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);}vectorTSave m_save;const TSave m_tDefault;
};templateclass TSave, class TRecord
class CTreeSingeLineTree : public CSingeUpdateLineTreeTSave, 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 CTreeSingeLineTreeTSave, TRecord
{
public:using CTreeSingeLineTreeTSave, 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:vectorint Ans(vectorint a, vectortupleint, int, int que) {const int N a.size();int M *max_element(a.begin(), a.end());vectorint queCnt(M 1);for (int i 0; i que.size(); i) {const int c get2(que[i]);if (c M) { continue; }queCnt[c];}vectorCMyLineTree* 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);};vectorint 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 Readint(n);vectortupleint, int, int que(q);int kind;for (int i 0; i q; i) {cin kind get0(que[i]) ;if (1 kind) {cin get1(que[i]) get2(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() { vectorint* 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
#includemap
#includeunordered_map
#includeset
#includeunordered_set
#includestring
#includealgorithm
#includefunctional
#includequeue
#include stack
#includeiomanip
#includenumeric
#include math.h
#include climits
#includeassert.h
#includecstring
#includelist#include bitset
using namespace std;templateclass T1, class T2
std::istream operator (std::istream in, pairT1, T2 pr) {in pr.first pr.second;return in;
}templateclass T1, class T2, class T3
std::istream operator (std::istream in, tupleT1, T2, T3 t) {in get0(t) get1(t) get2(t);return in;
}templateclass T1, class T2, class T3, class T4
std::istream operator (std::istream in, tupleT1, T2, T3, T4 t) {in get0(t) get1(t) get2(t) get3(t);return in;
}templateclass T int
vectorT Read() {int n;scanf(%d, n);vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateclass T int
vectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateint N 1000000
class COutBuff
{
public:COutBuff() {m_p puffer;}templateclass Tvoid 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;
};templateint N 12 * 1000000
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;
};templateclass 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;
};templateclass TSave, class TRecord
class CVectorSingUpdateLineTree : public CSingeUpdateLineTreeTSave, 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);}vectorTSave m_save;const TSave m_tDefault;
};templateclass TSave, class TRecord
class CTreeSingeLineTree : public CSingeUpdateLineTreeTSave, 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 CTreeSingeLineTreeTSave, TRecord
{
public:using CTreeSingeLineTreeTSave, 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:vectorint Ans(vectorint a, vectortupleint, int, int que) {const int N a.size();int M *max_element(a.begin(), a.end());vectorint colorCnt(M 1);for (const auto i : a) {colorCnt[i];}vectorCMyLineTree* lineTrees(M 1);vectorvectorint 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);}};vectorint 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 Readint(n);vectortupleint, int, int que(q);int kind;for (int i 0; i q; i) {cin kind get0(que[i]) ;if (1 kind) {cin get1(que[i]) get2(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,x1的颜色是c2。 it 指向v[c][x] (*it) it2指向v[c2][x1] ,(*it)–。 注意c1和c2相等忽略。
代码
#include iostream
#include sstream
#include vector
#includemap
#includeunordered_map
#includeset
#includeunordered_set
#includestring
#includealgorithm
#includefunctional
#includequeue
#include stack
#includeiomanip
#includenumeric
#include math.h
#include climits
#includeassert.h
#includecstring
#includelist#include bitset
using namespace std;templateclass T1, class T2
std::istream operator (std::istream in, pairT1, T2 pr) {in pr.first pr.second;return in;
}templateclass T1, class T2, class T3
std::istream operator (std::istream in, tupleT1, T2, T3 t) {in get0(t) get1(t) get2(t);return in;
}templateclass T1, class T2, class T3, class T4
std::istream operator (std::istream in, tupleT1, T2, T3, T4 t) {in get0(t) get1(t) get2(t) get3(t);return in;
}templateclass T int
vectorT Read() {int n;scanf(%d, n);vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateclass T int
vectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateint N 1000000
class COutBuff
{
public:COutBuff() {m_p puffer;}templateclass Tvoid 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;
};templateint N 12 * 1000000
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;
};templateclass 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;
};templateclass TSave, class TRecord
class CVectorSingUpdateLineTree : public CSingeUpdateLineTreeTSave, 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);}vectorTSave m_save;const TSave m_tDefault;
};templateclass TSave, class TRecord
class CTreeSingeLineTree : public CSingeUpdateLineTreeTSave, 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:vectorint Ans(vectorint a, vectortupleint, int, int que) {const int N a.size();int M *max_element(a.begin(), a.end());vectorvectorint v(M 1);for (int i 1; i N; i) {v[a[i - 1]].emplace_back(i);}vectorint 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 Readint(n);vectortupleint, int, int que(q);int kind;for (int i 0; i q; i) {cin kind get0(que[i]) ;if (1 kind) {cin get1(que[i]) get2(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学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
