【BFS 树状数组】P9026 [CCC 2021 S4] Daily Commute|普及+

本文涉及知识点

C++BFS算法 【C++】树状数组的使用、原理、封装类、样例

P9026 [CCC 2021 S4] Daily Commute

题目描述

已知有

N

N

N 个地铁站，你家在

1

1

1，学校在

N

N

N。

有

W

W

W 条单向人行道。经过需要一分钟。

此外还有一条环形地铁线路，依次经过

S

1

,

S

2

,

⋯
 

,

S

N

S_1,S_2,\\cdots,S_N

S1​,S2​,⋯,SN​，且保证

S

1

=

1

S_1=1

S1​=1。每天有且仅有一辆地铁在

0

0

0 时刻从

S

1

S_1

S1​ 出发，并且恰好在第

i

i

i 分钟到达

S

i

S_i

Si​。

在接下来

D

D

D 天中：

• 交换 $S_{X_i}$
• 查询从 $1$

输入格式

第一行：

N

,

W

,

D

N,W,D

N,W,D。

接下来

W

W

W 行：

A

i

,

B

i

A_i,B_i

Ai​,Bi​ 表示单向人行道。

接下来一行

N

N

N 个数：

S

S

S。

接下来

D

D

D 行：

X

i

,

Y

i

X_i,Y_i

Xi​,Yi​，保证

2

≤

X

i

,

Y

i

≤

N

,

X

i

≠

Y

i

2\\leq X_i,Y_i\\leq N,X_i\\neq Y_i

2≤Xi​,Yi​≤N,Xi​=Yi​。

输出格式

D

D

D 行，每天的答案。

输入输出样例 #1

输入 #1

4 3 3
1 2
3 4
4 1
1 4 3 2
3 4
4 2
3 2

输出 #1

1
2
3

说明/提示

3

≤

N

≤

200000

,

0

≤

W

≤

200000

,

1

≤

D

≤

200000

3\\leq N\\leq 200000,0\\leq W\\leq 200000,1\\leq D\\leq 200000

3≤N≤200000,0≤W≤200000,1≤D≤200000

译自 CCC2021 S4。

请注意常数。

[CCC 2021 S4] 最小值树状数组 BFS

步行边反向，利用BFS求终点到各点的距离w[i]。treeArr[i]记录到坐车到i站，再步行的时间。 b[i] 记录S的逆排列，即b[s[i]] = i，到x站的时间就是b[x]。 treeArr[x] = b[x] + w[x]每次交换只更改b和treeArr的两个值。 时间复杂度：O(nlogn) 不能最小树状数组，因为：值可能变大。 这样无法更新区间最小值。可以用线段树或有序集合。

代码

核心代码

#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<array>

#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;
cin >> n;
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
vector<T> ret;
T tmp;
while (cin >> tmp) {
ret.emplace_back(tmp);
if ('\\n' == cin.get()) { break; }
}
return ret;
}

template<class T = int>
vector<T> Read(int n) {
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}

template<int N = 1'000'000>
class COutBuff
{
public:
COutBuff() {
m_p = puffer;
}
template<class T>
void write(T x) {
int num[28], sp = 0;
if (x < 0)
*m_p++ = '-', x = –x;

if (!x)
*m_p++ = 48;

while (x)
num[++sp] = x % 10, x /= 10;

while (sp)
*m_p++ = num[sp—] + 48;
AuotToFile();
}
void writestr(const char* sz) {
strcpy(m_p, sz);
m_p += strlen(sz);
AuotToFile();
}
inline void write(char ch)
{
*m_p++ = ch;
AuotToFile();
}
inline void ToFile() {
fwrite(puffer, 1, m_p – puffer, stdout);
m_p = puffer;
}
~COutBuff() {
ToFile();
}
private:
inline void AuotToFile() {
if (m_p – puffer > N – 100) {
ToFile();
}
}
char puffer[N], * m_p;
};

