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

我可以不吃啊 · 2025-2-18 08:14:00

本文涉及知识点

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学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
怎样你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

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

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云

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

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云

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