自动搬运

查看原文

来自洛谷，原作者为

	EricWan 一只菜鸡。

搬运于2025-08-24 22:47:19，当前版本为作者最后更新于2025-03-12 22:11:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目中要求区间赋值，不难想到 ODT，单点查询，因此复杂度合理。

不会 ODT 的出门右转 ，或者发明 ODT

其他的操作无脑维护即可，我们需要思考 e 操作。

在同一个点的人可能有不止一段，如果暴力更新每一段，肯定就爆了。

我们可以吧每一个城的总活动奖金记录下来见，代码中的 event，一个人在一个城中住的那一段时间的活动奖金就是离开时的活动奖金减来到城的时候的奖金。这就是这题的其中一个 trick。

因此可以这样维护：一个人从 A 城移到 B 城的时候让他加上 A 城当时的活动奖金，然后减去 B 城当时的奖金。输出的时候自然是输出目前这个人里面存的奖金加上这个人所在的城的奖金。可以发现，这样可以很方便的维护每一个人的奖金。

当然此题也可以使用其他数据结构维护（？），例如线段树（？），但是代码量可能更长。ODT 我写了的非其它板子部分只有 2.5kb。

#include <bits/stdc++.h>
using namespace std;
namespace MATH {
	#define math_int long long
	int log2_(math_int k) {
		int l = 0, r = 62;
		while (l < r) {
			if ((1ll << ((l + r + 1) >> 1)) > k) {
				r = ((l + r + 1) >> 1) - 1;
			} else {
				l = ((l + r + 1) >> 1);
			}
		}
		return l;
	}
	#undef math_int
}
namespace graph_algorithm {
	#define graph_index signed
	template<typename T>
	void read_graph_u_u(vector<T> *e, graph_index m) {
		T u, v;
		while (m--) {
			cin >> u >> v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
	}
	#undef graph_index
}
namespace data_structure {
	#define ds_index size_t
	#define lowbit(x) ((x)&-(x))
	namespace BIT {
		template<typename T>
		struct BIT {
			vector<T> t;
			BIT(ds_index n) {
				t = vector<T>(n, 0);
			}
			void update(ds_index x, const T k) {
				if (x == 0) {
					t[0] += k;
				}
				while (x != 0 && x < t.size()) {
					t[x] += k;
					x += lowbit(x);
				}
			}
			T query(ds_index x) {
				T ans = t[0];
				while (x) {
					ans += t[x];
					x ^= lowbit(x);
				}
				return ans;
			}
		};
	}
	namespace ST {
		template<typename T, size_t Row, size_t Col>
		T query(T (&st)[Row][Col], ds_index l, ds_index r, bool (*cmp)(T, T)) {
			if (l > r) swap(l, r);
			ds_index k = MATH::log2_(r - l + 1);
			if (cmp(st[l][k], st[r - (1 << k) + 1][k])) {
				return st[l][k];
			} else {
				return st[r - (1 << k) + 1][k];
			}
		}
		template<typename T, size_t Row, size_t Col>
		void build_ST(T (&st)[Row][Col], ds_index n, bool (*cmp)(T, T)) {
			for (ds_index i = 1; ((ds_index)1 << i) <= n; i++) {
				for (ds_index j = 1; j + (1 << i) - 1 <= n; j++) {
					if (cmp(st[j][i - 1], st[j + (1 << (i - 1))][i - 1])) {
						st[j][i] = st[j][i - 1];
					} else {
						st[j][i] = st[j + (1 << (i - 1))][i - 1];
					}
				}
			}
		}
	}
	#undef ds_index
	#undef lowbit
}
#define int long long
#define MAXN 1000005
int n, m, q, fa[MAXN], fir[MAXN], dfn[MAXN], st[MAXN][20], dep[MAXN], event[MAXN], pos[MAXN], jiangly, newpos, l, r, value;
char op;
vector<int> e[MAXN];
data_structure::BIT::BIT<int> bit(MAXN);
set<pair<pair<int, int>, int> > odt;
bool cmp(int x, int y)
{
	return dep[x] < dep[y];
}
struct edge {
	int u, v, time;
} E[MAXN];
bool cmp_time(edge x, edge y) {
    return x.time < y.time;
}
int query(int x, int y) {
	int a = data_structure::ST::query(st, fir[x], fir[y], cmp);
	return dep[x] + dep[y] - 2 * dep[a];
}
void dfs(int id, int D) {
	dep[id] = D;
	fir[id] = ++dfn[0];
	dfn[dfn[0]] = id;
	for (int i : e[id]) {
		if (!fir[i]) {
			dfs(i, D + 1);
            dfn[++dfn[0]] = id;
		}
	}
}
signed main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		cin >> pos[i];
		odt.insert({{i, i}, pos[i]});
	}
	graph_algorithm::read_graph_u_u(e, n - 1);
	dfs(1, 1);
	for (int i = 1; i <= dfn[0]; i++) {
		st[i][0] = dfn[i];
	}
	data_structure::ST::build_ST(st, dfn[0], cmp);
	while (q--) {
		cin >> op;
		if (op == 't') {
			cin >> l >> r >> newpos;
			auto lit = --odt.upper_bound({{l, 10000000}, 10000000}), rit = --odt.upper_bound({{r, 10000000}, 10000000});
			int ll = lit->first.first, lr = lit->first.second, lp = lit->second;
			int rl = rit->first.first, rr = rit->first.second, rp = rit->second;
			if (lit == rit) {
				int dis = query(lp, newpos);
				bit.update(l, - dis + event[lp] - event[newpos]);
				bit.update(r + 1, dis - event[lp] + event[newpos]);
				odt.erase(lit);
				if (ll < l)
					odt.insert({{ll, l - 1}, lp});
				if (rr > r)
					odt.insert({{r + 1, rr}, rp});
			} else {
				odt.erase(lit);
				odt.erase(rit);
				lit = odt.insert({{l, lr}, lp}).first;
				if (ll < l) odt.insert({{ll, l - 1}, lp});
				rit = odt.insert({{rl, r}, rp}).first;
				if (rr > r) odt.insert({{r + 1, rr}, rp});
				auto seg_end = rit;
				seg_end++;
				vector<pair<pair<int, int>, int> > need_del;
				for (auto i = lit; i != seg_end; i++) {
					need_del.push_back(*i);
					int dis = query(i->second, newpos);
					bit.update(i->first.first, - dis + event[i->second] - event[newpos]);
					bit.update(i->first.second + 1, dis - event[i->second] + event[newpos]);
				}
				for (pair<pair<int, int>, int> i : need_del) {
					odt.erase(i);
				}
			}
			odt.insert({{l, r}, newpos});
		} if (op == 'e') {
			cin >> newpos >> value;
			event[newpos] += value;
		}
		if (op == 'q') {
			cin >> jiangly;
			cout << bit.query(jiangly) + event[(--odt.upper_bound({{jiangly, 10000000}, 10000000}))->second] << endl;
		}
	}
	return 0;
}