Question - 5
Segment trees are extremely useful. In particular "Lazy Propagation" (i.e. see here, for example) allows one to compute sums over a range in O(lg(n)), and update ranges in O(lg(n)) as well. In this problem you will compute something much harder:
The sum of squares over a range with range updates of 2 types:
1) increment in a range
2) set all numbers the same in a range.
Input
There will be T (T <= 25) test cases in the input file. First line of the input contains two positive integers, N (N <= 100,000) and Q (Q <= 100,000).
The next line contains N integers, each at most 1000. Each of the next Q lines starts with a number, which indicates the type of operation:
2 st nd -- return the sum of the squares of the numbers with indices in [st, nd] {i.e., from st to nd inclusive} (1 <= st <= nd <= N).
1 st nd x -- add "x" to all numbers with indices in [st, nd] (1 <= st <= nd <= N, and -1,000 <= x <= 1,000).
0 st nd x -- set all numbers with indices in [st, nd] to "x" (1 <= st <= nd <= N, and -1,000 <= x <= 1,000).Output
For each test case output the “Case <caseno>:” in the first line and from the second line output the sum of squares for each operation of type 2. Intermediate overflow will not occur with proper use of 64-bit signed integer.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 1Output:
Case 1:
30
7
13
Case 2:
1class Main {
static class TreeNode {
int sum, sq_sum;
TreeNode(int sum, int sq_sum) {
this.sum = sum;
this.sq_sum = sq_sum;
}
}
static class LazyNode {
// type : 0-> shows that no action is needed , 1-> shows that increment is needed,
// 2-> replacement is needed
int type, value;
LazyNode(int type, int value) {
this.type = type;
this.value = value;
}
}
public static void helper(TreeNode[] tree, LazyNode[] lazy, int start, int end, int index) {
if (lazy[index].type == 1) {
tree[index].sq_sum += (lazy[index].value * lazy[index].value * (end - start + 1))
+ (2 * lazy[index].value * tree[index].sum);
tree[index].sum += lazy[index].value * (end - start + 1);
if (start != end) {
lazy[2 * index] = new LazyNode(1, lazy[2 * index].value + lazy[index].value);
lazy[2 * index + 1] = new LazyNode(1, lazy[2 * index + 1].value + lazy[index].value);
}
} else {
tree[index].sq_sum = (end - start + 1) * lazy[index].value * lazy[index].value;
tree[index].sum = (end - start + 1) * lazy[index].value;
if (start != end) {
lazy[2 * index] = new LazyNode(2, lazy[index].value);
lazy[2 * index + 1] = new LazyNode(2, lazy[index].value);
}
}
lazy[index] = new LazyNode(0, 0);
}
// building the lazy tree aswell with its default values
public static void build(int[] arr, TreeNode[] tree, LazyNode[] lazy, int start, int end, int index) {
if (start == end) {
tree[index] = new TreeNode(arr[start], arr[start] * arr[start]);
lazy[index] = new LazyNode(0, 0); // default values
return;
}
int mid = (start + end) / 2;
build(arr, tree, lazy, start, mid, 2 * index);
build(arr, tree, lazy, mid + 1, end, 2 * index + 1);
tree[index] = new TreeNode(tree[2 * index].sum + tree[2 * index + 1].sum,
tree[2 * index].sq_sum + tree[2 * index + 1].sq_sum);
lazy[index] = new LazyNode(0, 0);// default values
}
public static void update(TreeNode[] tree, LazyNode[] lazy, int start, int end, int index, int L, int R, int value,
int type) {
if (lazy[index].type != 0)
helper(tree, lazy, start, end, index);
// no overlap
if (start > R || end < L)
return;
// complete overlap
if (start >= L && end <= R) {
if (type == 1) {
tree[index].sq_sum += 2 * value * tree[index].sum + (value * value * (end - start + 1));
tree[index].sum += value * (end - start + 1);
if (start != end) {
lazy[2 * index] = new LazyNode(1, lazy[2 * index].value + value);
lazy[2 * index + 1] = new LazyNode(1, lazy[2 * index + 1].value + value);
}
} else {
tree[index].sq_sum = value * value * (end - start + 1);
tree[index].sum = value * (end - start + 1);
if (start != end) {
lazy[2 * index] = new LazyNode(2, value);
lazy[2 * index + 1] = new LazyNode(2, value);
}
}
return;
}
// partial overlap
int mid = (start + end) / 2;
update(tree, lazy, start, mid, 2 * index, L, R, value, type);
update(tree, lazy, mid + 1, end, 2 * index + 1, L, R, value, type);
tree[index].sq_sum = tree[2 * index].sq_sum + tree[2 * index + 1].sq_sum;
tree[index].sum = tree[2 * index].sum + tree[2 * index + 1].sum;
}
public static TreeNode printQuery(TreeNode[] tree, LazyNode[] lazy, int start, int end, int index, int l, int r) {
// no overlap
if (start > r || end < l)
return new TreeNode(0, 0);
if (lazy[index].type != 0)
helper(tree, lazy, start, end, index);
// complete overlap
if (start >= l && end <= r)
return tree[index];
// partial overlap
int mid = (start + end) / 2;
TreeNode leftAns = printQuery(tree, lazy, start, mid, 2 * index, l, r);
TreeNode rightAns = printQuery(tree, lazy, mid + 1, end, 2 * index + 1, l, r);
return new TreeNode(leftAns.sum + rightAns.sum, leftAns.sq_sum + rightAns.sq_sum);
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int t = s.nextInt();
for (int j = 1; j <= t; j++) {
int n = s.nextInt(), q = s.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = s.nextInt();
TreeNode[] tree = new TreeNode[4 * n];
LazyNode[] lazy = new LazyNode[4 * n];
build(arr, tree, lazy, 0, n - 1, 1);
System.out.println("Case " + j + ":");
while (q-- > 0) {
int type = s.nextInt();
int st = s.nextInt() - 1;
int nd = s.nextInt() - 1;
if (type == 2)
System.out.println(printQuery(tree, lazy, 0, n - 1, 1, st, nd).sq_sum);
else {
int x = s.nextInt();
if (type == 1)
update(tree, lazy, 0, n - 1, 1, st, nd, x, 1);
else
update(tree, lazy, 0, n - 1, 1, st, nd, x, 2);
}
}
}
s.close();
}
}Last updated