Có \(N\) thị trấn nằm dọc theo một thung lũng sâu và thẳng ở đất nước JOI. Các thị trấn được đánh số \(0,1,\ldots,N-1\) theo thứ tự khoảng cách tăng dần từ biển.

Ông I, chủ tịch Ủy ban Khoa học của đất nước JOI, dự định xây dựng và duy trì các cáp liên lạc hai chiều giữa các thị trấn. Ban đầu chưa có cáp nào. Ông I có kế hoạch cho \(C\) ngày. Kế hoạch của ngày thứ \(i+1\), với \(0 \le i \le C-1\), được mô tả bởi ba số nguyên \(T_i,X_i,Y_i\):

• Nếu \(T_i=0\), xây một cáp nối thị trấn \(X_i\) và thị trấn \(Y_i\). Đảm bảo vào đầu ngày thứ \(i+1\) chưa có cáp nối hai thị trấn này.
• Nếu \(T_i=1\), tháo cáp nối thị trấn \(X_i\) và thị trấn \(Y_i\). Đảm bảo vào đầu ngày thứ \(i+1\) có cáp nối hai thị trấn này.

Ở đất nước JOI thường xảy ra sạt lở vách núi. Nếu sạt lở xảy ra giữa thị trấn \(x\) và thị trấn \(x+1\), với \(0 \le x \le N-2\), mọi cáp nối một thị trấn có số hiệu không lớn hơn \(x\) với một thị trấn có số hiệu không nhỏ hơn \(x+1\) đều không sử dụng được. Khi đó, cần chọn một số thị trấn để lắp trạm gốc, sao cho từ bất kỳ thị trấn nào cũng có thể đến được một trạm gốc bằng các cáp còn sử dụng được.

Ông I có \(Q\) câu hỏi. Câu hỏi thứ \(j+1\) được mô tả bởi hai số nguyên \(W_j,P_j\): nếu sạt lở xảy ra giữa thị trấn \(P_j\) và thị trấn \(P_j+1\) vào cuối ngày thứ \(W_j+1\), thì cần lắp ít nhất bao nhiêu trạm gốc?

Hãy viết chương trình trả lời các câu hỏi này. Mỗi câu hỏi xét riêng một tình huống sạt lở đối với mạng cáp sau các thao tác xây hoặc tháo cáp đến ngày được hỏi; các tình huống sạt lở không làm thay đổi kế hoạch cho những câu hỏi khác.

Cài đặt

Với C++, khai báo #include "collapse.h" và cài đặt hàm:

std::vector<int> simulateCollapse(
    int N,
    std::vector<int> T,
    std::vector<int> X,
    std::vector<int> Y,
    std::vector<int> W,
    std::vector<int> P
);

• N là số thị trấn.
• T, X, Y là ba mảng độ dài \(C\). Với \(0 \le i \le C-1\), T[i], X[i], Y[i] mô tả kế hoạch của ngày thứ \(i+1\).
• W, P là hai mảng độ dài \(Q\). Với \(0 \le j \le Q-1\), W[j], P[j] mô tả câu hỏi thứ \(j+1\).
• Hàm trả về mảng số nguyên D độ dài \(Q\), trong đó D[j] là câu trả lời cho câu hỏi thứ \(j+1\).

Trên LQDOJ, nộp đúng một tệp C++ cài đặt các hàm theo chữ ký trên. Có thể cài đặt thêm các hàm phụ. Chương trình không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc tương tác với bất kỳ tệp nào khác; được phép ghi ra luồng lỗi chuẩn. Gói đính kèm chính thức vẫn được giữ để tham khảo, nhưng trình chấm của bài này chỉ hỗ trợ C++. Thông báo kỳ thi gốc quy định tối đa \(50\) lần nộp cho mỗi bài.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau; chương trình của bạn nhận dữ liệu qua tham số hàm:

• Dòng đầu chứa \(N,C,Q\).
• Dòng thứ \(2+i\) chứa \(T_i,X_i,Y_i\), với \(0 \le i \le C-1\).
• Dòng thứ \(2+C+j\) chứa \(W_j,P_j\), với \(0 \le j \le Q-1\).

Dữ liệu ra

Trình chấm mẫu in mảng do simulateCollapse trả về: dòng thứ \(1+j\) chứa \(D_j\), với \(0 \le j \le Q-1\).

Ràng buộc

• \(2 \le N \le 100000\).
• \(1 \le C \le 100000\); \(1 \le Q \le 100000\).
• Với mọi \(0 \le i \le C-1\): \(T_i \in \{0,1\}\), \(0 \le X_i,Y_i \le N-1\), \(X_i \ne Y_i\).
• Với mọi \(0 \le j \le Q-1\): \(0 \le W_j \le C-1\), \(0 \le P_j \le N-2\).
• Các thao tác xây và tháo cáp luôn hợp lệ như mô tả ở trên.
• Giới hạn thời gian: \(6\) giây. Giới hạn bộ nhớ: \(512\) MB.

Phân nhóm

1. \(5\) điểm: Giới hạn \(N\): \(2 \le N \le 5000\); Giới hạn \(C,Q\): \(1 \le C,Q \le 5000\); Điều kiện bổ sung: Không có.
2. \(30\) điểm: Giới hạn \(N\): \(2 \le N \le 100000\); Giới hạn \(C,Q\): \(1 \le C,Q \le 100000\); Điều kiện bổ sung: Tất cả \(P_j\), với \(0 \le j \le Q-1\), bằng nhau.
3. \(30\) điểm: Giới hạn \(N\): \(2 \le N \le 100000\); Giới hạn \(C,Q\): \(1 \le C,Q \le 100000\); Điều kiện bổ sung: \(T_i=0\) với mọi \(0 \le i \le C-1\).
4. \(35\) điểm: Giới hạn \(N\): \(2 \le N \le 100000\); Giới hạn \(C,Q\): \(1 \le C,Q \le 100000\); Điều kiện bổ sung: Không có.

Ví dụ giao tiếp

Xét \(5\) thị trấn. Ký hiệu \((x,y)\) là cáp nối thị trấn \(x\) và thị trấn \(y\).

Giả sử có bốn cáp \((0,1)\), \((1,3)\), \((2,4)\), \((4,0)\) và sạt lở xảy ra giữa thị trấn \(1\) và thị trấn \(2\). Các cáp \((1,3)\) và \((4,0)\) không sử dụng được, nên chỉ còn cáp \((0,1)\) và \((2,4)\). Có thể lắp trạm gốc ở các thị trấn \(0\), \(2\) và \(3\). Số trạm gốc ít nhất cần lắp là \(3\).

Trong một tình huống khác, giả sử có sáu cáp \((0,1)\), \((0,3)\), \((1,2)\), \((2,4)\), \((4,0)\), \((4,3)\) và sạt lở xảy ra giữa thị trấn \(3\) và thị trấn \(4\). Các cáp \((2,4)\), \((4,0)\) và \((4,3)\) không sử dụng được, nên chỉ còn cáp \((0,1)\), \((0,3)\) và \((1,2)\). Có thể lắp trạm gốc ở thị trấn \(0\) và thị trấn \(4\). Số trạm gốc ít nhất cần lắp là \(2\).

Nguồn

JOI Open 2018 - Collapse, đề tiếng Anh, thông báo cài đặt và gói mã mẫu chính thức. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.