HACKEREARTH SEGMENT TREE PROBLEMS

1) https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/shivam-and-expensive-birthday-gift-da58b2f0/

2) https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/distinct-integers-in-range-66eca44b/

3) https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/k-th-bit-faae0e0d/

4) https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/easy-queries-751f9372/?sort=recent-comments

---------------------------------------------------------------------------------------------------------------------------------------

Answer 1 ->
#include<bits/stdc++.h>
using namespace std;

vector<long long> tree,arr;

void update(int start, int end, int parent, int index, int type){
    if(start==end){
        if(type==1){
            arr[start]++;
            tree[parent]++;
        }
        if(type==2 && arr[start]>0){
            arr[start]--;
            tree[parent]--;
        }
        return;
    }
    int mid=(start+end)/2;
    if(index>mid){
        update(mid+1,end,2*parent+2,index,type);
    }
    else{
        update(start,mid,2*parent+1,index,type);
    }
    tree[parent]=tree[2*parent+1]+tree[2*parent+2];
}

long long query(int start, int end, int parent, int qstart, int qend){
    if(qstart>end || qend<start){
        return 0;
    }
    if(qstart<=start && qend>=end){
        return tree[parent];
    }
    int mid=(start+end)/2;
    long long L=query(start,mid,2*parent+1,qstart,qend);
    long long R=query(mid+1,end,2*parent+2,qstart,qend);
    return L+R;
}

int main(){
    long long N,Q;
    scanf("%lld %lld ", &N, &Q);

    tree.resize(4*N+5,0);
    arr.resize(N,0);

    for(int i=0;i<Q;i++){
        long long type;
        scanf("%lld", &type);
        if(type==1 || type==2){
            long long index;
            scanf("%lld", &index);
            update(0,N-1,0,index-1,type);
        }
        else{
            long long l,r;
            scanf("%lld %lld", &l, &r);
            int ans=query(0,N-1,0,l-1,r-1);
            cout<<ans<<endl;
        }
    }
}

---------------------------------------------------------------------------------------------------------------------------------------
Answer 2->
#include <bits/stdc++.h>
using namespace std;

vector<bitset<5001>> treeA,treeB;
vector<int> A,B;

void build(int start, int end, int parent){
    if(start>end){
        return;
    }
    if(start==end){
        treeA[parent].set(A[start]);
        treeB[parent].set(B[start]);
        return;
    }
    int mid=(start+end)/2;
    build(start,mid,2*parent+1);
    build(mid+1,end,2*parent+2);
    treeA[parent]=treeA[2*parent+1] | treeA[2*parent+2];
    treeB[parent]=treeB[2*parent+1] | treeB[2*parent+2];
    return;
}

bitset<5001> query(int start, int end, int parent, int qstart, int qend, char type){
    if(qend<start || qstart>end){
        return bitset<5001>();
    }
    if(qstart<=start && qend>=end){
        if(type=='A'){
            return treeA[parent];
        }
        else{
            return treeB[parent];
        }
    }
    int mid=(start+end)/2;
    auto L=query(start,mid,2*parent+1,qstart,qend,type);
    auto R=query(mid+1,end,2*parent+2,qstart,qend,type);
    return L | R;
}


int main() {
    int N;
    cin>>N;

    A.resize(N);
    B.resize(N);

    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    for(int i=0;i<N;i++){
        cin>>B[i];
    }

    treeA.resize(4*N+5);
    treeB.resize(4*N+5);

    build(0,N-1,0);

    int Q;
    cin>>Q;

    while(Q--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        auto AQ=query(0,N-1,0,a-1,b-1,'A');
        auto BQ=query(0,N-1,0,c-1,d-1,'B');
        cout<<(AQ | BQ).count()<<endl;
    }
}
---------------------------------------------------------------------------------------------------------------------------------------
Answer 3->
#include <bits/stdc++.h>
using namespace std;

vector<int> tree;

void build(int start, int end, int parent){
    if(start==end){
        tree[parent]=1;
        return;
    }
    int mid=(start+end)/2;
    build(start,mid,2*parent+1);
    build(mid+1,end,2*parent+2);
    tree[parent]=tree[2*parent+1]+tree[2*parent+2];
}

