Codeforces Round #449 (Div. 1) Willem, Chtholly and Seniorious (ODT维护)

╰半橙微兮° 2021-09-29 14:20 156阅读 0赞

# 题意 #

给你一个长为 \\(n\\) 的序列 \\(a\_i\\) 需要支持四个操作。

*  \\(1~l~r~x:\\) 把 \\(i \\in \[l, r\]\\) 的 \\(a\_i\\) 加 \\(x\\) 。
 *  \\(2~l~r~x:\\) 把 \\(i \\in \[l, r\]\\) 的 \\(a\_i\\) 赋值成 \\(x\\) 。
 *  \\(3~l~r~x:\\) 求 \\(\[l, r\]\\) 区间的第 \\(x\\) 小元素。
 *  \\(4~l~r~x~y:\\) 求 \\((\\sum\_\{i = l\}^\{r\} \{a\_i\}^x) \\mod y\\) 。

一共会操作 \\(m\\) 次。

保证数据随机（给了你一个随机数据生成器）。

\\(1 \\le n, m \\le 10^5, 1 \\le a\_i \\le 10^9\\)

# 题解 #

对于这种 **数据随机** 并且有 **区间赋值** 的题，常常有一个很牛逼的乱搞算法，叫做 \\(\\mathrm\{ODT(Old~Driver~Tree)\}\\) ，也有叫 \\(\\mathrm\{Chtholly Tree\}\\) 的。

至于这个怎么做的呢？其实核心就一条，优化暴力。

如何优化呢？因为有赋值操作，考虑把相邻的数值一样的点合并成一个整的区间就行了。

至于如何实现呢？我们用 `std :: set<Node>` 维护一段段区间就行了。

`Node` 内容如下 `mutalbe` 是为了支持指针修改 ：

struct Node { int l, r; mutable ll val; } inline bool operator < (const Node &lhs, const Node &rhs) { return lhs.l < rhs.l; }

修改的时候，我们把 \\(\[l, r\]\\) 这段区间 \\(Split\\) 出来，也就是我们把 \\(l\\) 与 \\(l-1\\) 分开，\\(r\\) 与 \\(r + 1\\) 分开就行了。

具体实现如下：

void Split(int pos) { auto it = S.lower_bound((Node){pos, 0, 0}); if (it == S.end() || it -> l > pos) { -- it; S.emplace(it -> l, pos - 1, it -> val); S.emplace(pos, it -> r, it -> val); S.erase(it); } } // 将 pos 与 pos - 1 分开。

然后对于操作 \\(\[l, r\]\\) 区间，只需要暴力遍历指针就行了。（怎么暴力怎么来）

只有区间赋值那里需要搞搞操作，一次可以抹去一连续区间的迭代器。

也就是 `S.erase(itl, itr)` 会把 `[itl, itr)` 的所有元素全部删除，复杂度也挺优秀的。（比单个删除快）

然后这样操作后复杂度就变成 \\(O(m \\log n)\\) 的，十分的优秀。

# 总结 #

乱搞大法好啊！！\\(^o^)/~

# 代码 #

好写好调，真是一个优秀的暴力做法。

#include <bits/stdc++.h> #define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i) #define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i) #define Set(a, v) memset(a, v, sizeof(a)) #define Cpy(a, b) memcpy(a, b, sizeof(a)) #define debug(x) cout << #x << ": " << (x) << endl #define DEBUG(...) fprintf(stderr, __VA_ARGS__) #define fir first #define sec second #define mp make_pair #define pb push_back using namespace std; typedef long long ll; typedef pair<ll, int> PII; template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; } inline int read() { int x(0), sgn(1); char ch(getchar()); for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1; for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48); return x * sgn; } void File() { #ifdef zjp_shadow freopen ("C.in", "r", stdin); freopen ("C.out", "w", stdout); #endif } const int N = 1e5 + 1e3; int n, m, seed, v, a[N]; inline int rnd() { int res = seed; seed = (seed * 7ll + 13) % 1000000007; return res; } inline int Get(int lim) { return rnd() % lim + 1; } struct Node { int l, r; mutable ll val; Node(int l_ = 0, int r_ = 0, ll val_ = 0): l(l_), r(r_), val(val_) { } }; inline bool operator < (const Node &lhs, const Node &rhs) { return lhs.l < rhs.l; } multiset<Node> S; vector<PII> V; void Split(int pos) { auto it = S.lower_bound((Node){pos, 0, 0}); if (it == S.end() || it -> l > pos) { -- it; S.emplace(it -> l, pos - 1, it -> val); S.emplace(pos, it -> r, it -> val); S.erase(it); } } int Mod; inline int fpm(int x, int power) { int res = 1; for (; power; power >>= 1, x = 1ll * x * x % Mod) if (power & 1) res = 1ll * res * x % Mod; return res; } int main () { File(); n = read(); m = read(); seed = read(); v = read(); For (i, 1, n) a[i] = Get(v); for (int i = 1, j = 1; i <= n; i = j) { while (a[j] == a[i]) ++ j; S.emplace(i, j - 1, a[i]); } For (i, 1, m) { int opt = Get(4), l = Get(n), r = Get(n), x, y; if (l > r) swap(l, r); x = opt == 3 ? Get(r - l + 1) : Get(v); y = opt == 4 ? Get(v) : 0; Split(l); if (r < n) Split(r + 1); auto itl = S.lower_bound((Node) {l, 0, 0}), itr = S.upper_bound((Node) {r, 0, 0}); if (opt == 1) { for (auto it = itl; it != itr; ++ it) it -> val += x; } if (opt == 2) { S.erase(itl, itr); S.emplace(l, r, x); } if (opt == 3) { V.clear(); for (auto it = itl; it != itr; ++ it) V.pb(mp(it -> val, it -> r - it -> l + 1)); sort(V.begin(), V.end()); for (auto it : V) if (x <= it.sec) { printf ("%lld\n", it.fir); break; } else x -= it.sec; } if (opt == 4) { int ans = 0; Mod = y; for (auto it = itl; it != itr; ++ it) ans = (ans + 1ll * fpm(it -> val % Mod, x) * (it -> r - it -> l + 1)) % Mod; printf ("%d\n", ans); } } return 0; }

转载于:https://www.cnblogs.com/zjp-shadow/p/10022527.html