题解 CF679E 【Bear and Bad Powers of 42】

xht

2020-02-26 15:27:47

Solution

> [CF679E Bear and Bad Powers of 42](https://codeforces.com/contest/679/problem/E) ## 题意 - 定义一个正整数是坏的,当且仅当它是 $42$ 的次幂,否则它是好的。 - 给定一个长度为 $n$ 的序列 $a_i$,保证初始时所有数都是好的。 - 有 $q$ 次操作,每次操作有三种可能: - `1 i` 查询 $a_i$。 - `2 l r x` 将 $a_{l\dots r}$ 赋值为一个好的数 $x$。 - `3 l r x` 将 $a_{l \dots r}$ 都加上 $x$,重复这一过程直到所有数都变好。 - $n,q \le 10^5$,$a_i,x \le 10^9$。 ## 题解 设 $n,q$ 同阶。 这个奇奇怪怪的 $42$ 一点性质都没有,但是这个**次幂**的提示性就很明显,一定范围内**次幂**这破玩意儿的个数再怎么多也只有 $\mathcal O(\log)$ 个。 因此对于一个数,它最多被额外加 $\mathcal O(\log_{42} w)$ 次。在没有操作 2 的情况下,用线段树维护每个数到 $42$ 的次幂的差值即可,时间复杂度为 $\mathcal O(n \log n \log_{42} w)$。 有区间赋值操作时,我们把这一整段的值记录在最右边的位置上,然后在别的位置上打个标记就好了。由于每次这样的操作最多只会产生两个新的值,因此时间复杂度没变。 ## 代码 ```cpp const int N = 1e5 + 7; const ll inf = 1e18; int n, q; ll p[12] = {1}, a[N]; set<int> s; struct T { int l, r, o; ll z; pair<ll, int> x; } t[N<<2]; inline int f(ll x) { return lower_bound(p, p + 12, x) - p; } inline void upd(int p) { t[p].x = min(t[ls].x, t[rs].x); } inline void build(int p, int l, int r) { t[p].l = l, t[p].r = r; if (l == r) return t[p].x = mp(::p[t[p].o=f(a[l])] - a[l], l), void(); build(ls, l, md), build(rs, md + 1, r), upd(p); } inline void spd(int p) { t[ls].z = max(-inf, t[ls].z + t[p].z); t[rs].z = max(-inf, t[rs].z + t[p].z); t[ls].x.fi = min(inf, t[ls].x.fi - t[p].z); t[rs].x.fi = min(inf, t[rs].x.fi - t[p].z); t[p].z = 0; } inline ll ask(int p, int x) { if (t[p].l == t[p].r) return ::p[t[p].o] - t[p].x.fi; spd(p); return ask(x <= md ? ls : rs, x); } inline void setx(int p, int o, ll x) { if (t[p].l == t[p].r) return t[p].x = mp(::p[t[p].o=f(x)] - x, t[p].l), void(); spd(p); setx(o <= md ? ls : rs, o, x); upd(p); } inline void add(int p, int l, int r, ll x) { if (t[p].l >= l && t[p].r <= r) return t[p].z += x, t[p].x.fi -= x, void(); spd(p); if (l <= md) add(ls, l, r, x); if (r > md) add(rs, l, r, x); upd(p); } inline void work2(int l, int r, ll x) { if (l != 1) setx(1, l - 1, ask(1, *s.lower_bound(l - 1))), s.insert(l - 1); s.erase(s.lower_bound(l), s.upper_bound(r)); setx(1, r, x), s.insert(r); if (l < r) add(1, l, r - 1, -inf); } inline void upd(int p, int x) { if (t[p].l == t[p].r) { ll k = ::p[t[p].o] - t[p].x.fi; t[p].x = mp(::p[t[p].o=f(k)] - k, t[p].l); return; } spd(p); upd(x <= md ? ls : rs, x); upd(p); } inline void work3(int l, int r, ll x) { if (l != 1) setx(1, l - 1, ask(1, *s.lower_bound(l - 1))), s.insert(l - 1); setx(1, r, ask(1, *s.lower_bound(r))), s.insert(r); do { add(1, l, r, x); while (t[1].x.fi < 0) upd(1, t[1].x.se); } while (!t[1].x.fi); } int main() { for (int i = 1; i < 12; i++) p[i] = p[i-1] * 42; rd(n), rd(q), rda(a, n); for (int i = 1; i <= n; i++) s.insert(i); build(1, 1, n); for (int i = 1, o, x, l, r; i <= q; i++) { rd(o); switch (o) { case 1 : rd(x), print(ask(1, *s.lower_bound(x))); break; case 2 : rd(l), rd(r), rd(x), work2(l, r, x); break; case 3 : rd(l), rd(r), rd(x), work3(l, r, x); break; } } return 0; } ```