自动搬运

查看原文

来自洛谷，原作者为

	Ryo_Yamada **

搬运于2025-08-24 22:28:52，当前版本为作者最后更新于2021-06-05 15:51:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

区间操作首先想到线段树。

• 区间开方下取整

和 GSS4 一样，可以用相同的方法，记录区间最大值，如果这个最大值 $>1$ 才进入区间修改。$10^9$ 做五次开方操作就会变成 $1$，所以复杂度是有保证的。

• 区间平方

显然，区间平方的和 与 区间和的平方不是一个东西，无法直接修改，要考虑别的做法。平方和开方是相反的操作，平方再开方后原数是不变的，考虑对每个点记录一个 $\text{cnt}_i$ 表示当前这个数 $\text{val}_i$ 被平方了多少次。对于每次开方操作，将 $\text{cnt}_i$ 区间 $+1$。开方时，若 $\text{cnt}_i$ 不为 $0$ 则 $\text{cnt}_i = \text{cnt}_i-1$，否则将原数开方。因为 $1$ 平方和开方后都是 $1$，所以这种做法区间最大值在 $>1$ 上的正确性是有保证的。

但是这样还不足以通过。通过一次平方一次开方的操作可以将这种做法卡到 $O(nm)$。再维护区间 $\text{cnt}_i$ 的最小值，修改时，若这个最小值 $\geq 1$，则直接区间将 $\text{cnt}_i = \text{cnt}_i - 1$。否则进入左右区间修改。

$\text{Code}$：

#define ls id << 1
#define rs id << 1 | 1
#define Mid int mid = (l + r) >> 1

def(nn, int, 2e5 + 5)
def(N, int, 8e5 + 5)
def(p, int, 998244353)

int n, q;
int a[nn];
ll val[N], cnt[N], lz[N], mx[N], mnc[N];

void pushup(int id) {
	mx[id] = max(mx[ls], mx[rs]);
	mnc[id] = min(mnc[ls], mnc[rs]);
}

void pushdown(int id) {
	if(lz[id]) {
		cnt[ls] += lz[id];
		cnt[rs] += lz[id];
		mnc[ls] += lz[id];
		mnc[rs] += lz[id];
		lz[ls] += lz[id];
		lz[rs] += lz[id];
		lz[id] = 0;
	}
}

void build(int id, int l, int r) {
	if(l == r) {
		val[id] = mx[id] = a[l];
		return ;
	}
	Mid;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	pushup(id);
}

void update(int id, int l, int r, int x, int y) {
	if(x <= l && r <= y && mnc[id] >= 1) {
		--cnt[id], --mnc[id], --lz[id];
		return ;
	}
	if(l == r) {
		if(cnt[id]) --cnt[id], --mnc[id];
		else mx[id] = val[id] = sqrt(val[id]);
		return ;
	}
	pushdown(id);
	Mid;
	if(mx[ls] > 1 && mid >= x) update(ls, l, mid, x, y);
	if(mx[rs] > 1 && mid < y) update(rs, mid + 1, r, x, y);
	pushup(id);
}

void modify(int id, int l, int r, int x, int y) {
	if(x <= l && r <= y) {
		++cnt[id], ++mnc[id], ++lz[id];
		return ;
	}
	pushdown(id);
	Mid;
	if(mid >= x) modify(ls, l, mid, x, y);
	if(mid < y) modify(rs, mid + 1, r, x, y);
	pushup(id);
}

ll query(int id, int l, int r, int x) {
	if(l == r) {
		int pf = qpow(cnt[id], 2, p - 1);
		return qpow(pf, val[id], p);
	}
	pushdown(id);
	Mid;
	if(mid >= x) return query(ls, l, mid, x);
	else return query(rs, mid + 1, r, x);
}

int main() {
	qread(n, q);
	rep(i, 1, n) qread(a[i]);
	build(1, 1, n);
	W(q) {
		int op, l, r;
		qread(op, l, r);
		if(op == 1) {
			update(1, 1, n, l, r);
//			rep(i, l, r) {
//				ll x = query(1, 1, n, i);
//				cout << x << endl;
//			}
		}
		else modify(1, 1, n, l, r);
	}
	ll ans = 0;
	rep(i, 1, n) {
		ll x = query(1, 1, n, i);
		//cout << x << endl;
		(ans += x) %= p;
	}
	printf("%lld\n", ans);
 	return 0;
}