# SWEETRQ - Editorial

Contest

Setter : Vitaly Demidenko
Tester : Rahul Dugar
Editorialist : Rajarshi Basu

Medium-Hard

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

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 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){
}
long long readIntLn(long long l,long long 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
}

2 Likes

I donâ€™t think its supposed to say â€śEasyâ€ť in difficulty

1 Like

You can directly count good rectangles by counting the number of corners which are greater than both neighbors (there are 2 in a good rectangle and 1 in a bad rectangle). Itâ€™s really the same solution in the end, though.

Also, you donâ€™t need to maintain a full sorted order, you can just maintain, for each cell, the count of how many are other cells are smaller/larger than it in its row/column. This means you can process queries in O(Q(N+M)) without log factors.

5 Likes