homework_detail - 蒙青创OJ

/*
l~mid  mid+1~r
Max
Min
val
c.Max = max(a.Max,b.Max)
c,Min = min(a.Min,b.Min)
c.lMx = max(a.lMx,b.lMx,b.Max-a.Min)
c.rMx = max(a.rMx,b.rMx,a.Max-b.Min);
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;

struct node {
	int Max, Min, lm, rm;
	friend node operator + (node a, node b) {
		node c = {-1, -1, -1, -1};
		if (a.Max == -1)
			return b;
		else if (b.Max == -1)
			return a;
		else {
			node c;
			c.Max = max(a.Max, b.Max);
			c.Min = min(a.Min, b.Min);
			c.lm = max(max(a.lm, b.lm), b.Max - a.Min);
			c.rm = max(max(a.rm, b.rm), a.Max - b.Min);
			return c;
		}
	}
} tree[N << 2];
int tag[N << 2];
int n, m, a[N], w[N];
int son[N], siz[N], fa[N], dep[N];
int top[N], id[N], cnt;
vector<int>e[N];

void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void pushdown(int l, int r, int rt) {
	if (tag[rt]) {
		tag[rt << 1] += tag[rt];
		tag[rt << 1 | 1] += tag[rt];
		tree[rt << 1].Max += tag[rt];
		tree[rt << 1].Min += tag[rt];
		tree[rt << 1 | 1].Max += tag[rt];
		tree[rt << 1 | 1].Min += tag[rt];
		tag[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = {w[l], w[l], 0, 0};
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int L, int R, int c) {
	if (L <= l && r <= R) {
		tag[rt] += c;
		tree[rt].Max += c;
		tree[rt].Min += c;
		return;
	}
	pushdown(l, r, rt);
	int mid = (l + r) >> 1;
	if (L <= mid)
		update(l, mid, rt << 1, L, R, c);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R, c);
	pushup(rt);
}

node query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	pushdown(l, r, rt);
	node res = {-1, -1, -1, -1};
	int mid = (l + r) >> 1;
	if (L <= mid)
		res = res + query(l, mid, rt << 1, L, R);
	if (R > mid)
		res = res + query(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

void dfs1(int x, int f, int deep) {
	dep[x] = deep;
	fa[x] = f;
	int maxx = 0;
	siz[x] = 1;
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs1(v, x, deep + 1);
		siz[x] += siz[v];
		if (siz[v] > maxx) {
			maxx = siz[v];
			son[x] = v;
		}
	}
}

void dfs2(int x, int topfa) {
	id[x] = ++cnt;
	top[x] = topfa;
	w[cnt] = a[x];
	if (!son[x])
		return;
	dfs2(son[x], topfa);
	for (auto v : e[x]) {
		if (v == son[x] || v == fa[x])
			continue;
		dfs2(v, v);
	}
}

void Q1(int x, int y, int z) {
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]])
			swap(x, y);
		update(1, n, 1, id[top[y]], id[y], z);
		y = fa[top[y]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	update(1, n, 1, id[x], id[y], z);
}

node Q2(int x, int y) {
	node ansx = {-1, -1, -1, -1}, ansy = {-1, -1, -1, -1};
	while (top[x] != top[y]) {
		//	cout << x << " " << y << endl;
		if (dep[top[x]] > dep[top[y]]) {
			node tmp = query(1, n, 1, id[top[x]], id[x]);
			swap(tmp.lm, tmp.rm);
			ansx = ansx + tmp;
			x = fa[top[x]];
		} else {
			node tmp = query(1, n, 1, id[top[y]], id[y]);
			ansy = tmp + ansy;
			y = fa[top[y]];
		}
		//	cout << x << " " << y << endl;
	}
	if (dep[x] > dep[y]) {

		node tmp = query(1, n, 1, id[y], id[x]);
		swap(tmp.lm, tmp.rm);
		ansx = ansx + tmp;
	} else {
		//	cout << x << " " << id[x] << " " << y << " " << id[y] << endl;
		node tmp = query(1, n, 1, id[x], id[y]);
		ansx = ansx + tmp;
	}
	return ansx + ansy;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1, 0, 1);
	dfs2(1, 1);
	build(1, n, 1);
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		cout << Q2(x, y).lm << endl;
		Q1(x, y, z);
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;

struct node {
	int lc, rc, val;
	friend node operator + (node a, node b) {
		node c = {-1, -1, -1};
		if (a.lc == -1)
			return b;
		if (b.lc == -1)
			return a;
		c.lc = a.lc;
		c.rc = b.rc;
		c.val = a.val + b.val;
		if (a.rc == b.lc)
			c.val--;
		return c;
	}
} tree[N << 2];
int tag[N << 2], a[N], dep[N], son[N], fa[N], siz[N];
int top[N], id[N], w[N], cnt;
vector<int>e[N];

void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void pushdown(int rt) {
	if (tag[rt]) {
		tag[rt << 1] = tag[rt];
		tag[rt << 1 | 1] = tag[rt];
		tree[rt << 1] = {tag[rt], tag[rt], 1};
		tree[rt << 1 | 1] = {tag[rt], tag[rt], 1};
		tag[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = {w[l], w[l], 1};
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int L, int R, int c) {
	if (L <= l && r <= R) {
		tree[rt] = {c, c, 1};
		tag[rt] = c;
		return;
	}
	pushdown(rt);
	int mid = (l + r) >> 1;
	if (L <= mid)
		update(l, mid, rt << 1, L, R, c);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R, c);
	pushup(rt);
}

node query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	pushdown(rt);
	node res = {-1, -1, -1};
	int mid = (l + r) >> 1;
	if (L <= mid)
		res = res + query(l, mid, rt << 1, L, R);
	if (R > mid)
		res = res + query(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

void dfs1(int x, int f, int deep) {
	dep[x] = deep;
	fa[x] = f;
	int maxx = 0;
	siz[x] = 1;
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs1(v, x, deep + 1);
		siz[x] += siz[v];
		if (siz[v] > maxx) {
			maxx = siz[v];
			son[x] = v;
		}
	}
}

void dfs2(int x, int topfa) {
	top[x] = topfa;
	id[x] = ++cnt;
	w[cnt] = a[x];
	if (!son[x])
		return;
	dfs2(son[x], topfa);
	for (auto v : e[x]) {
		if (v == fa[x] || v == son[x])
			continue;
		dfs2(v, v);
	}
}

void pos1(int x, int y, int z) {
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]])
			swap(x, y);
		update(1, n, 1, id[top[y]], id[y], z);
		y = fa[top[y]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	update(1, n, 1, id[x], id[y], z);
}

node pos2(int x, int y) {
	node ansx = {-1, -1, -1}, ansy = {-1, -1, -1};
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]]) {
			swap(x, y);
			swap(ansx, ansy);
		}
		ansy = query(1, n, 1, id[top[y]], id[y]) + ansy;
		y = fa[top[y]];
	}
	if (dep[x] > dep[y])
		swap(x, y), swap(ansx, ansy);
	ansy = query(1, n, 1, id[x], id[y]) + ansy;
	swap(ansy.lc, ansy.rc);
	node res;
	res = ansy + ansx;
	return res;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1, 0, 1);
	dfs2(1, 1);
	build(1, n, 1);
	while (m--) {
		char pos;
		int x, y, z;
		cin >> pos >> x >> y;
		if (pos == 'C') {
			cin >> z;
			pos1(x, y, z);
		} else {
			cout << pos2(x, y).val << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+1;

struct node {
	int l, r, val;
} tree[N * 4 + 25 * N];
int n, m, a[N], tot, root[N];

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt].val = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	if (!tree[rt].l)
		tree[rt].l = ++tot;
	build(l, mid, tree[rt].l);
	if (!tree[rt].r)
		tree[rt].r = ++tot;
	build(mid + 1, r, tree[rt].r);
}

void update(int l, int r, int rt, int lst, int p, int c) {
	if (l == r) {
		tree[rt].val = c;
		return;
	}
	int mid = (l + r) / 2;
	if (p <= mid) {
		//右边连谁?
		tree[rt].r = tree[lst].r;
		tree[rt].l = ++tot;
		update(l, mid, tree[rt].l, tree[lst].l, p, c);
	} else {
		tree[rt].l = tree[lst].l;
		tree[rt].r = ++tot;
		update(mid + 1, r, tree[rt].r, tree[lst].r, p, c);
	}
}

int query(int l, int r, int rt, int p) {
	if (l == r) {
		return tree[rt].val;
	}
	int mid =  (l + r) >> 1;
	if (p <= mid)
		return query(l, mid, tree[rt].l, p);
	else
		return query(mid + 1, r, tree[rt].r, p);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	root[0] = ++tot;
	build(1, n, root[0]);
	for (int i = 1; i <= m; i++) {
		int opt, v, p, c;
		cin >> v >> opt >> p;
		if (opt == 1) {
			cin >> c;
			root[i] = ++tot;
			update(1, n, root[i], root[v], p, c);
		} else {
			root[i] = root[v];
			cout << query(1, n, root[i], p) << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

struct node {
	int l, r, val;
} tree[N * 4 + N * 25];
int n, m, a[N], b[N], id[N], tot, root[N];

void pushup(int rt) {
	tree[rt].val = tree[tree[rt].l].val + tree[tree[rt].r].val;
}

/*
l~r  tree[r]-tree[l-1]
*/
void build(int l, int r, int rt) {
	if (l == r) {
		return;
	}
	int mid = (l + r) >> 1;
	tree[rt].l = ++tot;
	tree[rt].r = ++tot;
	build(l, mid, tree[rt].l);
	build(mid + 1, r, tree[rt].r);
	pushup(rt);
}

