ENCDEC6 - EDITORIAL

PROBLEM LINK:

Practice

Author: Rishab Jain
Tester: Akash Kumar Bhagat
Editorialist: Rishab Jain

DIFFICULTY:

EASY-MEDIUM.

PREREQUISITES:

Lazy Segment Tree , Constant time range add operation

EXPLANATION:

The problem can be solved with lazy propagation in segment tree .When there are many updates and updates are done on a range, we can postpone some updates (avoid recursive calls in update) and do those updates only when required.
For more details on lazy segment tree visit Here.

Time complexity : O(ylogn +ylogn + logn) .

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long int 
#define inf 1e18
#define MAX 40005

const int mod = 1e9 + 7;

int t[MAX]; 
int lazy[MAX]; 
  


void push(int v) {
    t[v*2] += lazy[v];
    lazy[v*2] += lazy[v];
    t[v*2+1] += lazy[v];
    lazy[v*2+1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int addend) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        t[v] += addend;
        lazy[v] += addend;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), addend);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
        t[v] = min(t[v*2], t[v*2+1]);
    }
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return inf;
    if (l <= tl && tr <= r)
        return t[v];
    push(v);
    int tm = (tl + tr) / 2;
    return min(query(v*2, tl, tm, l, min(r, tm)), 
               query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

void built(int arr[], int ss, int se, int si) 
{ 
   
    if (ss > se) 
        return; 
  
    
    if (ss == se) { 
        t[si] = arr[ss]; 
        return; 
    } 
  
    
    int mid = (ss + se) / 2; 
    built(arr, ss, mid, si * 2 ); 
    built(arr, mid + 1, se, si * 2 + 1); 
  
    t[si] = min(t[si * 2], t[si * 2 + 1]); 
} 


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int tt;
    
    cin>>tt;
    
    while(tt--){
    memset(t,0,sizeof(t));
    memset(lazy,0,sizeof(lazy));
	int n , y;
	cin>>n;
	int arr[n];

	for(int i = 0; i<n ;i++){
		arr[i] = 1;
	}
     
    built(arr, 0, n - 1, 1);
	

	cin>>y;

	
    
    int l ,r;

	
    for(int i=0;i<y;i++){
    cin>>l>>r;
    int add = query(1,1,n,l+1,r+1);
    add = add % mod;
	update(1,1,n,l+1,r+1,add);
    }

	
	cout <<query(1,1,n,1,n)%mod<<endl; 

    }

}

Tester's Solution

MAX = 100005
tree = [0] * MAX; 
lazy = [0] * MAX;
 
def updateRangeUtil(si, ss, se, us, ue, diff) :
    if (lazy[si] != 0) :
        tree[si] += lazy[si];
        if (ss != se) :
            lazy[si * 2 + 1] += lazy[si];
            lazy[si * 2 + 2] += lazy[si];
        lazy[si] = 0;
 
    if (ss > se or ss > ue or se < us) :
        return; 
 
    if (ss >= us and se <= ue) :
        tree[si] += diff;
        if (ss != se) :
            lazy[si * 2 + 1] += diff;
            lazy[si * 2 + 2] += diff;
        return; 
 
    mid = (ss + se) // 2;
    updateRangeUtil(si * 2 + 1, ss,mid, us, ue, diff);
    updateRangeUtil(si * 2 + 2, mid + 1,se, us, ue, diff);
    tree[si] = min(tree[si * 2 + 1],tree[si * 2 + 2]); 
 
def updateRange(n, us, ue, diff) : 
    updateRangeUtil(0, 0, n - 1, us, ue, diff); 
 
def getSumUtil(ss, se, qs, qe, si) :
    if (lazy[si] != 0) :
        tree[si] += lazy[si];
        if (ss != se) :
            lazy[si * 2 + 1] += lazy[si];
            lazy[si * 2 + 2] += lazy[si];
        lazy[si] = 0;
 
    if (ss > se or ss > qe or se < qs) :
        return 10e9; 
 
    if (ss >= qs and se <= qe) :
        return tree[si]; 
 
    mid = (ss + se) // 2; 
    return min(getSumUtil(ss, mid, qs, qe, 2 * si + 1),getSumUtil(mid + 1, se, qs, qe, 2 * si + 2)); 
 
def getSum(n, qs, qe) : 
    if (qs < 0 or qe > n - 1 or qs > qe) :
        #print("Invalid Input", end = "");
        return -1;
 
    return getSumUtil(0, n - 1, qs, qe, 0); 
 
def constructSTUtil(arr, ss, se, si) : 
    if (ss > se) :
        return;
    if (ss == se) :
        tree[si] = arr[ss];
        return; 
    mid = (ss + se) // 2;
    constructSTUtil(arr, ss, mid, si * 2 + 1);
    constructSTUtil(arr, mid + 1, se, si * 2 + 2);
    tree[si] = min(tree[si * 2 + 1], tree[si * 2 + 2]); 
 
def constructST(arr, n) :
    constructSTUtil(arr, 0, n - 1, 0); 
 
for _ in range(int(input())):
    tree = [0] * MAX; 
    lazy = [0] * MAX;
    n=int(input());
    y=int(input());
    arr=[1]*n;
    constructST(arr, n);
    for xyz in range(y):
        l,r=map(int,input().split());
        updateRange(n, l, r, getSum(n, l, r)%1000000007);
    print(getSum(n, 0, n-1)%1000000007);

ALTERNATE EXPLANATION:

If we remove queries to find minimum then the problem will have no updates and using constant time range add operation it will be solved more faster.

we are removing queries to find minimum because , minimum in the range will always be even and in powers of 2 ,so follow the range queries and do constant time range add operation and at last find minimum and calculate its power with base 2.

Time Complexity : O(n + logn ).

How to do constant time range add operation?
Link

How to find power in O(logn) ?
Link

Solution

1 Like