#1488. BIENDOI - Biến đổi

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

NGUỒN: ĐỀ THI CHỌN HỌC SINH GIỎI THÀNH PHỐ BẢNG A VÀ CHỌN ĐỘI TUYỂN DỰ THI HỌC SINH GIỎI QUỐC GIA (TỈNH HẢI PHÒNG)
NĂM HỌC 2021 - 2022

Cho bảng gồm n dòng m cột (các dòng đánh số từ 1 đến n , các cột đánh số từ 1 đến m ). Ô giao giữa dòng i và cột j gọi là ô (i;j) có giá trị A[i][j]\ (1≤i≤n;1≤j≤m) . Ban đầu giá trị trên tất cả các ô bằng không.

Q thao tác (đánh số từ 1 đến Q ), mỗi thao tác là một trong 4 loại sau:

  • 1\ i\ j : Nếu A[i][j]=0 thì A[i][j]=1 ;
  • 2\ i\ j : Nếu A[i][j]=1 thì A[i][j]=0 ;
  • 3\ i : A[i][j]=1-A[i][j], ∀j thỏa mãn 1≤j≤m ;
  • 4\ k : Đưa bảng về trạng thái sau thao tác thứ k . Nếu k=0 thì bảng sẽ trở lại trạng thái ban đầu, tức là A[i][j]=0 ∀i,j thỏa mãn 1≤i≤n,1≤j≤m .

Sau mỗi thao tác, hãy cho biết có bao nhiêu ô (i;j) A[i][j]=1 .

Dữ liệu:

  • Dòng đầu gồm ba số nguyên n,m,Q\ (1≤n,m≤10^3,1≤Q≤10^5) là kích thước của bảng và số thao tác;
  • Q dòng tiếp theo là các thao tác theo thứ tự đã được mô tả ở trên. Dữ liệu đảm bảo rằng mọi thao tác đều hợp lệ.

Kết quả:

  • Ghi ra Q dòng, dòng thứ t\ (1≤t≤Q) ghi số lượng ô (i;j) A[i][j]=1 sau thao tác thứ t .

Ví dụ:

Dữ liệu:

4 2 6
3 2
2 2 2
3 3
3 2
2 2 2
3 2

Kết quả:

2
1
3
3
2
4

Giải thích:

Bảng thu được sau từng thao tác như sau:

\left[ {\begin{array}{*{20}{c}} 0&0\\ 0&0\\ 0&0\\ 0&0 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&0\\ 1&1\\ 0&0\\ 0&0 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&0\\ 1&0\\ 0&0\\ 0&0 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&0\\ 1&0\\ 1&1\\ 0&0 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&0\\ 0&1\\ 1&1\\ 0&0 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&0\\ 0&0\\ 1&1\\ 0&0 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&0\\ 1&1\\ 1&1\\ 0&0 \end{array}} \right]

Dữ liệu:

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

Kết quả:

3
4
3
6
5

Giải thích:

Bảng thu được sau từng thao tác như sau:

\left[ {\begin{array}{*{20}{c}} 0&0&0\\ 0&0&0\\ 0&0&0 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&0&0\\ 1&1&1\\ 0&0&0 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&1&0\\ 1&1&1\\ 0&0&0 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&0&0\\ 1&1&1\\ 0&0&0 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&0&0\\ 1&1&1\\ 1&1&1 \end{array}} \right] \Rightarrow \left[ {\begin{array}{*{20}{c}} 0&0&0\\ 1&1&1\\ 1&0&1 \end{array}} \right]

Giới hạn:

  • Subtask \#1: ( 40\% số điểm): n,m,Q≤100 ;
  • Subtask \#2: ( 20\% số điểm): Dữ liệu không có thao tác loại 4 ;
  • Subtask \#3: ( 40\% số điểm): Không có ràng buộc bổ sung.