忠诚

链接

不想说了,典型的线段树,之前已经写过,就不赘述了

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
class 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);
	}
	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 m, n;
	cin >> m >> n;
	vector<int>data(m + 1);
	for (int i = 1;i <= m;i++) {
		cin >> data[i];
	}
	node tree(data);
	for (int i = 0;i < n;i++) {
		int l, r;
		cin >> l >> r;
		cout << tree.query(1, 1, m, l, r) <<" ";
	}
}