Balanced Lineup G

链接

emm,写两棵树?

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
class min_node {
public:
	vector<int>tree;
	vector<int>lazy;
	int n;
	void build(vector<int>& data, int left, int right, int root) {
		if (left == right) {
			tree[root] = data[left];
			return;
		}
		int mid = left + (right - left) / 2;
		build(data, left, mid, 2 * root);
		build(data, mid + 1, right, 2 * root + 1);
		tree[root] = min(tree[2 * root], tree[2 * root + 1]);
	}
	void push_back(int root) {
		if (lazy[root]) {
			int l = lazy[root];
			int left = 2 * root;
			int right = 2 * root + 1;
			tree[left] += l;
			tree[right] += l;
			lazy[left] += l;
			lazy[right] += l;
			lazy[root] = 0;
		}
	}
	int query(int root, int left, int right, int ql, int qr) {
		if (ql > right || qr < left) {
			return INT_MAX;
		}
		if (ql <= left && qr >= right) {
			return tree[root];
		}
		push_back(root);
		int mid = left + (right - left) / 2;
		int min_l = query(2 * root, left, mid, ql, qr);
		int min_r = query(2 * root + 1, mid + 1, right, ql, qr);
		return min(min_l, min_r);
	}
	min_node(vector<int>& data) {
		n = data.size() - 1;
		tree.resize(4 * (n + 1));
		lazy.resize(4 * (n + 1), 0);
		build(data, 1, n, 1);
	}
};
class max_node {
public:
	vector<int>tree;
	vector<int>lazy;
	int n;
	void build(vector<int>& data, int left, int right, int root) {
		if (left == right) {
			tree[root] = data[left];
			return;
		}
		int mid = left + (right - left) / 2;
		build(data, left, mid, 2 * root);
		build(data, mid + 1, right, 2 * root + 1);
		tree[root] = max(tree[2 * root], tree[2 * root + 1]);
	}
	void push_back(int root) {
		if (lazy[root]) {
			int l = lazy[root];
			int left = 2 * root;
			int right = 2 * root + 1;
			tree[left] += l;
			tree[right] += l;
			lazy[left] += l;
			lazy[right] += l;
			lazy[root] = 0;
		}
	}
	int query(int root, int left, int right, int ql, int qr) {
		if (ql > right || qr < left) {
			return INT_MIN;
		}
		if (ql <= left && qr >= right) {
			return tree[root];
		}
		push_back(root);
		int mid = left + (right - left) / 2;
		int max_l = query(2 * root, left, mid, ql, qr);
		int max_r = query(2 * root + 1, mid + 1, right, ql, qr);
		return max(max_l, max_r);
	}
	max_node(vector<int>& data) {
		n = data.size() - 1;
		tree.resize(4 * (n + 1));
		lazy.resize(4 * (n + 1), 0);
		build(data, 1, n, 1);
	}
};
int main() {
	int n, q;
	cin >> n >> q;
	vector<int>data(n + 1);
	for (int i = 1;i <= n;i++) {
		cin >> data[i];
	}
	min_node min_tree(data);
	max_node max_tree(data);
	for (int i = 0;i < q;i++) {
		int left, right;
		cin >> left >> right;
		cout << max_tree.query(1, 1, n, left, right) - min_tree.query(1, 1, n, left, right) << endl;
	}
}

时间复杂度:O(n + 2q log n)

空间复杂度:O(n)