void update(int l, int r, int rt, int lst, int p, int c) {
	if (l == r) {
		tree[rt].val = tree[lst].val + c;
		return;
	}
	int mid = (l + r) >> 1;
	if (p <= mid) {
		tree[rt].r = tree[lst].r;
		tree[rt].l = ++tot;
		update(l, mid, tree[rt].l, tree[lst].l, p, c);
	} else {
		tree[rt].l = tree[lst].l;
		tree[rt].r = ++tot;
		update(mid + 1, r, tree[rt].r, tree[lst].r, p, c);
	}
	pushup(rt);
}

int query(int l, int r, int L, int R, int k) {
	if (l == r) {
		return l;
	}
	int mid = (l + r) >> 1;
	//L-R的左儿子一共有多少个数
	int D = tree[tree[R].l].val - tree[tree[L].l].val;
	if (D >= k) {
		return query(l, mid, tree[L].l, tree[R].l, k);
	} else
		return query(mid + 1, r, tree[L].r, tree[R].r, k - D);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	int nn = unique(b + 1, b + n + 1) - b;
	nn--;
	for (int i = 1; i <= n; i++) {
		id[i] = lower_bound(b + 1, b + nn + 1, a[i]) - b;
	}
	build(1, nn, 1);
	for (int i = 1; i <= n; i++) {
		root[i] = ++tot;
		update(1, nn, root[i], root[i - 1], id[i], 1);
	}
	for (int i = 1; i <= m; i++) {
		int l, r, k;
		cin >> l >> r >> k;
		cout << b[query(1, nn, root[l - 1], root[r], k)] << endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, m;
double a[N];

struct node {
	double sum1, sum2;
} tree[N << 2];
double tag[N << 2];

void pushup(int rt) {
	tree[rt].sum1 = tree[rt << 1].sum1 + tree[rt << 1 | 1].sum1;
	tree[rt].sum2 = tree[rt << 1].sum2 + tree[rt << 1 | 1].sum2;
}

void pushdown(int l, int r, int rt) {
	if (tag[rt]) {
		tag[rt << 1] += tag[rt];
		tag[rt << 1 | 1] += tag[rt];
		int mid = (l + r) >> 1;
		tree[rt << 1].sum2 += 2 * tag[rt] * tree[rt << 1].sum1 + (mid - l + 1) * tag[rt] * tag[rt];
		tree[rt << 1 | 1].sum2 += 2 * tag[rt] * tree[rt << 1 | 1].sum1 + (r - mid) * tag[rt] * tag[rt];
		tree[rt << 1].sum1 += tag[rt] * (mid - l + 1);
		tree[rt << 1 | 1].sum1 += tag[rt] * (r - mid);
		tag[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt].sum1 = a[l];
		tree[rt].sum2 = a[l] * a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int L, int R, double k) {
	if (L <= l && r <= R) {
		tag[rt]+=k;
		tree[rt].sum2 += 2 * k * tree[rt].sum1 + (r - l + 1) * k * k;
		tree[rt].sum1 += k * (r - l + 1);
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(l, r, rt);
	if (L <= mid)
		update(l, mid, rt << 1, L, R, k);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R, k);
	pushup(rt);
}

double query1(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt].sum1;
	}
	double res = 0;
	int mid = (l + r) >> 1;
	pushdown(l, r, rt);
	if (L <= mid)
		res += query1(l, mid, rt << 1, L, R);
	if (R > mid)
		res += query1(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

double query2(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt].sum2;
	}
	double res = 0;
	int mid = (l + r) >> 1;
	pushdown(l, r, rt);
	if (L <= mid)
		res += query2(l, mid, rt << 1, L, R);
	if (R > mid)
		res += query2(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build(1, n, 1);
	while (m--) {
		int pos, l, r;
		double k;
		cin >> pos >> l >> r;
		if (pos == 1) {
			cin >> k;
			update(1, n, 1, l, r, k);
		} else if (pos == 2) {
			double res = query1(1, n, 1, l, r);
			cout << fixed << setprecision(4) << res / (r - l + 1) << endl;
		} else {
			int len = (r - l + 1);
			double sum1 = query1(1, n, 1, l, r);
			double sum2 = query2(1, n, 1, l, r);
			double res = sum2 / len - (sum1 * sum1) / (len * len);
			cout << fixed << setprecision(4) << res << endl;
		}
	}
	return 0;
}

/*
l~mid mid+1~r
1.tree[rt<<1].sum+tree[rt<<1|1].sum
2.tree[rt<<1].sum+tree[rt<<1|1].lmx
3.tree[rt<<1|1].sum+tree[rt<<1].rmx
4.tree[rt<<1].rmx+tree[rt<<1|1].lmx
5.tree[rt<<1].mx
6.tree[rt<<1|1].mx
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

struct node {
	int sum, lmx, rmx, mx;
	friend node operator + (node a, node b) {
		node c;
		c.sum = a.sum + b.sum;
		c.lmx = max(a.sum + b.lmx, a.lmx);
		c.rmx = max(b.sum + a.rmx, b.rmx);
		c.mx = max(a.sum + b.lmx, b.sum + a.rmx);
		c.mx = max(c.mx, max(a.mx, b.mx));
		c.mx = max(c.mx, a.sum + b.sum);
		c.mx = max(c.mx, a.rmx + b.lmx);
		return c;
	}
} tree[N << 2];
int n, m, a[N];

void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = {a[l], a[l], a[l], a[l]};
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int p, int c) {
	if (l == r) {
		tree[rt] = {c, c, c, c};
		return;
	}
	int mid = (l + r) >> 1;
	if (p <= mid)
		update(l, mid, rt << 1, p, c);
	else
		update(mid + 1, r, rt << 1 | 1, p, c);
	pushup(rt);
}

node query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	int mid = (l + r) >> 1;
	if (R <= mid)
		return query(l, mid, rt << 1, L, R);
	else if (L > mid)
		return query(mid + 1, r, rt << 1 | 1, L, R);
	else
		return query(l, mid, rt << 1, L, R) + query(mid + 1, r, rt << 1 | 1, L, R);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build(1, n, 1);
	while (m--) {
		int pos, l, r, p, c;
		cin >> pos >> l >> r;
		if (pos == 1) {
			if (l > r)
				swap(l, r);
			cout << query(1, n, 1, l, r).mx << endl;
		} else {
			update(1, n, 1, l, r);
		}
	}
	return 0;
}

/*
l~mid mid+1
c.cnt = a.cnt+b.cnt
XXXXX(XXX  XXX)XXXXX
左边的右括号，右边的左括号
cnt,left,right
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m;

struct node {
	int cnt, left, right, x;
	friend node operator + (node a, node b) {
		node c;
		c.left = b.left;
		if (b.x == 1) {
			c.left = a.left;
		}
		c.right = a.right;
		if (a.x == 1) {
			c.right = b.right;
		}
		if (a.left == 1 && b.right == 1)
			c.cnt = a.cnt + b.cnt + 1;
		else
			c.cnt = a.cnt + b.cnt;
		c.x = a.x & b.x;
		return c;
	}
} tree[N << 2];

void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = {0, 0, 0, 1};
		if (l == 1) {
			tree[rt] = {0, 1, 0, 0};
		} else if (l == n) {
			tree[rt] = {0, 0, 1, 0};
		}
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int p, char c) {
	if (l == r) {
		if (c == 'X') {
			tree[rt] = {0, 0, 0, 1};
		} else if (c == '(') {
			tree[rt] = {0, 1, 0, 0};
		} else if (c == ')') {
			tree[rt] = {0, 0, 1, 0};
		}
		return;
	}
	int mid = (l + r) >> 1;
	if (p <= mid)
		update(l, mid, rt << 1, p, c);
	else
		update(mid + 1, r, rt << 1 | 1, p, c);
	pushup(rt);
}

node query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	int mid = (l + r) >> 1;
	if (R <= mid)
		return query(l, mid, rt << 1, L, R);
	else if (L > mid)
		return query(mid + 1, r, rt << 1 | 1, L, R);
	else
		return query(l, mid, rt << 1, L, R) + query(mid + 1, r, rt << 1 | 1, L, R);
}

int main() {
	cin >> n >> m;
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		int pos, l, r, x;
		char c;
		cin >> pos;
		if (pos == 1) {
			cin >> x >> c;
			update(1, n, 1, x, c);
		} else {
			cin >> l >> r;
			cout << query(1, n, 1, l, r).cnt << endl;
		}
	}
}

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

struct node {
	int sum, Max;
} tree[N << 2];
int a[N], n, m;

void pushup(int rt) {
	tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
	tree[rt].Max = max(tree[rt << 1].Max, tree[rt << 1 | 1].Max);
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = {a[l], a[l]};
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int L, int R) {
	if (tree[rt].Max == 1)
		return;
	if (l == r) {
		tree[rt].sum = sqrt(tree[rt].sum);
		tree[rt].Max = sqrt(tree[rt].Max);
		return;
	}
	int mid = (l + r) >> 1;
	if (L <= mid)
		update(l, mid, rt << 1, L, R);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R);
	pushup(rt);
}

int query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt].sum;
	}
	int mid = (l + r) >> 1;
	int res = 0;
	if (L <= mid)
		res += query(l, mid, rt << 1, L, R);
	if (R > mid)
		res += query(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> m;
	build(1, n, 1);
	while (m--) {
		int pos, l, r;
		cin >> pos >> l >> r;
		if (l > r)
			swap(l, r);
		if (pos == 0) {
			update(1, n, 1, l, r);
		} else
			cout << query(1, n, 1, l, r) << endl;
	}
	return 0;
}

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

struct node {
	int l, r, c;
} p[N];
int n, m, t, a[N], tree[N << 2], tag[N << 2];

bool cmp(node a, node b) {
	if (a.r == b.r)
		return a.l > b.l;
	return a.r < b.r;
}

void pushup(int rt) {
	tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}

void pushdown(int rt) {
	if (tag[rt]) {
		tag[rt << 1] += tag[rt];
		tag[rt << 1 | 1] += tag[rt];
		tree[rt << 1] += tag[rt];
		tree[rt << 1 | 1] += tag[rt];
		tag[rt] = 0;
	}
}

void update(int l, int r, int rt, int L, int R, int c) {
	if (L <= l && r <= R) {
		tree[rt] += c;
		tag[rt] += c;
		return;
	}
	pushdown(rt);
	int mid = (l + r) >> 1;
	if (L <= mid)
		update(l, mid, rt << 1, L, R, c);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R, c);
	pushup(rt);
}

int query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	pushdown(rt);
	int mid = (l + r) >> 1;
	int res = 0;
	if (L <= mid)
		res = max(res, query(l, mid, rt << 1, L, R));
	if (R > mid)
		res = max(res, query(mid + 1, r, rt << 1 | 1, L, R));
	return res;
}

signed main() {
	cin >> n >> m >> t;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].l >> p[i].r >> p[i].c;
	}
	sort(p + 1, p + n + 1, cmp);
	int res = 0;
	for (int i = 1; i <= n; i++) {
		//	cout << i << endl;
		int l = p[i].l, r = p[i].r, c = p[i].c;
		int tmp = query(1, m, 1, l, r - 1);
		//	cout << i << endl;
		if (tmp + c <= t) {
			update(1, m, 1, l, r - 1, c);
			res += c;
		} else if(t-tmp>0){
			update(1, m, 1, l, r - 1, t - tmp);
			res += t - tmp;
		}
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, m, a[N], dep[N], siz[N], fa[N], son[N];
int cnt, top[N], id[N], wt[N];
int r, p;
int tree[N << 2], tag[N << 2];
vector<int>e[N];

void dfs1(int x, int f, int deep) {
	dep[x] = deep;
	fa[x] = f;
	siz[x] = 1;
	int maxx = 0;
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs1(v, x, deep + 1);
		siz[x] += siz[v];
		if (siz[v] > maxx) {
			maxx = siz[v];
			son[x] = v;
		}
	}
}

void dfs2(int x, int topfa) {
	id[x] = ++cnt;
	top[x] = topfa;
	wt[cnt] = a[x];
	if (!son[x])
		return;
	dfs2(son[x], topfa);
	for (auto v : e[x]) {
		if (v == fa[x] || v == son[x])
			continue;
		dfs2(v, v);
	}
}

void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
	tree[rt] %= p;
}

void pushdown(int l, int r, int rt) {
	if (tag[rt]) {
		tag[rt << 1] += tag[rt];
		tag[rt << 1] %= p;
		tag[rt << 1 | 1] += tag[rt];
		tag[rt << 1 | 1] %= p;
		int mid = (l + r) >> 1;
		tree[rt << 1] += tag[rt] * (mid - l + 1);
		tree[rt << 1] %= p;
		tree[rt << 1 | 1] += tag[rt] * (r - mid);
		tree[rt << 1 | 1] %= p;
		tag[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = wt[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int L, int R, int c) {
	if (L <= l && r <= R) {
		tag[rt] += c;
		tag[rt] %= p;
		tree[rt] += c * (r - l + 1);
		tree[rt] %= p;
		return;
	}
	pushdown(l, r, rt);
	int mid = (l + r) >> 1;
	if (L <= mid)
		update(l, mid, rt << 1, L, R, c);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R, c);
	pushup(rt);
}

int query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	int mid = (l + r) >> 1;
	pushdown(l, r, rt);
	int res = 0;
	if (L <= mid)
		res += query(l, mid, rt << 1, L, R), res %= p;
	if (R > mid)
		res += query(mid + 1, r, rt << 1 | 1, L, R), res %= p;
	return res;
}

void pos1(int x, int y, int z) {
	z %= p;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);
		update(1, n, 1, id[top[x]], id[x], z);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	update(1, n, 1, id[x], id[y], z);
}

int pos2(int x, int y) {
	int res = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);
		res += query(1, n, 1, id[top[x]], id[x]);
		res %= p;
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	res += query(1, n, 1, id[x], id[y]);
	res%=p;
	return res;
}

void pos3(int x, int z) {
	z %= p;
	update(1, n, 1, id[x], id[x] + siz[x] - 1, z);
}

int pos4(int x) {
	return query(1, n, 1, id[x], id[x] + siz[x] - 1);
}

signed main() {
	cin >> n >> m >> r >> p;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(r, 0, 1);
	dfs2(r, r);
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		int pos, x, y, z;
		cin >> pos;
		if (pos == 1) {
			cin >> x >> y >> z;
			pos1(x, y, z);
		} else if (pos == 2) {
			cin >> x >> y;
			cout << pos2(x, y) << endl;
		} else if (pos == 3) {
			cin >> x >> z;
			pos3(x, z);
		} else {
			cin >> x;
			cout << pos4(x) << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
vector<int>e[N];
int n, m, a[N], son[N], siz[N], fa[N], dep[N];
int top[N], tot, id[N], wt[N], root;
int tree[N << 2], tag[N << 2];

void dfs1(int x, int f, int deep) {
	dep[x] = deep;
	siz[x] = 1;
	fa[x] = f;
	int maxx = 0;
	for (auto v : e[x]) {
		if (v == f)
			continue;
		dfs1(v, x, deep + 1);
		siz[x] += siz[v];
		if (maxx < siz[v]) {
			maxx = siz[v];
			son[x] = v;
		}
	}
}

void dfs2(int x, int topfa) {
	top[x] = topfa;
	id[x] = ++tot;
	wt[tot] = a[x];
	if (!son[x])
		return;
	dfs2(son[x], topfa);
	for (auto v : e[x]) {
		if (v == fa[x] || v == son[x])
			continue;
		dfs2(v, v);
	}
}

void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void pushdown(int l, int r, int rt) {
	if (tag[rt]) {
		tag[rt << 1] += tag[rt];
		tag[rt << 1 | 1] += tag[rt];
		int mid = (l + r) >> 1;
		tree[rt << 1] += tag[rt] * (mid - l + 1);
		tree[rt << 1 | 1] += tag[rt] * (r - mid);
		tag[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = wt[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int L, int R, int c) {
	if (L <= l && r <= R) {
		tag[rt] += c;
		tree[rt] += c * (r - l + 1);
		return;
	}
	int mid =  (l + r) >> 1;
	pushdown(l, r, rt);
	if (L <= mid)
		update(l, mid, rt << 1, L, R, c);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R, c);
	pushup(rt);
}

int query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	pushdown(l, r, rt);
	int mid = (l + r) >> 1;
	int res = 0;
	if (L <= mid)
		res += query(l, mid, rt << 1, L, R);
	if (R > mid)
		res += query(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

void pos1(int x) {
	root = x;
}

void pos2(int x, int y, int c) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);
		update(1, n, 1, id[top[x]], id[x], c);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	update(1, n, 1, id[x], id[y], c);
}

int findroot(int x, int y) {
	//在x的儿子中，找到子树中含有y
	while (top[x] != top[y]) {
		y = top[y];
		if (fa[y] == x)
			return y;
		y = fa[y];
	}
	while (fa[y] != x) {
		y = fa[y];
	}
	return y;
}

void pos3(int x, int c) {
	if (x == root) {
		update(1, n, 1, 1, n, c);
	}
	//root不在x的子树里
	else if (id[root] < id[x] || id[root] > id[x] + siz[x] - 1) {
		update(1, n, 1, id[x], id[x] + siz[x] - 1, c);
	} else {
		int v = findroot(x, root);
		if (id[v] != 1) {
			update(1, n, 1, 1, id[v] - 1, c);
		}
		if (id[v] + siz[v] <= n) {
			update(1, n, 1, id[v] + siz[v], n, c);
		}
	}
}

int pos4(int x, int y) {
	int res = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])
			swap(x, y);
		res += query(1, n, 1, id[top[x]], id[x]);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])
		swap(x, y);
	res += query(1, n, 1, id[x], id[y]);
	return res;
}

int pos5(int x) {
	if (x == root) {
		return tree[1];
	} else if (id[root] < id[x] || id[root] > id[x] + siz[x] - 1) {
		return query(1, n, 1, id[x], id[x] + siz[x] - 1);
	} else {
		int res = 0;
		int v = findroot(x, root);
		if (id[v] != 1) {
			res += query(1, n, 1, 1, id[v] - 1);
		}
		if (id[v] + siz[v] <= n) {
			res += query(1, n, 1, id[v] + siz[v], n);
		}
		return res;
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 2; i <= n; i++) {
		int x;
		cin >> x;
		e[x].push_back(i);
		e[i].push_back(x);
	}
	dfs1(1, 0, 1);
	dfs2(1, 1);
	build(1, n, 1);
	cin >> m;
	root = 1;
	for (int i = 1; i <= m; i++) {
		int pos, x, y, z;
		cin >> pos;
		if (pos == 1) {
			cin >> x;
			pos1(x);
		} else if (pos == 2) {
			cin >> x >> y >> z;
			pos2(x, y, z);
		} else if (pos == 3) {
			cin >> x >> z;
			pos3(x, z);
		} else if (pos == 4) {
			cin >> x >> y;
			cout << pos4(x, y) << endl;
		} else if (pos == 5) {
			cin >> x;
			cout << pos5(x) << endl;
		}
	}
	return 0;
}

Please claim the assignment to see the problems.

Status: Live...
Problem: 32
Open Since: 2025-10-10 0:00
Deadline: 2025-12-31 23:59
Extension: 24 hour(s)

Homework Introduction

Problem

SIGN IN