Segment Tree siêu dễ

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho dãy số A1,A2,,Anm truy vấn. Có 2 loại truy vấn:

  • Loại 1: 1xy: gán giá trị của Ax=y.
  • Loại 2: 2lr (lr): yêu cầu tìm giá trị nhỏ nhất trong đoạn [l,r].

Input

  • Dòng đầu chứa số 2 nguyên n,m (n,m105).
  • Dòng thứ 2 chứa n số nguyên dương A1,A2,,An.
  • m dòng tiếp theo chứa m truy vấn thuộc một trong hai loại trên.

Tất cả các số đều dương và nhỏ hơn 109.

Output

  • Kết quả của các truy vấn loại 2 theo thứ tự.

Sample Input 1:

Copy
4 4
2 6 8 7
2 1 3
1 2 1
2 1 3
2 3 4

Sample Output 1:

Copy
2
1
7


Segment Tree rất dễ

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho dãy số A1,A2,,Anm truy vấn. Có 2 loại truy vấn:

  • Loại 1: 1lrx: tăng đoạn Al,Al+1,...,Ar lên x đơn vị.
  • Loại 2: 2lr (lr): yêu cầu tìm giá trị nhỏ nhất trong đoạn [l,r].

Input

  • Dòng đầu chứa số 2 nguyên n,m (n,m105).
  • Dòng thứ 2 chứa n số nguyên dương A1,A2,,An.
  • m dòng tiếp theo chứa m truy vấn thuộc một trong hai loại trên.

Tất cả các số đều dương và nhỏ hơn 109.

Output

  • Kết quả của các truy vấn loại 2 theo thứ tự.

Sample Input 1:

Copy
4 4
2 6 8 7
2 2 4
1 1 3 2
2 1 3
2 2 4

Sample Output 1:

Copy
6
4
7


Segment Tree quá dễ

Nộp bài
Time limit: 3.0 / Memory limit: 256M

Point: 100

Cho dãy số A1,A2,,Anm truy vấn. Có 3 loại truy vấn:

  • Loại 1: +lrx: cộng các số trong đoạn Al,Al+1,...,Ar với x.
  • Loại 2: lrx: nhân các số trong đoạn Al,Al+1,...,Ar với x.
  • Loại 3: ?p: đưa ra giá trị của Ap mod 109+7.

Input

  • Dòng đầu chứa số 2 nguyên n,m (n,m105).
  • Dòng thứ 2 chứa n số nguyên dương A1,A2,,An.
  • m dòng tiếp theo chứa m truy vấn thuộc một trong ba loại trên.

Tất cả các số đều dương và nhỏ hơn 109.

Output

  • Kết quả của các truy vấn loại 3 theo thứ tự.

Subtask

  • Sub 1: n,m1000.
  • Sub 2: n,m100000.

Sample Input 1:

Copy
4 5
1 3 0 7
+ 3 3 9
? 3
* 2 4 6
+ 1 4 9
? 4

Sample Output 1:

Copy
9
51

Segment Tree cực dễ

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho dãy số A1,A2,,An và số nguyên dương k. Hãy tìm dãy con dài nhất của A (không nhất thiết phải liên tiếp) sao cho chênh lệch giữa 2 phần tử liên tiếp trong dãy con không ít hơn k.

Input

  • Dòng đầu chứa số 2 nguyên n,k (n105).
  • Dòng thứ 2 chứa n số nguyên dương A1,A2,,An.

Tất cả các số đều dương và nhỏ hơn 109.

Output

  • Độ dài của dãy con dài nhất thỏa mãn yêu cầu đề bài.

Subtask

  • Sub 1: n,m1000.
  • Sub 2: n,m100000.

Sample Input 1:

Copy
6 15
1014 1024 1034 1045 1030 998

Sample Output 1:

Copy
4

Segment Tree hơi dễ

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho dãy số độ dài nm truy vấn. Ban đầu tất cả các số đều bằng 0. Có 2 loại truy vấn:

  • Loại 1: 1lrab: cộng thêm vào phần tử thứ i thêm (iL)a+b đơn vị với mọi LiR.
  • Loại 2: 2lr (lr): yêu cầu tìm tổng của các phần tử trong khoảng [l,r], lấy dư cho 109+7.

Input

  • Dòng đầu chứa số 2 nguyên n,m (n,m105).
  • m dòng tiếp theo chứa m truy vấn thuộc một trong hai loại trên.

Tất cả các số đều dương và nhỏ hơn 109.

Output

  • Kết quả của các truy vấn loại 2 theo thứ tự.

Subtask

  • Sub 1: n,m1000.
  • Sub 2: n,m100000.

Sample Input 1:

Copy
5 4
1 1 5 1 1
2 1 5
1 2 3 1 1
2 1 5

Sample Output 1:

Copy
15
18