template<int N = 1'000'000>
class CInBuff
{
public:
inline CInBuff() {}
inline CInBuff<N>& operator>>(char& ch) {
FileToBuf();
while (('\\r' == *S) || ('\\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车
ch = *S++;
return *this;
}
inline CInBuff<N>& operator>>(int& val) {
FileToBuf();
int x(0), f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x << 1) + (x << 3) + (*S++ ^ 48);
val = f ? –x : x; S++;//忽略空格换行
return *this;
}
inline CInBuff& operator>>(long long& val) {
FileToBuf();
long long x(0); int f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x << 1) + (x << 3) + (*S++ ^ 48);
val = f ? –x : x; S++;//忽略空格换行
return *this;
}
template<class T1, class T2>
inline CInBuff& operator>>(pair<T1, T2>& val) {
*this >> val.first >> val.second;
return *this;
}
template<class T1, class T2, class T3>
inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
return *this;
}
template<class T1, class T2, class T3, class T4>
inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
return *this;
}
template<class T = int>
inline CInBuff& operator>>(vector<T>& val) {
int n;
*this >> n;
val.resize(n);
for (int i = 0; i < n; i++) {
*this >> val[i];
}
return *this;
}
template<class T = int>
vector<T> Read(int n) {
vector<T> ret(n);
for (int i = 0; i < n; i++) {
*this >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> Read() {
vector<T> ret;
*this >> ret;
return ret;
}
private:
inline void FileToBuf() {
const int canRead = m_iWritePos – (S – buffer);
if (canRead >= 100) { return; }
if (m_bFinish) { return; }
for (int i = 0; i < canRead; i++)
{
buffer[i] = S[i];//memcpy出错
}
m_iWritePos = canRead;
buffer[m_iWritePos] = 0;
S = buffer;
int readCnt = fread(buffer + m_iWritePos, 1, N – m_iWritePos, stdin);
if (readCnt <= 0) { m_bFinish = true; return; }
m_iWritePos += readCnt;
buffer[m_iWritePos] = 0;
S = buffer;
}
int m_iWritePos = 0; bool m_bFinish = false;
char buffer[N + 10], * S = buffer;
};

class CBFSDis
{
public:
CBFSDis(vector<vector<int>>& vNeiB, vector<int> start)
{
m_vDis.assign(vNeiB.size(), m_iNotMayDis);
queue<int> que;
for (const auto& n : start)
{
m_vDis[n] = 0;
que.emplace(n);
}
while (que.size())
{
const int cur = que.front();
que.pop();
for (const auto next : vNeiB[cur])
{
if (m_iNotMayDis != m_vDis[next])
{
continue;
}
m_vDis[next] = m_vDis[cur] + 1;
que.emplace(next);
}
}
}
public:
const int m_iNotMayDis = 1e9;
vector<int> m_vDis;
};

class Solution {
public:
vector<int> Ans(const int N, vector<pair<int, int>>& edge, vector<int>& S, vector<pair<int, int>>& change) {
S.insert(S.begin(), 0);
vector<vector<int>> neiBo(N + 1);
for (const auto& [u, v] : edge) {
neiBo[v].emplace_back(u);
}
const auto& dis = CBFSDis(neiBo, { N }).m_vDis;
vector<int> np(N + 1);
for (int i = 1; i <= N; i++) {
np[S[i]] = i;
}
multiset<int> mind;
auto Add = [&](int i) {
mind.emplace(np[i] – 1 + dis[i]);
};
auto Sub = [&](int i) {
mind.erase(mind.find(np[i] – 1 + dis[i]));
};
for (int i = 1; i <= N; i++) {
Add(i);
}
vector<int> ans;
for (const auto& [x, y] : change) {
Sub(S[x]);
Sub(S[y]);
swap(S[x], S[y]);
swap(np[S[x]], np[S[y]]);
Add(S[x]);
Add(S[y]);
ans.emplace_back(*mind.begin());
}
return ans;
}
};

int main() {
#ifdef _DEBUG
freopen("a.in", "r", stdin);
#endif // DEBUG
//ios::sync_with_stdio(0); cin.tie(nullptr);
CInBuff<> in; COutBuff<10'000'000> ob;
int N, W, D;
cin >> N >> W >> D ;
auto edge = Read<pair<int, int>>(W);
auto s = Read<int>(N);
auto change = Read<pair<int, int>>(D);
auto res = Solution().Ans(N,edge,s,change);

#ifdef _DEBUG
printf("N=%d", N);
Out(s, ",s=");
Out(edge, ",edge=");
Out(change, ",change=");
//Out(B, "B=");
//Out(que, "que=");
//Out(B, "B=");
#endif // DEBUG
for (const auto& i : res) {
cout << i << "\\n";
}
return 0;
}

单元测试

int N;
vector<pair<int, int>> edge, change;
vector<int> s;
TEST_METHOD(TestMethod1)
{
N = 4, s = { 1,4,3,2 }, edge = { {1,2},{3,4},{4,1} }, change = { {3,4},{4,2},{3,2} };
auto res = Solution().Ans(N, edge, s, change);
AssertEx({1,2,3}, res);
}

扩展阅读

视频课程

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

测试环境

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