Thay Thế Giá Trị

Xem PDF
Tác giả:
algorit , bin9638
Dạng bài
Điểm: 250 (p) Thời gian: 1.2s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Hôm nay, những nhân vật thông minh nhất vũ trụ anime như \(Conan, Kira, L, Sakamoto, Armin, ...\) đang tranh giải "Bộ não vàng" do algorit tổ chức. bin9638 cũng là một trong những người tham gia cuộc thi này. Để chiến thắng cuộc thi thì phải giải được bài toán mà algorit đưa ra như sau:

Cho một dãy số nguyên dương \(A_1,A_2,...,A_N\) gồm \(N\) phần tử .

Cho \(Q\) thao tác , mỗi thao tác gồm 2 số nguyên dương \(x\) và \(y\) , thao tác này làm tất cả phần tử đang mang giá trị \(x\) trong mảng chuyển thành giá trị \(y\). Với mỗi thao tác hãy tính tổng tất cả các phần tử của mảng

bin9638 rất muốn trở thành nhân vật thông minh nhất vũ trụ anime nhưng vì những đối thủ của anh quá giỏi nên đành nhờ các bạn giúp đỡ. Hãy giúp cậu ấy nhé !

  • Yêu cầu : Sau mỗi thao tác hãy tính lại tổng tất cả các phần tử của mảng .

Input

  • Dòng đầu tiên gồm 2 số nguyên dương \(N\) và \(Q\) \(. (N , Q \le 10^6)\)
  • Dòng tiếp theo gồm các số nguyên dương \(A_1,A_2,...,A_N\) \(. (A_i \le 10^{12})\)
  • \(Q\) dòng tiếp theo gồm 2 số nguyên dương \(x , y\) \(. (x,y \le 10^{12})\)

Output

  • Gồm \(Q\) dòng , mỗi dòng là tổng giá trị của mảng .

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N,Q \le 10^3 , A_i \le 10^9.\)*
  • Subtask \(2\) (\(30\%\) số điểm): \(N,Q \le 10^5 , A_i \le 10^6.\)*
  • Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm .*

Example

Test 1

Input 
5 3
1 2 3 5 4
1 2
2 3
3 4
Output 
16
18
21
Note

Giải thích :

  • Với thao tác đầu tiên mảng biến đổi thành \([2,2,3,5,4].\)
  • Với thao tác thứ 2 , mảng biến đổi thành \([3,3,3,5,4].\)
  • Với thao tác thứ 3 , mảng biến đổi thành \([4,4,4,5,4].\)

Bình luận


  • 2
    tuanha2    12:23 p.m. 14 Tháng 9, 2020

    Xin gợi ý hoặc solution cho bài này trên test 15 ạ.Triệu hồi @SPyofgame giúp em với ạ


    • 13
      stupidloc4    2:18 p.m. 14 Tháng 9, 2020 ← đã chỉnh sửa

      với bài này ta cần 1 mảng đếm để lưu số lần a[i] được lặp lại.
      gọi sum là tổng các phần tử của mảng a.
      với mỗi q, ta trừ sum đi (dem[x] nhân x) và cộng vào sum (dem[x] nhân y);
      sau đó cho dem[y] tăng lên dem[x];
      và gán dem[x]=0;
      với trường hợp x!=y;

      còn trường hợp khi x=y thì dem[x] giữ nguyên nên sum không thay đổi nên chỉ cần cout sum;

      p/s: vì a[i] <=1e12 nên để đếm số a[i] thì dùng map<long long,int>dem;


      • 2
        todonghai2k7    10:11 p.m. 16 Tháng 9, 2020 ← chỉnh sửa 3

        Thêm 1 đk để AC nữa là

        ios_base::sync_with_stdio(0);

        cin.tie(NULL);

        cout.tie(NULL);

        Nếu ko thêm 3 câu lệnh trên thì ăn 30 / 50
        còn thêm thì 50 / 50 :))))


        • 1
          VoBaThongL921    8:56 p.m. 30 Tháng 9, 2021 ← đã chỉnh sửa

          Fast io quan trọng đến như thế sao ?
          Fast io quan trọng đến như thế à ?

          • à nó quan trọng thiệt 🙂 ko có thì 30/50

          • 1
            nguyendanghau2006    10:55 p.m. 2 Tháng 1, 2022

            sao tui cũng fast io các kiểu rùi mà vẫn 30/50 :((


            • 0
              VoBaThongL921    7:21 a.m. 3 Tháng 1, 2022

              thay endl bằng "\n" là được á ông 😃


              • 1
                minhtuanitk20    3:55 p.m. 9 Tháng 1, 2022

                define endl "\n"


                • 1
                  nguyendanghau2006    7:51 a.m. 3 Tháng 1, 2022 ← đã chỉnh sửa

                  :o, ảo rứa lun
                  -> chừ tui mới biết, cảm ơn ông nha


          • 0
            Lê_Gia_Khánh    6:57 p.m. 14 Tháng 9, 2020

            Thì ra là dùng map hèn gì rte 😢


            • 0
              algorit    10:23 a.m. 2 Tháng 10, 2020

              Lê_Gia_Khánh rời rạc cũng AC nhé em


          • 0
            N7hoatt    6:50 p.m. 14 Tháng 9, 2020

            thế mà mik lm phức tạp kết hợp thêm set lmao :))

          1 bình luận nữa