Trị tuyệt đối của đoạn con - LCOJ: Luyện Code Online Judge

LBC_2E - Trị tuyệt đối của đoạn con

Điểm: 1,50 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

wronganswer

Dạng bài

Quỳnh đang nghiên cứu một số đề tài về tin học, Quỳnh nghiên cứu giá trị tuyệt đối của một dãy ~X~ đó là chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất của dãy ~X~.

Ví dụ ta có dãy ~X = [1, 6, 9, 3, -1, 7]~, giá trị tuyệt đối của dãy ~X~ này là ~|9 - (-1)| = 10~.

Vào một ngày đẹp trời, Quỳnh mời bạn tới phòng nghiên cứu, cô ấy cho bạn một dãy ~N~ số nguyên ~A_1, A_2, \cdots , A_N~. Cô ấy nhờ bạn viết 1 chương trình máy tính thực hiện ~Q~ phép toán trên dãy trên để có thể dữ liệu về nghiên cứu của mình, ~Q~ phép toán này có 2 loại:

~1 \ u \ v~: Phép toán này sẽ gán giá trị ~A_u = v~ ~(1 \leq u \leq N, -10^9 \leq v \leq 10^9)~.
~2 \ u \ v~: Phép toán này sẽ tính giá trị tuyệt đối của dãy ~A_u, A_{u + 1}, \cdots , A_v~ ~(1 \leq u \leq v \leq N)~.

Bạn hãy giúp Quỳnh viết chương trình thực hiện ~Q~ phép toán trên.

Input

Dòng đầu tiên gồm 2 số nguyên dương ~N, Q~ được phân tách nhau bởi dấu cách ~(1 \leq N, Q \leq 2 \times 10^5)~.
Dòng tiếp theo gồm ~N~ số nguyên của dãy ~A_1, A_2, \cdots , A_N~ ~(-10^9 \leq A_i \leq 10^9)~.
~Q~ dòng tiếp theo, mỗi dòng thể hiện 1 trong 2 phép toán nêu trên.

Output

Gồm nhiều dòng, mỗi dòng trả lời các phép toán loại ~2 \ u \ v~.

Sample

Input #1

8 5
3 2 4 5 1 1 5 3
2 1 4
2 2 7
1 5 7
1 6 0
2 2 7

Output #1

3
4
7

Bình luận

Please read the guidelines before commenting.

để ý kĩ ta thấy được abs của đoạn từ ~a_u~ đến ~a_v~ chỉ là abs(giá trị lớn nhất - giá trị nhỏ nhất)

với ~N~ chỉ bé hơn ~2.10^5~ nên bài này rất thích hợp để dùng CTDL SegmentTree

với mỗi truy vấn loại 2 in ra abs(max - min) (trước đó đã build cây max min rồi nhé :D)

Code tham khảo (C++)

#include <bits/stdc++.h>

#define MAX 200002
#define INF 1000000000

using namespace std;

int n, q, ques, u, v;
int a[MAX];

struct node {
  int mn, mx;
  node() {
    mn = INF, mx = -INF;
  }
  node(int _mn, int _mx) {
    mn = _mn, mx = _mx;
  }
};

node st[MAX << 2];

void build(int id, int l, int r) {
  if(l == r) {
    st[id] = node(a[l], a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(id << 1, l, mid);
  build(id << 1 | 1, mid + 1, r);
  st[id].mn = min(st[id << 1].mn, st[id << 1 | 1].mn);
  st[id].mx = max(st[id << 1].mx, st[id << 1 | 1].mx);
}

void update(int id, int l, int r, int u, int v) {
  if(l == r) {
    st[id] = node(v, v);
    return;
  }
  int mid = (l + r) >> 1;
  (u <= mid ? update(id << 1, l, mid, u, v) : update(id << 1 | 1, mid + 1, r, u, v));
  st[id].mn = min(st[id << 1].mn, st[id << 1 | 1].mn);
  st[id].mx = max(st[id << 1].mx, st[id << 1 | 1].mx);
}

node query(int id, int l, int r, int u, int v) {
  if(r < u || v < l) return node(INF, -INF);
  if(u <= l && r <= v) return st[id];
  int mid = (l + r) >> 1;
  node L = query(id << 1, l, mid, u, v);
  node R = query(id << 1 | 1, mid + 1, r, u, v);
  return node(min(L.mn, R.mn), max(L.mx, R.mx));
}

int main() {
  ios::sync_with_stdio(true);  
  cin>>n>>q;
  for(int i = 1; i <= n; ++i) cin>>a[i];
  build(1, 1, n);
  while(q--) {
    cin>>ques>>u>>v;
    if(ques == 1) update(1, 1, n, u, v);
    else cout<<abs(query(1, 1, n, u, v).mn - query(1, 1, n, u, v).mx)<<'\n';
  }
  return 0;
}