void update(int start, int end, int parent, int index){
    if(start==end){
        tree[parent]=0;
        return;
    }
    int mid=(start+end)/2;
    if(index>mid){
        update(mid+1,end,2*parent+2,index);
    }
    else{
        update(start,mid,2*parent+1,index);
    }
    tree[parent]=tree[2*parent+1]+tree[2*parent+2];
}

int query(int start, int end, int parent, int K){
    if(start==end){
        return K==0 ? start : INT_MAX;
    }
    int mid=(start+end)/2;
    if(tree[2*parent+1]>K){
        return query(start,mid,2*parent+1,K);
    }
    else{
        return query(mid+1,end,2*parent+2,K-tree[2*parent+1]);
    }
}

int main() {
    int N;
    cin>>N;

    tree.resize(4*N+5);
    build(0,N-1,0);

    int Q;
    cin>>Q;

    while(Q--){
        int type;
        cin>>type;
        if(type==1){
            int K;
            cin>>K;
            int ans=query(0,N-1,0,K-1);
            if(ans==INT_MAX){
                cout<<-1<<endl;
            }
            else{
                cout<<ans+1<<endl;
            }
        }
        else{
            int index;
            cin>>index;
            update(0,N-1,0,index-1);
        }
    }
}
---------------------------------------------------------------------------------------------------------------------------------------
Answer 4->
/*
#include <bits/stdc++.h>
using namespace std;

pair<int,int> tree[4*100001+5];  // {first,second}={min,max}
int arr[100001];

void build(int start, int end, int parent){
    if(start==end){
        if(arr[start]==1){
            tree[parent]={start,start};
        }
        else{
            tree[parent]={INT_MIN,INT_MAX};
        }
        return;
    }
    int mid=(start+end)/2;
    build(start,mid,2*parent+1);
    build(mid+1,end,2*parent+2);
    tree[parent].first=max(tree[2*parent+1].first,tree[2*parent+2].first);
    tree[parent].second=min(tree[2*parent+1].second,tree[2*parent+2].second);
    return;
}

void update(int start, int end, int parent, int index){
    if(start==end){
        tree[parent]={start,start};
        return;
    }
    int mid=(start+end)/2;
    if(index>mid){
        update(mid+1,end,2*parent+2,index);
    }
    else{
        update(start,mid,2*parent+1,index);
    }
    tree[parent].first=max(tree[2*parent+1].first,tree[2*parent+2].first);
    tree[parent].second=min(tree[2*parent+1].second,tree[2*parent+2].second);
}

int query(int start, int end, int parent, int qstart, int qend, char type){
    if(qstart>end || qend<start){
        return type=='L' ? INT_MIN : INT_MAX;
    }
    if(qstart<=start && qend>=end){
        return type=='L' ? tree[parent].first : tree[parent].second;
    }
    int mid=(start+end)/2;
    int Lans=query(start,mid,2*parent+1,qstart,qend,type);
    int Rans=query(mid+1,end,2*parent+2,qstart,qend,type);
    return type=='L' ? max(Lans,Rans) : min(Lans,Rans);
}

int main() {
    int N;
    cin>>N;

    int Q;
    cin>>Q;

    for(int i=0;i<N;i++){
        cin>>arr[i];
    }

    build(0,N-1,0);

    while(Q--){
        int type,index;
        cin>>type>>index;

        if(type==0){
            int L=query(0,N-1,0,0,index-1,'L');
            int R=query(0,N-1,0,index+1,N-1,'R');
            if(L==INT_MIN){
                L=-1;
            }
            if(R==INT_MAX){
                R=-1;
            }
            cout<<L<<" "<<R<<endl;
        }
        else if(arr[index]==0){
            arr[index]=1;
            update(0,N-1,0,index);
        }
    }
}
*/

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin>>N;

    int Q;
    cin>>Q;

    vector<int> arr(N);
    set<int> s;

    for(int i=0;i<N;i++){
        cin>>arr[i];
        if(arr[i]==1){
            s.insert(i);
        }
    }

    while(Q--){
        int type,index;
        cin>>type>>index;

        if(type==0){
            int L=-1;
            int R=-1;
            auto itr1=s.upper_bound(index-1);
            auto itr2=s.upper_bound(index);
            if(itr1!=s.begin()){
                L=*prev(itr1);
            }
            if(itr2!=s.end()){
                R=*itr2;
            }
            cout<<L<<" "<<R<<endl;
        }
        else if(arr[index]==0){
            arr[index]=1;
            s.insert(index);
        }
    }
}