- #include "iostream"#include "string.h"#include "stack"#include "queue"#include "string"#include "vector"#include "set"#include "map"#include "algorithm"#include "stdio.h"#include "math.h"#define ll long long#define bug(x) cout << x << " " << "UUUUU" << endl;#define mem(a) memset(a, 0, sizeof(a))#define mp(x, y) make_pair(x, y)#define pb(x) push_back(x) using namespace std;
- const long long INF = 1e18 + 1LL;
- const int inf = 1e9 + 1e8;
- const int N = 5e4 + 100;
- const ll mod = 1e9 + 7;
- int mi[N << 2],
- ma[N << 2],
- maa,
- mii;
- void push_up(int root) {
- mi[root] = min(mi[root * 2], mi[root * 2 + 1]);
- ma[root] = max(ma[root * 2], ma[root * 2 + 1]);
- }
- void creat(int root, int l, int r) {
- if (l == r) {
- scanf("%d", &ma[root]);
- mi[root] = ma[root]; //cout<<l<<"UUUUUUUUUU"<<endl;
- return;
- }
- int mid = l + r >> 1;
- creat(root * 2, l, mid);
- creat(root * 2 + 1, mid + 1, r);
- push_up(root);
- }
- void query(int root, int l, int r, int L, int R) {
- if (l == L && r == R) {
- maa = max(maa, ma[root]),
- mii = min(mii, mi[root]);
- return;
- }
- int mid = l + r >> 1;
- if (R <= mid) query(root * 2, l, mid, L, R);
- else if (L > mid) query(root * 2 + 1, mid + 1, r, L, R);
- else {
- query(root * 2, l, mid, L, mid);
- query(root * 2 + 1, mid + 1, r, mid + 1, R);
- }
- }
- int main() {
- //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
- int n,
- q,
- l,
- r;
- cin >> n >> q;
- creat(1, 1, n);
- while (q--) {
- scanf("%d%d", &l, &r);
- maa = -inf,
- mii = inf;
- query(1, 1, n, l, r);
- printf("%d\n", maa - mii);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2222614.html