CF679E Bear and Bad Powers of 42 题解

CF679E Bear and Bad Powers of 42

题意

• 定义一个正整数是坏的，当且仅当它是 $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)$。

有区间赋值操作时，我们把这一整段的值记录在最右边的位置上，然后在别的位置上打个标记就好了。由于每次这样的操作最多只会产生两个新的值，因此时间复杂度没变。

代码

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;
}