REC25F - Editorial

editorial
,
1

Contest
Author: moinak878_pvt
Testers: chef_ash, rakesh272611
Editorialist: moinak878_pvt

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Hashing, Segment Trees

PROBLEM:

We have a board on which 2 type of queries can be performed.

  1. In this we can place a board of some color on a section of the board, the dimensions of which will be mentioned.
  2. We have to determine if 2 cells are similar, i.e we have to check whether both the cells have the same colors and of the same frequency.

EXPLANATION:

For the update queries we need to lazily update all the cells starting from top left to bottom right with the hash of the color. For the type 2 query, we need to check if the hash of the two cells are equal.
For this purpose we would maintain a 2D segment tree ( create a segment tree on every row and then create a segment tree on the already created segment tree ).

For the type 1 query, go through all the cells of the 2D segment tree that cover the range (both row wise and column wise) and update it with the hash. This would take O(logM.logN) time ( i.e , for logN rows , update logM columns).

For the type 2 query, go through all the rows of the segment tree whose ranges lie in the path from root to the range of the cell mentioned in the query (X0,Y0). Now, for every such row , similarly go through the columns and if you find non zero values in them , push them down to its children, till you reach a cell with no children. In such a case , add it to your current hash value.

Do the above step for both the cells (X0,Y0) and (X1,Y1) and compare their hashes. If those are equal print YES else print NO.

TIME COMPLEXITY :

O(M.N + Q.logM.logN)

SOLUTIONS:

Solution 
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

int P = 999999929;

vector< vector<int> > build(int &n,int &m){
    while(__builtin_popcount(n)!=1LL) n++;
    while(__builtin_popcount(m)!=1LL) m++;
    vector<vector<int> > tree(2*n+1 , vector<int> (2*m+1,0LL));
    return tree;
}

int query(vector< vector<int> > &tree , int n , int m , int i , int j){ 
    vector<int> rows , cols;
    for(int x=(n+i) ; x>=1LL; x/=2LL)
        rows.push_back(x);
    for(int x=(m+j) ; x>=1LL; x/=2LL)
        cols.push_back(x);
    reverse(begin(rows),end(rows));
    reverse(begin(cols),end(cols));

    int ans = 0LL;

    for(auto row : rows){
        for(auto col : cols){
            if(col<m){
                tree[row][2*col] = (tree[row][2*col] + tree[row][col])%P;
                tree[row][2*col+1] = (tree[row][2*col+1] + tree[row][col])%P;
                tree[row][col]=0;
            }
            else    
                ans= (ans + tree[row][col])%P;
        }
    }

    return ans;
}

void update_points(int node , int lr , int rr , int x , int y , vector<int> &points){
    if(lr>y || rr<x) // no overlap
        return;
    if(lr>=x && rr<=y) // complete overlap
    {
        points.push_back(node);
        return;
    }

    int mid = (lr + rr) / 2;
    update_points(2 * node, lr, mid, x, y, points);
    update_points(2 * node+1, mid+1, rr, x, y, points);
}

void update(vector< vector<int> > &tree , int n , int m , int i0 , int j0 , int i1 , int j1 , int v){
    // find nodes which contain i0 - i1
        // find nodes with j0-j1 -> +=v
    vector<int> rows,cols;
    update_points(1,0,n-1,i0,i1,rows);
    update_points(1,0,m-1,j0,j1,cols);
    
    for(auto row : rows){
        for(auto col : cols){
            tree[row][col]= (tree[row][col] + v)%P;
        }
    }
} 

long long bin_exp(long long a, long long b, long long m) {
    a %= m;
    long long res = 1LL;
    while (b > 0LL) {
        if (b & 1LL)
            res = res * a % m;
        a = a * a % m;
        b >>= 1LL;
    }
    return res;
}


int hash_functionA(int col){
    int HA = 67;
    int KA = 5654345;
    return bin_exp(KA+col , HA , P);
}

int hash_functionB(int col){
    int HB = 127;
    int KB = 3456982;
    return bin_exp(KB+col , HB , P);
}
void solve(){
    int n,m; cin>>n>>m;
    vector<vector<int> > treeA = build(n,m);
    vector<vector<int> > treeB = build(n,m);
    int Q; cin>>Q;
    assert(Q>=1LL && Q<=1e5);
    int type,x0,y0,x1,y1;
    while(Q--){
        cin>>type>>x0>>y0>>x1>>y1;
        x0-- , y0-- , x1-- , y1--;
        if(type==1){ // update
            int col ; cin>>col;
            int hash_colA = hash_functionA(col);
            int hash_colB = hash_functionB(col);
            update(treeA,n,m,x0,y0,x1,y1,hash_colA);
            update(treeB,n,m,x0,y0,x1,y1,hash_colB);
        }
        else{
            pair<int,int> point0 = {query(treeA,n,m,x0, y0) , query(treeB,n,m,x0,y0)};
            pair<int,int> point1 = {query(treeA,n,m,x1, y1) , query(treeB, n, m, x1, y1)};
            
            if(point0==point1)
                cout<<"YES\n";
            else
                cout<<"NO\n";
        }
    }
}
int32_t main(){
    fast
    solve();
    return 0;
}

Any other solution or feedback can be posted in the comments. We are always open to them.