Truy Vấn Chẵn Lẻ
Xem PDF
Điểm:
600
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn được cho một mảng \(a\) có \(n\) phần tử. Bạn phải xử lí \(Q\) truy vấn, mỗi truy vấn thuộc một trong hai dạng:
1 x: Tăng tất cả các phần tử trong mảng đang có giá trị chẵn \(x\) đơn vị.2 x: Tăng tất cả các phần tử trong mảng đang có giá trị lẻ \(x\) đơn vị.
Chú ý rằng, trong các truy vấn, chúng ta xét giá trị của \(a_{i}\), chứ không xét chỉ số.
Yêu cầu: Đưa ra tổng của mảng \(a\) sau mỗi truy vấn?
Input
- Dòng thứ nhất chứa hai số nguyên dương \(n, Q\) (\(n, Q \le 10^5\)).
- Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2},..., a_{n}\) (\(a_{i} \le 10^6\)).
- \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn như mô tả ở trên (\(1 \le x \le 10^4\)).
Output
- Đưa ra \(Q\) số nguyên trên \(Q\) dòng, dòng thứ \(i\) chứa một số nguyên duy nhất là tổng của mảng sau khi thực hiện truy vấn thứ \(i\).
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(Q \le 10\).
- Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.
Test 1
Input
1 2
2
1 1
2 1Output
3
4Note
Ở test trên, ban đầu mảng \(a\) có \(1\) giá trị chẵn có giá trị là \({2}\).
- Sau khi thực hiện truy vấn thứ \(1\), mảng \(a\) trở thành \({3}\). Khi đó, tổng của mảng \(a\) có giá trị là \(3\).
- Sau khi thực hiện truy vấn thứ \(2\), mảng \(a\) trở thành \({4}\). Khi đó, tổng của mảng \(a\) có giá trị là \(4\).
Bình luận
Giải:
Đặt \(e\) là số phần tử chẵn của mảng ban đầu, \(o\) là số phần tử lẻ của mảng ban đầu, và \(s\) là tổng các phần tử của mảng ban đầu.
Trong mỗi truy vấn:
1 x:Tăng \(s\) lên \(x \times e\) đơn vị và in ra \(s\).
Nếu \(x\) lẻ thì đặt \(e = 0\) và \(o =\) độ dài của mảng.
2 x:Tăng \(s\) lên \(x \times o\) đơn vị và in ra \(s\).
Nếu \(x\) lẻ thì đặt \(o = 0\) và \(e =\) độ dài của mảng.
Mn người có thể tham khảo code của mình :
include <bits/stdc++.h>
using namespace std;
define ll long long
ll sum=0,demchan,demle;
int main() {
ios_base::sync_with_stdio(0);
cin.tie();cout.tie();
int n,q,x;
cin>>n>>q;
for(int i=1;i<=n;i++) {
cin>>x;
if(x%2==0) {
demchan++;
}
else {
demle++;
}
sum+=x;
}
while(q--) {
int a,b;
cin>>a>>b;
if(a==1) {
sum=sum+(1lldemchanb);
cout<<sum<<endl;
if(b%2==1) {
demle=demle+demchan;
demchan=0;
}
}
else if(a==2) {
sum=sum+(1lldemleb);
cout<<sum<<endl;
if(b%2==1) {
demchan=demle+demchan;
demle=0;
}
}
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.