Matrix Electron
Xem dạng PDF
Nguồn đề: CLB GTLT FITHOU, mọi sự sao chép yêu cầu thêm đường dẫn tới bài tập, xin chân thành cảm ơn.
Tại một thành phố Z có một hệ thống điện có thể mô tả như một ma trận có n hàng và m cột. Mỗi một ô trong ma trận là một viên năng lượng tích điện, viên năng lượng có thể tích điện dương (1), tích điện âm(-1) , hoặc không tích điện(0).
Đạt là một kĩ sư điện tài năng mới du học về từ Nhật Bản, đạt thực hiện nối hai viên năng lượng tại hai ô (x1,y1) (x2,y2) với nhau, hai viên sau khi nối lại với nhau sẽ có cùng điện tích ban đầu nếu điện tích của hai viên giống nhau, nếu khác thì sẽ theo quy luật sau :
Gọi dt1 là điện tích của viên năng lượng tại ô (x1,y1), dt2 là điện tích của viên năng lượng tại ô (x2,y2), dt sẽ là điện tích của hai viên năng lượng sau khi Đạt nối chúng lại với nhau.
- dt1 = 1, dt2 = 0 => dt = 1
- dt1 = 0, dt2 = 1 => dt = 1
- dt1 = -1, dt2 = 0 => dt = -1
- dt1 = 0, dt2 = -1 => dt = -1
- dt1 = 1, dt2 = -1 => dt = 0
- dt1 = -1, dt2 = 1 => dt = 0
Ngoài ra sau khi nối hai viên năng lượng lại với nhau chúng sẽ được tính là một viên thống nhất, và luôn luôn có cùng điện tích với nhau, nếu điện tích của viên năng lượng thứ nhất thay đổi, điện tích viên năng lượng thứ hai cũng sẽ thay đổi theo và ngược lại
Thi thoảng, sau khi nối vài viên Đạt muốn kiểm tra điện tích hiện tại của một viên bất kì, hãy giúp Đạt kiểm tra.
Input
Dòng đầu tiên chứa hai số nguyên n, m - số dòng và cột của ma trận ~(1 \le n,m \le 10^3 )~
n dòng tiếp theo, mỗi dòng thứ i sẽ có m số nguyên, số nguyên thứ j cho biết điện tích ban đầu của viên năng lượng tại ô (i,j) (điện tích dương: 1, điện tích âm: -1, không có điện tích: 0)
Dòng tiếp theo chứa một số nguyên q số lượng thao tác của đạt,
q dòng tiếp theo mỗi dòng miêu tả một thao tác, có 2 loại thao tác : ~(1 \le q \le 10^5 )~
Thao tác loại 1 gồm 3 số nguyên:
- type, x, y với type = 1, đạt sẽ kiểm tra xem điện tích hiện tại của viên năng lượng tại ô (x,y) là gì.
- ~(1 \le x \le n )~ , ~(1 \le y \le m )~
Thao tác loại 2 gồm 5 số nguyên:
- type, x1, y1, x2, y2 với type = 2, đạt sẽ nối hai viên năng lượng (x1,y1) và (x2,y2) lại với nhau.
- ~(1 \le x1,x2 \le n )~ , ~(1 \le y1,y2 \le m )~
Output
Với mỗi thao tác loại 1 hãy in ra điện tích hiện tại của viên năng lượng tại (x,y) trên 1 dòng.
Sample Input 1
5 5
0 0 0 0 1
0 0 0 0 0
0 1 -1 0 0
0 0 0 0 0
1 0 0 0 -1
9
2 1 1 1 2
2 1 2 1 3
2 1 1 1 5
1 1 2
2 5 2 5 5
2 5 2 5 3
1 5 2
2 1 2 5 2
1 1 1
Sample Output 1
1
-1
0
20% điểm tương ứng với ~(1 \le n,m \le 50 )~, ~(1 \le q \le 100 )~
80% điểm tương ứng với ~(1 \le n,m \le 1000 )~, ~(1 \le q \le 10^5 )~
Bình luận
Chỉ như một cuộc dạo chơi 🐧
1 buổi đi dạo trong rừng dsa :)
vấn đề này mình nghĩ có thể sử dụng DSU thật ngu ngốc khi mình không làm nó ngay từ đầu.