Hello Codeforces,↵
↵
I was recently thinking of the following problem:↵
Given an NxN 2D array, you are given some queries to find the maximum value of a cell in the array, with online updates. ↵
↵
More formally,↵
There are two types of updates.↵
↵
1. Given integers i and k, add x to every cell a[i][j], for j in some range [1,k]. ↵
2. Given integers i and k, add x to every cell a[j][i], for j in some range [1,k]. ↵
↵
And the query is, find the current maximum cell in the whole 2D array.↵
↵
N is around 10^5, and I was wondering if there is a way to solve this with a sublinear query and update complexity.↵
↵
I am aware that RMQ with 2D segment tree and 2D range updates is not possible in sublinear time, but this problem is not as general as the updates are only on rows or columns, not entire submatrices. Similarly, the queries are on the entire grid instead of specific submatrices.↵
↵
Some of my own ideas I had:↵
↵
If we could ignore the 2nd type of query, we could just have each row having its own segment tree, and just do regular lazy range updates. To get the current maximum of the 2D grid, we could keep a multiset, where each element represents the maximum value in a respective row, and after a query on a row, we could just update its occurrence in the multiset.
↵
I was recently thinking of the following problem:↵
Given an NxN 2D array, you are given some queries to find the maximum value of a cell in the array, with online updates. ↵
↵
More formally,↵
There are two types of updates.↵
↵
1. Given integers i and k, add x to every cell a[i][j], for j in some range [1,k]. ↵
2. Given integers i and k, add x to every cell a[j][i], for j in some range [1,k]. ↵
↵
And the query is, find the current maximum cell in the whole 2D array.↵
↵
N is around 10^5, and I was wondering if there is a way to solve this with a sublinear query and update complexity.↵
↵
I am aware that RMQ with 2D segment tree and 2D range updates is not possible in sublinear time, but this problem is not as general as the updates are only on rows or columns, not entire submatrices. Similarly, the queries are on the entire grid instead of specific submatrices.↵
↵
Some of my own ideas I had:↵
↵
If we could ignore the 2nd type of query, we could just have each row having its own segment tree, and just do regular lazy range updates. To get the current maximum of the 2D grid, we could keep a multiset, where each element represents the maximum value in a respective row, and after a query on a row, we could just update its occurrence in the multiset.
