APIO 2019

Các nhà khảo cổ tìm thấy một thiết bị kỳ lạ có lẽ là của nền văn minh cổ đại tạo ra. Thiết bị có màn hình hiển thị hai số nguyên \(x\) và \(y\).

Sau khi khám phá thiết bị này, các nhà khoa học đã đưa ra kết luận rằng thiết bị này là một loại đồng hồ. Nó xác định thời gian \(t\) so với một thời điểm nào đó trong quá khứ, nhưng hiển thị thời gian theo một cách kỳ lạ, có lẽ được sử dụng bởi những người tạo ra thiết bị này. Nếu thời gian đó là một số nguyên \(t\), hai số nguyên được hiển thị là \(x=((t+\lfloor t/B\rfloor)\bmod A)\) và \(y=(t\bmod B)\). Ở đây, \(\lfloor x\rfloor\) là hàm làm tròn xuống — số nguyên lớn nhất nhỏ hơn hoặc bằng \(x\).

Các nhà khảo cổ đã nghiên cứu thiết bị và phát hiện ra rằng màn hình của nó không được bật mọi lúc trong quá khứ. Thực chất, nó chỉ hoạt động trong \(n\) khoảng thời gian liên tục trong quá khứ, khoảng thứ \(i\) là từ thời điểm \(l_i\) đến thời điểm \(r_i\), bao gồm cả hai đầu mút. Bây giờ các nhà khoa học muốn tính toán xem có bao nhiêu cặp phân biệt \((x,y)\) được thiết bị hiển thị khi màn hình được bật.

Hai cặp \((x_1,y_1)\) và \((x_2,y_2)\) là phân biệt nếu \(x_1\ne x_2\) hoặc \(y_1\ne y_2\).

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(n\), \(A\) và \(B\) (\(1\le n\le 10^6\); \(1\le A,B\le 10^{18}\)).

Mỗi dòng trong số \(n\) dòng tiếp theo chứa hai số nguyên \(l_i\) và \(r_i\) là thời điểm bắt đầu và kết thúc của đoạn \([l_i,r_i]\) khi thiết bị hoạt động trong quá khứ (\(0\le l_i\le r_i\le 10^{18}\), \(r_i<l_{i+1}\)).

Dữ liệu ra

In ra số lượng cặp phân biệt \((x,y)\) được hiển thị trên thiết bị khi nó được bật trong quá khứ.

Phân nhóm

Đặt \(S=\sum_{i=1}^{n}(r_i-l_i+1)\) và \(L=\max_{i=1}^{n}(r_i-l_i+1)\).

Ví dụ

3 3 3
4 4
7 9
17 18

4

3 5 10
1 20
50 68
89 98

31

2 16 13
2 5
18 18

5

Giải thích

Trong test ví dụ đầu tiên, màn hình thiết bị hiển thị các số nguyên sau trong quá khứ.

Vì vậy có bốn cặp phân biệt \((0,0)\), \((0,1)\), \((1,2)\), \((2,1)\).

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2019, được lưu trong kho đề APIO.

St. Petersburg nằm trên \(n\) hòn đảo được kết nối bởi \(m\) cây cầu. Các hòn đảo được gán nhãn bởi các số nguyên từ \(1\) đến \(n\) và các cây cầu được gán nhãn từ \(1\) đến \(m\). Mỗi cây cầu nối hai hòn đảo khác nhau. Một số cây cầu được xây dựng trong thời đại Peter, và một số khác được xây dựng gần đây. Đó là lý do tại sao những cây cầu khác nhau có giới hạn trọng lượng khác nhau. Cụ thể, chỉ những chiếc xe có trọng lượng không vượt quá \(d_i\) mới có thể đi qua cây cầu \(i\). Đôi khi, một số cây cầu ở St. Petersburg đang được cải tạo, nhưng điều này không nhất thiết sẽ làm cho cây cầu chắc chắn hơn, vì vậy một số giá trị \(d_i\) có thể tăng hoặc giảm. Bạn phát triển một sản phẩm nhằm hỗ trợ cư dân và du khách của thành phố. Hiện tại, bạn phát triển một mô-đun phải thực hiện hai loại truy vấn:

1. Thay đổi giới hạn trọng lượng của cầu \(b_j\) thành \(r_j\).
2. Đếm số lượng hòn đảo có thể đi tới được từ đảo \(s_j\) bằng một chiếc xe có trọng lượng \(w_j\).

Hãy trả lời tất cả các truy vấn loại thứ hai.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) — số lượng hòn đảo và số cây cầu ở St. Petersburg (\(1\le n\le 50\,000\), \(0\le m\le 100\,000\)).

Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa ba số nguyên \(u_i\), \(v_i\) và \(d_i\), mô tả cây cầu nối hai hòn đảo \(u_i\) và \(v_i\), có giới hạn trọng lượng ban đầu là \(d_i\) (\(1\le u_i,v_i\le n\); \(u_i\ne v_i\); \(1\le d_i\le 10^9\)).

Dòng tiếp theo chứa một số nguyên \(q\) — số lượng truy vấn (\(1\le q\le 100\,000\)). Tiếp theo là \(q\) dòng chứa các truy vấn.

Mỗi truy vấn bắt đầu bằng một số nguyên \(t_j\) (\(t_j\in\{1,2\}\)).

