CF803G Periodic RMQ Problem Solution

Description

给定序列 $b=(b_1,b_2,\cdots ,b_n)$ 和常数 $k$，将 $b$ 复制 $k$ 份拼接可以得到序列 $a$.
执行 $m$ 次操作，分为两种：

• $\mathrm{assign}(l,r,x)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow x$.
• $\mathrm{query}(l,r)$：求 $\underset{i=l}{\overset{r}{\min }}{a}_i$.

Limitations

$1\le n,m\le 10^5$
$1\le k\le 10^4$
$1\le b_i,x\le 10^9$
$1\le l\le r\le nk$
$4\text{s},512\text{MB}$

Solution

由于 $nk$ 可达 $10^9$，所以无法直接建出线段树.
考虑动态开点，每个节点维护最小值 $\text{min}$，标记 $\text{tag}$.
在建节点时，需要查询 $\underset{i=l}{\overset{r}{\min }}{a}_i$，分情况考虑（假设下标从 $0$ 开始）：

• 若 $\lfloor \frac{l}{n}\rfloor =\lfloor \frac{r}{n}\rfloor$，那么 $[l,r]$ 在同一段 $b$ 内，答案为 $\underset{i=l\mathrm{mod}n}{\overset{r\mathrm{mod}n}{\min }}{b}_i$.
• 若 $\lfloor \frac{l}{n}\rfloor +1=\lfloor \frac{r}{n}\rfloor$，那么 $[l,r]$ 在相邻两段内，答案为 $\min (\underset{i=r\mathrm{mod}n}{\overset{n-1}{\min }}{b}_i,\underset{i=1}{\overset{l\mathrm{mod}n}{\min }}{b}_i)$.
• 否则 $[l,r]$ 跨越了一整段，答案为 $\underset{i=0}{\overset{n-1}{\min }}{b}_i$.

为了不让复杂度退化，需要一个支持 $O(1)$ RMQ 的数据结构，使用 ST 表即可，总时间复杂度 $O(q\log nk)$.
如果用指针写线段树，注意结构体的所有变量都要初始化.

Code

$3.4\text{KB},1.39\text{s},231.64\text{MB}\text{(maximum, C++20)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}constexpr int inf = 2e9;
namespace seg_tree {struct Node {int l, r, min, tag;Node *ls, *rs;inline void pushup() { min = std::min(ls->min, rs->min); }inline void pushdown() {if (tag) {ls->apply(tag);rs->apply(tag);tag = 0;}}inline void apply(int _tag) { min = tag = _tag; }};struct SegTree {int n;Node* root;vector<vector<int>> f;vector<int> lg;inline SegTree() {}inline SegTree(const vector<int>& a, int k) {n = a.size();st_init(a);root = newnode(0, n * k - 1);}inline void st_init(const vector<int>& a) {lg.resize(n + 1);lg[0] = -1;for (int i = 1; i <= n; i++) lg[i] = lg[i / 2] + 1;f.resize(n, vector<int>(lg[n] + 1));for (int i = 0; i < n; i++) f[i][0] = a[i];for (int j = 1; j <= lg[n]; j++)for (int i = 0; i + (1 << j) - 1 < n; i++)f[i][j] = std::min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}inline int st_query(int l, int r) {int p = lg[r - l + 1];int res = std::min(f[l][p], f[r - (1 << p) + 1][p]);return res;}inline int rmq(int l, int r) {if (l / n == r / n) return st_query(l % n, r % n);if (l / n + 1 == r / n) {return std::min(st_query(l % n, n - 1), st_query(0, r % n));}return st_query(0, n - 1);}inline Node* newnode(int l, int r) {Node* res = new Node;res->l = l, res->r = r;res->min = rmq(l, r), res->tag = 0;res->ls = res->rs = nullptr;return res;}inline void update(Node* u, int l, int r, int k) {if (l <= u->l && u->r <= r) return u->apply(k);const int mid = (u->l + u->r) >> 1;if (u->ls == nullptr) u->ls = newnode(u->l, mid);if (u->rs == nullptr) u->rs = newnode(mid + 1, u->r);u->pushdown();if (l <= mid) update(u->ls, l, r, k);if (r > mid) update(u->rs, l, r, k);u->pushup();}inline int query(Node* u, int l, int r) {if (l <= u->l && u->r <= r) return u->min;const int mid = (u->l + u->r) >> 1;if (u->ls == nullptr) u->ls = newnode(u->l, mid);if (u->rs == nullptr) u->rs = newnode(mid + 1, u->r);u->pushdown();int res = inf;if (l <= mid) chmin(res, query(u->ls, l, r));if (r > mid) chmin(res, query(u->rs, l, r));return res;}inline void range_assign(int l, int r, int k) { update(root, l, r, k); }inline int range_min(int l, int r) { return query(root, l, r); }};
}
using seg_tree::SegTree;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, k;cin >> n >> k;vector<int> a(n);for (int i = 0; i < n; i++) cin >> a[i];int m; cin >> m;SegTree sgt(a, k);for (int i = 0, op, l, r, v; i < m; i++) {cin >> op >> l >> r, l--, r--;if (op == 1) cin >> v, sgt.range_assign(l, r, v);else cout << sgt.range_min(l, r) << '\n';}return 0;
}