PROBLEM LINK
Setter : Vitaly Demidenko
Tester : Rahul Dugar
Editorialist : Rajarshi Basu
DIFFICULTY
Medium-Hard
PREREQUISITES
Implementation
PROBLEM
We are given a rectangle of size N*M : N,M\leq 1000. We need to count the number of rectangles so that one of the following conditions should hold:
- \min(a_{r_1,c_1}, a_{r_2,c_2}) \gt \max(a_{r_1,c_2}, a_{r_2,c_1})
- \min(a_{r_2,c_1}, a_{r_1,c_2}) \gt \max(a_{r_1,c_1}, a_{r_2,c_2})
We also have Q \leq 10000 queries, where we update a particular cell to a different value, and after every such query, we need to output the new number of such rectangles.
EXPLANATION
Observation 1
Instead of good rectangles, can we count bad rectangles more easily?
Observation 2
Each bad rectangle has exactly 2 corners such that one of their adjacent corners have higher value, and the other has lower value. Think how we can use this to count.
Full Solution
- Just count how many rectangles each corner is a part of (make use of sorted orderings along rows and columns or other such methods) using simple counting along rows and columns and then multiply them, and then divide by 2 since each rectangle is double counted by both its corners.
- To handle updates, just do a linear scan across the row and column of the cell to remove previous rectangles that were considered, and add in the new ones. Again, update the sorted orderings of the row and column affected.
Time Complexity
O(NM \log max(N,M) + Q(NlogN + MlogM))
SOLUTION
Tester's Code
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int a[1005][1005];
vi roc[1005],coc[1005];
vi rop[1005],cop[1005];// $ROPE
void solve() {
int n=1000,m=1000;
cin>>n>>m;
vector<pair<int,pii>> hol;
fr(i,1,n)
fr(j,1,m)
// a[i][j]=rng(1e18);
cin>>a[i][j];
fr(i,1,n) {
roc[i].resize(m);
iota(all(roc[i]),1LL);
sort(all(roc[i]),[&](int j, int k){
return a[i][j]<a[i][k];
});
rop[i].resize(m+1);
for(int j=0; j<m; j++)
rop[i][roc[i][j]]=j;
}
fr(i,1,m) {
coc[i].resize(n);
iota(all(coc[i]),1LL);
sort(all(coc[i]),[&](int j, int k){
return a[j][i]<a[k][i];
});
cop[i].resize(n+1);
for(int j=0; j<n; j++)
cop[i][coc[i][j]]=j;
}
int ans=(n*(n-1)*m*(m-1))/2;
fr(i,1,n)
fr(j,1,m) {
int roo=rop[i][j];
int coo=cop[j][i];
ans-=roo*(n-coo-1)+coo*(m-roo-1);
}
cout<<ans/2<<endl;
int q=10000;
cin>>q;
int pool=0;
while(q--) {
int x,y,h;
cin>>x>>y>>h;
// x=rng(n)+1,y=rng(m)+1,h=rng(1e18);
fr(i,1,n) {
int roo=rop[i][y];
int coo=cop[y][i];
ans+=roo*(n-coo-1)+coo*(m-roo-1);
}
fr(i,1,m) {
if(i==y)
continue;
int roo=rop[x][i];
int coo=cop[i][x];
ans+=roo*(n-coo-1)+coo*(m-roo-1);
}
trace(1);
for(int i=0; i<m; i++)
if(roc[x][i]==y) {
roc[x].erase(roc[x].begin()+i);
break;
}
for(int i=0; i<n; i++)
if(coc[y][i]==x) {
coc[y].erase(coc[y].begin()+i);
break;
}
trace(1);
a[x][y]=h;
roc[x].insert(upper_bound(all(roc[x]),y,[&](int j, int k){
return a[x][j]<a[x][k];
}),y);
coc[y].insert(upper_bound(all(coc[y]),x,[&](int j, int k){
return a[j][y]<a[k][y];
}),x);
trace(1,roc[x],coc[y]);
trace(rop[x],coc[y]);
for(int j=0; j<m; j++)
rop[x][roc[x][j]]=j;
for(int j=0; j<n; j++)
cop[y][coc[y][j]]=j;
trace(1);
fr(i,1,n) {
int roo=rop[i][y];
int coo=cop[y][i];
ans-=roo*(n-coo-1)+coo*(m-roo-1);
}
trace(1);
fr(i,1,m) {
if(i==y)
continue;
int roo=rop[x][i];
int coo=cop[i][x];
ans-=roo*(n-coo-1)+coo*(m-roo-1);
}
pool+=ans/2;
cout<<ans/2<<endl;
}
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(7);
int t=1;
// cin>>t;
fr(i,1,t)
solve();
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
