势能分析 线段树 学习记录

算法讲解111【扩展】线段树专题2-线段树的离散化、二分搜索、特别修改_哔哩哔哩_bilibili

对于gcd, 取log, 开根号, 取模, 等操作, 一个数的下降比较快, 可以考虑暴力操作势能分析

P4145 上帝造题的七分钟 2 / 花神游历各国 - 洛谷

对于每个数, 最多操作六次开根号操作就会降到1, 线段树修改操作 直接修改到叶子节点, 但是如果当前区间的最大值是1, 则这个区间不再需要进行操作, 不进入这个区间, 这样的话, 每个数最多操作6次, 加上树高, 一共是6 * logn * n次

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

//线段树，区间修改，区间查询
//https://www.luogu.com.cn/problem/P3372
template<typename Info, typename Tag>
struct SegmentTree {
#define ls (id<<1)
#define rs (id<<1|1)
	SegmentTree() = default;
	SegmentTree(int n) : n(n), info(n << 2), tag(n << 2), len(n << 2) {}
	SegmentTree(const SegmentTree<Info, Tag> &o) : n(o.n), info(o.info), tag(o.tag) {}
	template<typename T>
	SegmentTree(const std::vector<T> &init) : SegmentTree((int)init.size()) {
		auto build = [&](auto self, int id, int l, int r) ->void {
			len[id] = r - l + 1;
			if(l == r) {
				info[id] = init[l];
				return;
			}
			int mid = (l + r) / 2;
			self(self, ls, l, mid);
			self(self, rs, mid + 1, r);
			pushup(id);
		};
		build(build, 1, 0, n - 1);
	}
	void apply(int id, const Tag &dx) {
		info[id].apply(dx, len[id]);
		tag[id].apply(dx);
	}
	void pushup(int id) {
		info[id] = info[ls] + info[rs];
	}
	void pushdown(int id) {
		apply(ls, tag[id]);
		apply(rs, tag[id]);
		tag[id] = Tag();
	}
	
	void modify(int id, int l, int r, int pos, const Info &val) {
		if(l == r) {
			info[id] = val;
			return;
		}
		pushdown(id);
		int mid = (l + r) / 2;
		if(pos <= mid) {
			modify(ls, l, mid, pos, val);
		} else {
			modify(rs, mid + 1, r, pos, val);
		}
		pushup(id);
	}
	
	void rangeUpdate(int id, int l, int r, int x, int y, const Tag &dx) {
		if (info[id].maxx == 1) {
			return;
		}
		if(l == r) {
			info[id].sum = sqrt(info[id].sum);
			info[id].maxx = sqrt(info[id].maxx);
			return;
		}
		int mid = (l + r) / 2;
		pushdown(id);
		if(x <= mid) {
			rangeUpdate(ls, l, mid, x, y, dx);
		}
		if(y > mid) {
			rangeUpdate(rs, mid + 1, r, x, y, dx);
		}
		pushup(id);
	}
	Info rangeQuery(int id, int l, int r, int x, int y) {
		if(x <= l && r <= y) {
			return info[id];
		}
		int mid = (l + r) / 2;
		pushdown(id);
		Info res;
		if(x <= mid) {
			res = res + rangeQuery(ls, l, mid, x, y);
		}
		if(y > mid) {
			res = res + rangeQuery(rs, mid + 1, r, x, y);
		}
		return res;
	}


	void rangeUpdate(int l, int r, const Tag &dx) {
		rangeUpdate(1, 0, n - 1, l, r, dx);
	}
	void update(int pos, const Tag &dx) {
		rangeUpdate(pos, pos, dx);
	}
	Info rangeQuery(int l, int r) {
		return rangeQuery(1, 0, n - 1, l, r);
	}
	Info query(int pos) {
		return rangeQuery(pos, pos);
	}

	void modify(int pos, const Info &val) {
		return modify(1, 0, n - 1, pos, val);
	}
#undef ls
#undef rs
	int n;
	std::vector<Info> info;
	std::vector<Tag> tag;
	std::vector<int> len;
};

constexpr i64 INF = 4E18;
i64 mod = 1e9 + 7;
struct Tag {
	i64 add = 0;
	i64 mul = 1;
	void apply(const Tag &dx) {
		// mul = (mul * dx.mul) % mod;
		// add = (add * dx.mul + dx.add) % mod;
	}
};

struct Info {
	i64 sum = 0;
	i64 maxx = 0;
	Info() {}
	Info(i64 x) : sum(x), maxx(x) {};
	void apply(const Tag &dx, const int &len) {
		// sum = (sum * dx.mul + dx.add * len) % mod;

	}
};

Info operator+(const Info &x, const Info &y) {
	Info res;
	res.sum = (x.sum + y.sum);
	res.maxx = max(x.maxx, y.maxx);
	return res;
}
void solve() {
	int n;
	cin >> n;
	vector<i64> a(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	SegmentTree<Info, Tag> seg(a);
	
	int m;
	cin >> m;
	while(m--) {
		int k, l, r;
		cin >> k >> l >> r;
		if (r < l) swap(l, r);

		if (k == 0) {
			Tag tag;
			seg.rangeUpdate(l, r, tag);
		} else {
			cout << seg.rangeQuery(l, r).sum << '\n';
		}
	}





}


int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	int T = 1;
	//cin >> T;
	while (T--) solve();

	return 0;
}

