UOJ228 基础数据结构练习题

Vexoben

Mar 16, 2019

It takes 8 minutes to read this article.

题目链接：UOJ228 基础数据结构练习题

（刷新以获取数学公式）

题意

给出一个长度为 $n$ 的数列 $A$ ，接下来有 $m$ 次操作，操作有三种：

对于所有的 $i∈[l,r]$ ，将 $A_i$ 变成 $A_i+x$ 。
对于所有的 $i∈[l,r]$ ，将 $A_i$ 变成 $\lfloor\sqrt{A_i}\rfloor$ 。
对于所有的 $i∈[l,r]$ ，询问 $A_i$ 的和。

数据范围： $n,m,A_i,x≤100000$

题解

用线段树做。

不考虑区间加，那么每个数最多做 $log$ 次 $sqrt$ 就会变为 $1$ ，于是只要判断当前区间有没有大于 $1$ 的数，有就向下递归计算即可。

考虑区间加。一个直观的想法是，如果一些数在 $sqrt$ 之后得到的是相同的数，这个区间内就相当于区间赋值；否则递归下去计算。不幸的是，这样的复杂度并不正确。 $[8,9,8,9,8,9]$ 可以和 $[2,3,2,3,2,3]$ 之间互相转化，每次都将复杂度卡满。

可以换一个思路。如果一个区间内， $sqrt$ 后最大数的变化量和最小数的变化量相等，就转化为区间减法，否则就向下递归。这样一个数会被递归到，要么是源自初始序列要 $log$ 次降为 $1$ ，要么是源自这个位置位于某一次加法操作的端点上。也就是：向下递归相当于回收加法产生的差分数组的两个标记。这样总复杂度就是 $O(nlogn)$ （此处认为 $n$ , $m$ 同阶）

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 10;

int n, m;
int a[N];
LL tr[N << 2], mx[N << 2], mi[N << 2], tag[N << 2];

void read(int &x) {
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + c - '0';
}

void Pushup(int x) {
	tr[x] = tr[x << 1] + tr[x << 1 | 1];
	mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	mi[x] = min(mi[x << 1], mi[x << 1 | 1]);
}

void Build(int x, int l, int r) {
	if (l == r) {
		tr[x] =  mi[x] = mx[x] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	Build(x << 1, l, mid);
	Build(x << 1 | 1, mid + 1, r);
	Pushup(x);
}

void Pushdown(int x, int l, int r) {
	if (tag[x]) {
		int mid = (l + r) >> 1;
		tr[x << 1] += 1LL * (mid - l + 1) * tag[x];
		mi[x << 1] += tag[x];
		mx[x << 1] += tag[x];
		tag[x << 1] += tag[x];
		tr[x << 1 | 1] += 1LL * (r - mid) * tag[x];
		mi[x << 1 | 1] += tag[x];
		mx[x << 1 | 1] += tag[x];
		tag[x << 1 | 1] += tag[x];
		tag[x] = 0;
	}
}

void Update1(int x, int l, int r, int ql, int qr, int del) {
	if (ql <= l && r <= qr) {
		tr[x] += 1LL * (r - l + 1) * del;
		mx[x] += del;
		mi[x] += del;
		tag[x] += del;
		return;
	}
	int mid = (l + r) >> 1;
	Pushdown(x, l, r);
	if (mid >= ql) Update1(x << 1, l, mid, ql, qr, del);
	if (mid < qr) Update1(x << 1 | 1, mid + 1, r, ql, qr, del);
	Pushup(x);
}

void Update2(int x, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
		LL u = sqrt(mx[x]), v = sqrt(mi[x]);
		if (mx[x] - u == mi[x] - v) {
			LL del = mx[x] - u;
			tag[x] -= del;
			mx[x] -= del;
			mi[x] -= del;
			tr[x] -= 1LL * del * (r - l + 1);
			return;
		}
	}
	Pushdown(x, l, r);
	int mid = (l + r) >> 1;
	if (mid >= ql) Update2(x << 1, l, mid, ql, qr);
	if (mid < qr) Update2(x << 1 | 1, mid + 1, r, ql, qr);
	Pushup(x);
}

LL Query(int x, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return tr[x];
	Pushdown(x, l, r);
	int mid = (l + r) >> 1;
	LL ans = 0;
	if (mid >= ql) ans += Query(x << 1, l, mid, ql, qr);
	if (mid < qr) ans += Query(x << 1 | 1, mid + 1, r, ql, qr);
	return ans;
}

int main() {
	read(n); read(m);
	for (int i = 1; i <= n; ++i) {
		read(a[i]);
	}
	Build(1, 1, n);
	while (m--) {
		int opt, l, r, x;
		read(opt); read(l); read(r);
		if (opt == 1) {
			read(x);
			Update1(1, 1, n, l, r, x);
		}
		if (opt == 2) {
			Update2(1, 1, n, l, r);
		}
		if (opt == 3) {
			printf("%lld\n", Query(1, 1, n, l, r));
		}
	}
	return 0;
}