SPOJ - SEGSQRSS
Source: SPOJ - SEGSQRSS
Tags: Data Structures
Problem:
Cho một dãy gồm N số nguyên và Q truy vấn có dạng:
2 l r: In ra tổng bình phương các phần tử trong [l, r].
1 l r x: Cộng x vào các phần tử trong [l, r].
0 l r x: Đổi tất cả các phần tử trong [l, r] thành x.
Trong input sẽ có T test cases, với mỗi test case, in ra "Case <số thứ tự của test>:" và theo sau là các dòng chứa đáp án tương ứng với các truy vấn 2 l r trong test.
T ≤ 25. N, Q ≤ 1e5.
Các số trong mảng ban đầu không vượt quá 1000.
-1000 ≤ x ≤ 1000.
Ví dụ:
Input:
2
4 5
1 2 3 4
2 1 4
0 3 4 1
2 1 4
1 3 4 1
2 1 4
1 1
1
2 1 1
Output:
Case 1:
30
7
13
Case 2:
1
Solution:
Đối với việc update của truy vấn dạng 0 thì quá đơn giản rồi, còn đối với truy vấn dạng 1, ta sẽ khai triển như sau:
Gọi 1 phần tử trong đoạn là a, bình phương của phần tử này là a^2. Sau khi cộng x vào phần tử này, ta có bình phương của phần tử đó lúc này là (a + x)^2 = a^2 + 2ax + x^2 (hằng đẳng thức đáng nhớ số 1, SGK Toán 8, NXB Giáo dục Việt Nam), vậy lúc này, tổng bình phương các phần tử trong đoạn sẽ là A[l]^2 + A[l + 1]^2 + ... + A[r]^2 + 2x(A[l] + A[l + 1] + ... + A[r]) + (r - l + 1) x^2. Trong đó, A[l]^2 + A[l + 1]^2 + ... + A[r]^2 chính là đáp án lúc chưa cập nhật, (r - l + 1) x^2 ta có thể tính dễ dàng, còn tổng của đoạn ta chỉ cần thêm một biến lưu tổng (không có bình phương) của mỗi đoạn là xong. Các giá trị còn lại có thể cập nhật dễ dàng, và tất nhiên chúng ta phải sử dụng Lazy Propagation để cập nhật đoạn thuận tiện nhất.
Độ phức tạp: O(T * (N + Q) * logN)
Code: (bình thường mặc dù trên lý thuyết thì ta hay để mảng IT là 4N nhưng mà bản thân mình thì hay để 5N cho chắc ăn thôi, cơ mà trong bài này, mình để 5N là 5e5 thì lại không đủ, phải để tới 1e6 lận :/ mình cũng không hiểu tại sao)
#include <iostream>
using namespace std;
struct IT_node {
long long sumsqr, sum, lazytype, lazyval;
} IT[1000000];
long long sqr(long long x) {
return x * x;
}
void lazy_down(int k, int l, int r) {
int m = (l + r) / 2;
if (IT[k].lazytype == 0)
IT[2 * k].lazytype = IT[2 * k + 1].lazytype = 0,
IT[2 * k].lazyval = IT[2 * k + 1].lazyval = IT[k].lazyval,
IT[2 * k].sumsqr = (m - l + 1) * sqr(IT[k].lazyval),
IT[2 * k].sum = (m - l + 1) * IT[k].lazyval,
IT[2 * k + 1].sumsqr = (r - m) * sqr(IT[k].lazyval),
IT[2 * k + 1].sum = (r - m) * IT[k].lazyval;
else if (IT[k].lazytype == 1)
IT[2 * k].lazytype = IT[2 * k + 1].lazytype = 1,
IT[2 * k].lazyval = IT[2 * k + 1].lazyval = IT[k].lazyval,
IT[2 * k].sumsqr += 2 * IT[2 * k].sum * IT[k].lazyval + (m - l + 1) * sqr(IT[k].lazyval),
IT[2 * k].sum += (m - l + 1) * IT[k].lazyval,
IT[2 * k + 1].sumsqr += 2 * IT[2 * k + 1].sum * IT[k].lazyval + (r - m) * sqr(IT[k].lazyval),
IT[2 * k + 1].sum += (r - m) * IT[k].lazyval;
IT[k].lazytype = -1;
}
void update(int a, int b, int x, int t, int k, int l, int r) {
if (b < l || r < a) return;
int m = (l + r) / 2; lazy_down(k, l, r);
if (a <= l && r <= b) {
IT[k].lazytype = t; IT[k].lazyval = x;
if (!t)
IT[k].sumsqr = (r - l + 1) * sqr(x),
IT[k].sum = (r - l + 1) * x;
else
IT[k].sumsqr += 2 * IT[k].sum * x + (r - l + 1) * sqr(x),
IT[k].sum += (r - l + 1) * x;
}
else
update(a, b, x, t, 2 * k, l, m),
update(a, b, x, t, 2 * k + 1, m + 1, r),
IT[k].sumsqr = IT[2 * k].sumsqr + IT[2 * k + 1].sumsqr,
IT[k].sum = IT[2 * k].sum + IT[2 * k + 1].sum;
}
long long get(int a, int b, int k, int l, int r) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) return IT[k].sumsqr;
int m = (l + r) / 2; lazy_down(k, l, r);
return get(a, b, 2 * k, l, m) + get(a, b, 2 * k + 1, m + 1, r);
}
int main() {
int t; cin >> t;
for (int test = 1; test <= t; ++test) {
cout << "Case " << test << ":\n";
int n, q; cin >> n >> q;
for (int i = 1, x; i <= n; ++i)
cin >> x, update(i, i, x, 0, 1, 1, n);
while (q--) {
int type; cin >> type;
if (type == 2) {
int l, r; cin >> l >> r;
cout << get(l, r, 1, 1, n) << '\n';
}
else {
int l, r, x; cin >> l >> r >> x;
update(l, r, x, type, 1, 1, n);
}
}
}
}
Tags: Data Structures
Problem:
Cho một dãy gồm N số nguyên và Q truy vấn có dạng:
2 l r: In ra tổng bình phương các phần tử trong [l, r].
1 l r x: Cộng x vào các phần tử trong [l, r].
0 l r x: Đổi tất cả các phần tử trong [l, r] thành x.
Trong input sẽ có T test cases, với mỗi test case, in ra "Case <số thứ tự của test>:" và theo sau là các dòng chứa đáp án tương ứng với các truy vấn 2 l r trong test.
T ≤ 25. N, Q ≤ 1e5.
Các số trong mảng ban đầu không vượt quá 1000.
-1000 ≤ x ≤ 1000.
Ví dụ:
Input:
2
4 5
1 2 3 4
2 1 4
0 3 4 1
2 1 4
1 3 4 1
2 1 4
1 1
1
2 1 1
Output:
Case 1:
30
7
13
Case 2:
1
Solution:
Đối với việc update của truy vấn dạng 0 thì quá đơn giản rồi, còn đối với truy vấn dạng 1, ta sẽ khai triển như sau:
Gọi 1 phần tử trong đoạn là a, bình phương của phần tử này là a^2. Sau khi cộng x vào phần tử này, ta có bình phương của phần tử đó lúc này là (a + x)^2 = a^2 + 2ax + x^2 (hằng đẳng thức đáng nhớ số 1, SGK Toán 8, NXB Giáo dục Việt Nam), vậy lúc này, tổng bình phương các phần tử trong đoạn sẽ là A[l]^2 + A[l + 1]^2 + ... + A[r]^2 + 2x(A[l] + A[l + 1] + ... + A[r]) + (r - l + 1) x^2. Trong đó, A[l]^2 + A[l + 1]^2 + ... + A[r]^2 chính là đáp án lúc chưa cập nhật, (r - l + 1) x^2 ta có thể tính dễ dàng, còn tổng của đoạn ta chỉ cần thêm một biến lưu tổng (không có bình phương) của mỗi đoạn là xong. Các giá trị còn lại có thể cập nhật dễ dàng, và tất nhiên chúng ta phải sử dụng Lazy Propagation để cập nhật đoạn thuận tiện nhất.
Độ phức tạp: O(T * (N + Q) * logN)
Code: (bình thường mặc dù trên lý thuyết thì ta hay để mảng IT là 4N nhưng mà bản thân mình thì hay để 5N cho chắc ăn thôi, cơ mà trong bài này, mình để 5N là 5e5 thì lại không đủ, phải để tới 1e6 lận :/ mình cũng không hiểu tại sao)
#include <iostream>
using namespace std;
struct IT_node {
long long sumsqr, sum, lazytype, lazyval;
} IT[1000000];
long long sqr(long long x) {
return x * x;
}
void lazy_down(int k, int l, int r) {
int m = (l + r) / 2;
if (IT[k].lazytype == 0)
IT[2 * k].lazytype = IT[2 * k + 1].lazytype = 0,
IT[2 * k].lazyval = IT[2 * k + 1].lazyval = IT[k].lazyval,
IT[2 * k].sumsqr = (m - l + 1) * sqr(IT[k].lazyval),
IT[2 * k].sum = (m - l + 1) * IT[k].lazyval,
IT[2 * k + 1].sumsqr = (r - m) * sqr(IT[k].lazyval),
IT[2 * k + 1].sum = (r - m) * IT[k].lazyval;
else if (IT[k].lazytype == 1)
IT[2 * k].lazytype = IT[2 * k + 1].lazytype = 1,
IT[2 * k].lazyval = IT[2 * k + 1].lazyval = IT[k].lazyval,
IT[2 * k].sumsqr += 2 * IT[2 * k].sum * IT[k].lazyval + (m - l + 1) * sqr(IT[k].lazyval),
IT[2 * k].sum += (m - l + 1) * IT[k].lazyval,
IT[2 * k + 1].sumsqr += 2 * IT[2 * k + 1].sum * IT[k].lazyval + (r - m) * sqr(IT[k].lazyval),
IT[2 * k + 1].sum += (r - m) * IT[k].lazyval;
IT[k].lazytype = -1;
}
void update(int a, int b, int x, int t, int k, int l, int r) {
if (b < l || r < a) return;
int m = (l + r) / 2; lazy_down(k, l, r);
if (a <= l && r <= b) {
IT[k].lazytype = t; IT[k].lazyval = x;
if (!t)
IT[k].sumsqr = (r - l + 1) * sqr(x),
IT[k].sum = (r - l + 1) * x;
else
IT[k].sumsqr += 2 * IT[k].sum * x + (r - l + 1) * sqr(x),
IT[k].sum += (r - l + 1) * x;
}
else
update(a, b, x, t, 2 * k, l, m),
update(a, b, x, t, 2 * k + 1, m + 1, r),
IT[k].sumsqr = IT[2 * k].sumsqr + IT[2 * k + 1].sumsqr,
IT[k].sum = IT[2 * k].sum + IT[2 * k + 1].sum;
}
long long get(int a, int b, int k, int l, int r) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) return IT[k].sumsqr;
int m = (l + r) / 2; lazy_down(k, l, r);
return get(a, b, 2 * k, l, m) + get(a, b, 2 * k + 1, m + 1, r);
}
int main() {
int t; cin >> t;
for (int test = 1; test <= t; ++test) {
cout << "Case " << test << ":\n";
int n, q; cin >> n >> q;
for (int i = 1, x; i <= n; ++i)
cin >> x, update(i, i, x, 0, 1, 1, n);
while (q--) {
int type; cin >> type;
if (type == 2) {
int l, r; cin >> l >> r;
cout << get(l, r, 1, 1, n) << '\n';
}
else {
int l, r, x; cin >> l >> r >> x;
update(l, r, x, type, 1, 1, n);
}
}
}
}
Nhận xét
Đăng nhận xét