Kiểm thử - HackMD

--- tags: Propose for Bedao --- # Kiểm thử ## Statement Trong thiết kế hệ thông, kiểm thử là một giai đoạn vô cùng quan trọng. Quân đang thiết kế một máy theo nguyên lí máy Turing, tức là thực hiện các thao tác trên một băng ghi bộ nhớ; và máy của anh đang trong giai đoạn kiểm thử. Băng ghi bộ nhớ của Quân có thể coi là một dãy $n$ bit được đánh số $1$ đến $n$ từ trái sang phải, mỗi bit ban đầu có một trạng thái xác định. Để kiểm tra máy, người ta lần lượt thực hiện các truy vấn thuộc trong hai loại: - `1 l r`: Chuyển trạng thái các bit từ bit thứ `l` đến bit thứ `r` (`0` thành `1` và `1` thành `0`) - `2 x y z t`: Kiểm tra xem hai dãy nhị phân con từ `x` đến `y` và từ `z` đến `t` có giống nhau không Ví dụ: Với dãy nhị phân `010001010110`: - Hai dãy nhị phân từ $1$ đến $3$ và từ $7$ đến $9$ bằng nhau (Cùng bằng `010`) - Hay dãy nhị phân từ $4$ đến $6$ và từ $10$ đến $12$ khác nhau Yêu cầu: Bạn hãy giúp Quân kiểm tra máy của anh bằng cách trả lời các truy vấn loại `2` nhé ## Input - Dòng đầu tiên chứa xâu nhị phân $S$ $(|S|\le 10^5)$ mô tả trạng thái băng nhớ ban đầu - Dòng thứ hai chứa số nguyên dương $q$ $(q\le 10^5)$ là số truy vấn, $q$ dòng tiếp mỗi dòng chứa một truy vấn thuộc một trong hai dạng: - `1 l r` $(1\le l\le r \le n)$ - `2 x y z t`: $(1\le x\le y\le n, 1\le z\le t\le n)$ ## Output - In ra nhiều dòng theo thứ tự là đáp án của truy vấn loại `2` tương ứng: Nếu hai dãy là giống nhau, in ra `YES`, ngược lại in ra `NO`. ## Example | Input | Output | | --------- | ------ | | | | | 01101011 5 1 3 4 2 2 3 5 6 1 1 8 2 1 5 2 7 2 1 2 7 8 |YES NO NO | ## Scoring - Có 15% số điểm của bài với $|S|,q\le 1000$ - Có 25% số điểm khác với $r-l\le 1000$ trong mọi truy vấn loại 1 - Còn lại không có điều kiện gì thêm # Solution Đặt $P_i=\sum_{j=1}^iS_j\times 10^{j}$ $S[x..y] = S[z..t]\Leftrightarrow \frac{P_y-P_{x-1}}{10^x}=\frac{P_t-P_{z - 1}}{10^z}$ $\Rightarrow$ Ta sử dụng kĩ thuật Hashing. Việc cần làm là duy trì $P$ trên; ta dùng một cây phân đoạn (Segment Tree), mỗi node gồm 2 giá trị: - $sum=\sum S_j\times 10^j$ - $psum = \sum (1-S_j)\times 10^j$ Việc đảo giá trị một đoạn chính là thao tác $swap(sum, psum)$ Kết hợp với kĩ thuật lazy, ta có được lời giải cho bài toán