Search an Increasing Matrix
National Olympiad — National round (2016 season)
Submission name: MatrixSearch.cpp
Problem summary
Maintain a matrix strictly increasing along every row and column. Support membership queries and positive increments to every cell at or below row R and at or right of column C.
Input
N M; matrix; Q; operations 1 X or 2 R C Y.
Output
Y or N for each membership query.
Constraints
N,M ≤ 1000; Q ≤ 20000; initial values ≤ 10^9; query X ≤ 2·10^9; 1 ≤ Y ≤ 50000.
Worked example
An independently prepared example for this explanation.
Input
3 4 11 13 14 17 13 15 19 21 18 20 23 42 9 1 42 1 27 2 2 2 4 1 27 2 1 3 7 1 20 1 32 1 19 1 42
Output
Y N Y N Y Y N
Solution analysis
- Positive bottom-right increments preserve strict row and column ordering. Membership can therefore follow the usual staircase from the top-right cell: move left when too large and down when too small.
- Instead of explicitly changing all covered cells, record how update offsets change along this staircase. An increment (R,C,Y) adds Y to enter[R][c] for every c≥C, and to leave[r][C] for every r≥R. When entering row r at column c, add enter[r][c] to the running offset; when leaving column c to the left, subtract leave[r][c].
- The first sample update starts at row 2,column 2 with value 4. The staircase acquires this offset when it crosses into row 2 at any column at least 2, and loses it when it crosses left from column 2. Each cell’s value is its original value plus the running offset; both updates and queries touch only O(N+M) entries.
Why it works
For a single update, a descending-leftward staircase enters its covered bottom-right quadrant at most once and exits it at most once. The enter and leave arrays add and remove exactly Y at these crossings, so the running offset equals that update’s contribution at every visited cell. Linearity proves this for all updates together. Sortedness makes each staircase step discard an entire impossible row or column, giving correct membership.
Watch out. Start each search with the top row’s enter contribution. Subtract the current column’s leave value before moving left. This is a standard-input task, despite its advanced update mechanism.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
// Algorithm: Positive bottom-right increments preserve strict row and column ordering.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<vector<int>>a(n,vector<int>(m)),enter(n,vector<int>(m,0)),leave(n,vector<int>(m,0));
for(auto&row:a){
for(int&value:row){
cin>>value;
}
}
int q;
cin>>q;
while(q-->0){
int type;
cin>>type;
if(type==2){
int row,column,increment;
cin>>row>>column>>increment;
--row;
--column;
for(int c=column;c<m;++c){
enter[row][c]+=increment;
}
for(int r=row;r<n;++r){
leave[r][column]+=increment;
}
}
else{
int target;
cin>>target;
int row=0,column=m-1;
long long offset=enter[0][column];
bool found=false;
while(row<n&&column>=0){
long long value=a[row][column]+offset;
if(value==target){
found=true;
break;
}
if(value>target){
offset-=leave[row][column];
--column;
}
else{
++row;
if(row<n){
offset+=enter[row][column];
}
}
}
cout<<(found?'Y':'N')<<'\n';
}
}
}