「SP11470」TTM - To the moon

题目描述

给定一段长度为 \(N\) 的序列 \(a\) 以及 \(M\) 次操作，操作有以下几种：

C l r d ：将区间 \([l,r]\) 中的数都加上 \(d\)
Q l r ：查询当前时间戳区间 \([l,r]\) 中所有数的和
H l r t ：查询时间戳为 \(t\) 时，区间 \([l,r]\) 中所有数的和
B t ：将当前时间戳重置为 \(t\)

对于每一次询问操作，输出一行对应的答案。

时间戳初始值为 \(0\)

数据范围：

\(1\leq N,M\leq 10^5\)

然后要开 long long

基本思路

主席树的一道比较模板的题。。。

原谅我不想讲细节（其实代码里面写的还可以）

关于标记永久化的一些实现细节，我是参考的《信息学奥赛一本通 \(\cdot\) 提高篇》

细节注意事项

long long一定要开
细节不要写挂，数据结构题还是有点难调的
应该不会有人像我一样搞错输入顺序吧。。。

参考代码

/*--------------------------------

  Author: The Ace Bee

  Blog: www.cnblogs.com/zsbzsb

  This code is made by The Ace Bee

--------------------------------*/

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= (c == '-'), c = getchar();

	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

	s = f ? -s : s;

}

typedef long long LL;

const int _ = 100010;

int n, m, a[_];

int tot, rt[_], lc[_ << 5], rc[_ << 5];

LL sum[_ << 5], add[_ << 5];

inline void build(int& p, int l = 1, int r = n) {

	p = ++tot;

	if (l == r) return read(sum[p]);

	int mid = (l + r) >> 1;

	build(lc[p], l, mid), build(rc[p], mid + 1, r);

	sum[p] = sum[lc[p]] + sum[rc[p]];

}

inline void update(int& p, int q, int ql, int qr, int v, int l = 1, int r = n) {

	lc[p = ++tot] = lc[q], rc[p] = rc[q], add[p] = add[q], sum[p] = sum[q];

	if (ql <= l && r <= qr) { add[p] += v; return; }

	int mid = (l + r) >> 1;

	if (ql <= mid) update(lc[p], lc[q], ql, qr, v, l, mid);

	if (qr > mid) update(rc[p], rc[q], ql, qr, v, mid + 1, r);

	sum[p] += 1ll * v * (min(qr, r) - max(ql, l) + 1);

}

inline LL query(int p, int ql, int qr, int l = 1, int r = n) {

	if (ql <= l && r <= qr) return sum[p] + 1ll * add[p] * (r - l + 1);

	int mid = (l + r) >> 1; LL res = 0;

	if (ql <= mid) res += query(lc[p], ql, qr, l, mid);

	if (qr > mid) res += query(rc[p], ql, qr, mid + 1, r);

	return res + 1ll * add[p] * (min(qr, r) - max(ql, l) + 1);

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n), read(m), build(rt[0]);

	int tim = 0;

	for (rg int i = 1; i <= m; ++i) {

		char s[5]; scanf("%s", s);

		if (s[0] == 'B') read(tim), tot = rt[tim + 1] - 1;

		else if (s[0] == 'C') { int ql, qr, v;

			read(ql), read(qr), read(v), ++tim;

			update(rt[tim], rt[tim - 1], ql, qr, v);

		} else if (s[0] == 'Q') { int ql, qr;

			read(ql), read(qr);

			printf("%lld\n", query(rt[tim], ql, qr));

		} else if (s[0] == 'H') { int t, ql, qr;

			read(ql), read(qr), read(t);

			printf("%lld\n", query(rt[t], ql, qr));

		}

	}

	return 0;

}

巴特西

「SP11470」TTM - To the moon

题目描述

基本思路

细节注意事项

参考代码

最新文章

热门文章