Có một tòa nhà cao \(N\) tầng, mỗi tầng có đúng một cư dân. Các tầng được đánh số từ \(0\) đến \(N-1\) theo thứ tự từ dưới lên; cư dân \(r\) sống ở tầng \(r\).

Mỗi tầng có ban công trồng cây. Cư dân có thể giúp tưới cây ở ban công ngay bên dưới. Mỗi sáng tại thời điểm \(0\), mọi cư dân rời tòa nhà. Ban đầu cư dân \(r\) về nhà lúc \(t_r\). Nếu \(r\) về sớm hơn nghiêm ngặt người ở tầng dưới, tức \(t_r<t_{r-1}\), thì \(r\) tưới cây giúp cư dân \(r-1\); nếu không, cư dân \(r-1\) tự tưới.

Cuối mỗi ngày xảy ra đúng một sự kiện:

• !: một cư dân thay đổi giờ về nhà, có hiệu lực từ ngày kế tiếp.
• ?: một cư dân hỏi mình đã tưới cây giúp tầng dưới bao nhiêu lần.

Cư dân \(0\) không tưới giúp ai; cây của cư dân \(N-1\) không được ai ở tầng trên tưới giúp.

Dữ liệu vào

Dòng đầu chứa \(N,D\), số cư dân và số ngày cần theo dõi.

Dòng tiếp theo chứa \(t_0,t_1,\ldots,t_{N-1}\).

\(D\) dòng tiếp theo, dòng thứ \(i\) mô tả sự kiện cuối ngày \(i\):

• ! r x: từ ngày kế tiếp, đặt \(t_r=x\) (\(0\le r<N\)). \(x\) có thể bằng giá trị hiện tại.
• ? r: hỏi số lần cư dân \(r\) đã tưới giúp cư dân \(r-1\) kể từ đầu ngày \(0\) (\(1\le r<N\)).

Bảo đảm có ít nhất một sự kiện ?.

Dữ liệu ra

Với mỗi sự kiện ? r, in số lần cư dân \(r\) đã tưới cây giúp cư dân \(r-1\) kể từ đầu ngày \(0\). Không tính số lần cư dân tự tưới cây của mình.

Ràng buộc

• \(2\le N\le200\,000\).
• \(1\le D\le200\,000\).
• Ban đầu và sau mỗi thay đổi, \(1\le t_r\le10^9\).

Phân nhóm

1. \(9\) điểm: \(D=1\) và sự kiện duy nhất là ?.
2. \(12\) điểm: mọi sự kiện đều là ?.
3. \(13\) điểm: \(N=2\).
4. \(18\) điểm: \(N,D\le2000\).
5. \(21\) điểm: mỗi cư dân thay đổi giờ về nhiều nhất một lần.
6. \(27\) điểm: không có ràng buộc thêm.

Ví dụ

3 4
7 7 5
? 2
? 1
? 2
? 2

1
0
3
4

2 5
5 7
! 1 4
? 1
! 0 4
! 1 6
? 1

1
2

4 6
13 9 15 2
! 1 18
? 3
! 0 12
! 2 1
? 1
? 2

2
1
5

3 6
5 2 4
? 1
! 1 8
! 0 10
! 1 3
? 1
? 2

1
4
2

Nguồn

EGOI 2026 - Ngày 2, Watering Plants.

Đề bài EGOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).