Problem - D - Codeforces

每次取模操作, 如果mod小于x, 则x取模之后最少减半, 所以一个数最多进行log次取模操作

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
//线段树，区间修改，区间查询
//https://www.luogu.com.cn/problem/P3372
template<typename Info, typename Tag>
struct SegmentTree {
#define ls (id<<1)
#define rs (id<<1|1)
	SegmentTree() = default;
	SegmentTree(int n) : n(n), info(n << 2), tag(n << 2), len(n << 2) {}
	SegmentTree(const SegmentTree<Info, Tag> &o) : n(o.n), info(o.info), tag(o.tag) {}
	template<typename T>
	SegmentTree(const std::vector<T> &init) : SegmentTree((int)init.size()) {
		auto build = [&](auto self, int id, int l, int r) ->void {
			len[id] = r - l + 1;
			if(l == r) {
				info[id] = init[l];
				return;
			}
			int mid = (l + r) / 2;
			self(self, ls, l, mid);
			self(self, rs, mid + 1, r);
			pushup(id);
		};
		build(build, 1, 0, n - 1);
	}
	void apply(int id, const Tag &dx) {
		info[id].apply(dx, len[id]);
		tag[id].apply(dx);
	}
	void pushup(int id) {
		info[id] = info[ls] + info[rs];
	}
	void pushdown(int id) {
		apply(ls, tag[id]);
		apply(rs, tag[id]);
		tag[id] = Tag();
	}
	
	void modify(int id, int l, int r, int pos, const Info &val) {
		if(l == r) {
			info[id] = val;
			return;
		}
		pushdown(id);
		int mid = (l + r) / 2;
		if(pos <= mid) {
			modify(ls, l, mid, pos, val);
		} else {
			modify(rs, mid + 1, r, pos, val);
		}
		pushup(id);
	}
	
	void rangeUpdate(int id, int l, int r, int x, int y, const Tag &dx) {
		if (info[id].maxx < dx.mod) {
			return;
		}
		if (l == r) {
			info[id].maxx %= dx.mod;
			info[id].sum %= dx.mod;
			return;
		}
		
		int mid = (l + r) / 2;
		pushdown(id);
		if(x <= mid) {
			rangeUpdate(ls, l, mid, x, y, dx);
		}
		if(y > mid) {
			rangeUpdate(rs, mid + 1, r, x, y, dx);
		}
		pushup(id);
	}
	Info rangeQuery(int id, int l, int r, int x, int y) {
		if(x <= l && r <= y) {
			return info[id];
		}
		int mid = (l + r) / 2;
		pushdown(id);
		Info res;
		if(x <= mid) {
			res = res + rangeQuery(ls, l, mid, x, y);
		}
		if(y > mid) {
			res = res + rangeQuery(rs, mid + 1, r, x, y);
		}
		return res;
	}


	void rangeUpdate(int l, int r, const Tag &dx) {
		rangeUpdate(1, 0, n - 1, l, r, dx);
	}
	void update(int pos, const Tag &dx) {
		rangeUpdate(pos, pos, dx);
	}
	Info rangeQuery(int l, int r) {
		return rangeQuery(1, 0, n - 1, l, r);
	}
	Info query(int pos) {
		return rangeQuery(pos, pos);
	}

	void modify(int pos, const Info &val) {
		return modify(1, 0, n - 1, pos, val);
	}
#undef ls
#undef rs
	int n;
	std::vector<Info> info;
	std::vector<Tag> tag;
	std::vector<int> len;
};

constexpr i64 INF = 4E18;
i64 mod = 1e9 + 7;
struct Tag {
	i64 mod = 0;
	void apply(const Tag &dx) {
		// mul = (mul * dx.mul) % mod;
		// add = (add * dx.mul + dx.add) % mod;
	}
};

struct Info {
	i64 sum = 0;
	i64 maxx = 0;
	Info() {}
	Info(i64 x) : sum(x), maxx(x) {};
	void apply(const Tag &dx, const int &len) {
		// sum = (sum * dx.mul + dx.add * len) % mod;
	}
};

Info operator+(const Info &x, const Info &y) {
	Info res;
	res.sum = (x.sum + y.sum);
	res.maxx = max(x.maxx, y.maxx);
	return res;
}

void solve() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	SegmentTree<Info, Tag> seg(a);
	while(m--) {
		int k;
		cin >> k;
		if (k == 1) {
			int l, r;
			cin >> l >> r;
			cout << seg.rangeQuery(l, r).sum << '\n';
		} else if (k == 2) {
			int l, r, mod;
			cin >> l >> r >> mod;
			Tag tag;
			tag.mod = mod;
			seg.rangeUpdate(l, r, tag);
		} else {
			int i, x;
			cin >> i >> x;
			Info info;
			info = x;
			seg.modify(i, info);
		}
	}






}


int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	int T = 1;
	//cin >> T;
	while (T--) solve();

	return 0;
}