Nếu \(t_j=1\), truy vấn là loại một, tiếp theo là hai số nguyên \(b_j\) và \(r_j\), nghĩa là giới hạn trọng lượng của cây cầu \(b_j\) sẽ thay đổi thành \(r_j\) (\(1\le b_j\le m\), \(1\le r_j\le 10^9\)).

Nếu \(t_j=2\), truy vấn là loại hai, tiếp theo là hai số nguyên \(s_j\) và \(w_j\), mô tả chiếc xe có trọng lượng \(w_j\) ở hòn đảo \(s_j\) (\(1\le s_j\le n\), \(1\le w_j\le 10^9\)).

Dữ liệu ra

Đối với mỗi truy vấn loại thứ hai, in câu trả lời trên một dòng riêng biệt.

Phân nhóm

Ví dụ

3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2

3
2
3

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

1
7
7
5
7
7
4

Giải thích

Các đường màu xanh lá cây thể hiện những cây cầu mà chiếc xe ở truy vấn có thể đi qua. Các đỉnh màu xanh biểu diễn những hòn đảo có thể đi đến được bằng chiếc xe này. Mũi tên chỉ vào hòn đảo nơi chiếc xe được đặt ban đầu.

{{asset:apio19bridges/pic0.png}}

Truy vấn 1.

{{asset:apio19bridges/pic1.png}}

Truy vấn 3.

{{asset:apio19bridges/pic2.png}}

Truy vấn 5.

Hình ảnh cho ví dụ thứ nhất.

{{asset:apio19bridges/pic3.png}}

Truy vấn 1.

{{asset:apio19bridges/pic4.png}}

Truy vấn 3.

{{asset:apio19bridges/pic5.png}}

Truy vấn 5.

{{asset:apio19bridges/pic6.png}}

Truy vấn 8.

{{asset:apio19bridges/pic7.png}}

Truy vấn 9.

{{asset:apio19bridges/pic8.png}}

Truy vấn 11.

{{asset:apio19bridges/pic9.png}}

Truy vấn 12.

Hình ảnh cho ví dụ thứ hai.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2019, được lưu trong kho đề APIO.

Có một chiếc xe taxi tự lái trên một đường phố dài ở Innopolis. Đường phố này có \(n+1\) điểm dừng taxi và \(n\) đoạn đường nối các điểm dừng liền nhau. Trên mỗi đoạn đường có một cây đèn đường. Nếu cây đèn thứ \(i\) bật sáng, nó chiếu sáng đoạn đường nối điểm dừng thứ \(i\) và điểm dừng thứ \(i+1\). Ngược lại, đoạn đường này bị tối.

Để đảm bảo an toàn, xe taxi tự lái chỉ có thể chạy trên các đoạn đường được chiếu sáng. Hay nói cách khác, xe taxi có thể chạy từ điểm dừng \(a\) tới điểm dừng \(b\) (\(a<b\)) nếu các đoạn đường nằm giữa \(a\) và \(a+1\), \(a+1\) và \(a+2\), \(\ldots\), \(b-1\) và \(b\) được chiếu sáng tại thời điểm đó.

Sau khi bị hỏng hoặc sửa chữa, các cây đèn đường có thể bật hoặc tắt. Bạn được cho trạng thái ban đầu của các cây đèn đường tại thời điểm \(0\). Sau đó, có các sự kiện diễn ra vào thời điểm cuối của các giờ \(1,2,\ldots,q\). Có chính xác một sự kiện diễn ra vào thời điểm cuối của mỗi giờ. Có hai loại sự kiện:

• toggle \(i\) — cây đèn thứ \(i\) chuyển trạng thái: nếu nó đang bật thì nó sẽ được tắt; nếu nó đang tắt thì nó sẽ được bật.
• query \(a\) \(b\) — trưởng phòng taxi tự lái muốn biết tổng số giờ từ thời điểm \(0\) tới thời điểm hiện tại mà chiếc xe taxi có khả năng lái từ điểm dừng \(a\) tới điểm dừng \(b\).

Hãy giúp trưởng phòng taxi tự lái trả lời các câu hỏi này.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1\le n,q\le 300\,000\)) — số lượng cây đèn và số lượng sự kiện.

Dòng thứ hai chứa một xâu kí tự \(s\) mô tả trạng thái ban đầu của các cây đèn (\(|s|=n\)). \(s_i\) là 1 nếu cây đèn thứ \(i\) đang bật, và \(s_i\) là 0 nếu cây đèn thứ \(i\) đang tắt.

Mỗi dòng trong \(q\) dòng tiếp theo mô tả các sự kiện. Dòng thứ \(i\) mô tả một sự kiện sẽ diễn ra sau giờ \(i\).

• toggle \(i\) (\(1\le i\le n\)) — cây đèn thứ \(i\) đổi trạng thái.
• query \(a\) \(b\) (\(1\le a<b\le n+1\)) — tính số lượng giờ cho đến thời điểm hiện tại mà taxi có thể lái từ điểm dừng \(a\) đến điểm dừng \(b\).

Ít nhất một trong các sự kiện là query.

Dữ liệu ra

Với mỗi sự kiện query, in ra một số nguyên là đáp án cho câu hỏi.

Phân nhóm

Ví dụ

5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6

1
2
0
0
1
2

Giải thích

Trong ví dụ này:

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2019, được lưu trong kho đề APIO.