Question

Microsoft | OA Coding Questions and Solutions | Set - 33 | 2022

Answer 1

Image of ques

Answer 2

// PASSED ALL TEST CASES


Please upvote if it helps you :) #Happy_Coding


Code ::


struct item{
int sum;
bool flip;
};


class SegTree{
public:
int size;
vector values;


SegTree(int n){
    size = 1;
    while(size<n) size*=2;
    for(int i=0;i<(2*size);i++) values.push_back({0,false});
}
int operation(item x,item y,int lx,int rx,int mid){
    int res = 0;
    if(x.flip == 0) res+=x.sum;
    else res += (mid-lx)-x.sum;
    if(y.flip == 0) res+=y.sum;
    else res+=(rx-mid)-y.sum;
    
    return res;
}

void propagate(int cur,int lx,int rx){
    int f = values[cur].flip,sum = values[cur].sum,m = (lx+rx)/2;
    
    if(f == 1) values[cur].sum = (rx-lx)-values[cur].sum;
    
    values[cur].flip = 0;
    
    if(rx-lx == 1) return;
    
    values[cur*2+1].flip ^= f;
    values[cur*2+2].flip ^= f;
}

void update(int cur,int lx,int rx,int l,int r){
    propagate(cur,lx,rx);
    if(rx<=l || lx>=r) return;
    if(lx>=l && rx<= r){
        values[cur].flip ^= 1;
        propagate(cur,lx,rx);
        return;
    }
    int mid = (lx+rx)/2;
    update(cur*2+1,lx,mid,l,r);
    update(cur*2+2,mid,rx,l,r);
    
    values[cur].sum = operation(values[cur*2+1],values[cur*2+2],lx,rx,mid);
}
void update(int l,int r){
    update(0,0,size,l,r);
}
int get(int cur,int lx,int rx,int k){
    propagate(cur,lx,rx);
    if(rx-lx == 1){
        propagate(cur,lx,rx);
        return lx;
    }
    int mid = (lx+rx)/2;
    int s1;
    if(values[2*cur+1].flip == 0) s1=values[2*cur+1].sum;
    else s1 = (mid-lx)-values[2*cur+1].sum;
    
    if(k<=s1){
        return get(cur*2+1,lx,mid,k);
    }else{
        return get(cur*2+2,mid,rx,k-s1);
    }
    values[cur].sum = operation(values[cur*2+1],values[cur*2+2],lx,rx,mid);
} 
int get(int k){
    return get(0,0,size,k);
}



};


vector Solution::solve(int A, vector<vector > &B)
{
SegTree st(A);
vector res;
for(auto it:B){
if(it[0] == 1){
st.update(it[1],it[2]);
}else{
res.push_back(st.get(it[1]));
}
}
return res;
}