MO's on Tree- So Close Yet So Far(Codechef) 


CODECHEF:So Close Yet So Far(MO's on Tree)

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define piii pair< int ,pair<int,int> >
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
#define UNIK(v) sort(all(v)),v.resize( unique(all(v)) -v.begin() );
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     70005
#define inf    1000000010
#define MD     1000000007LL
#define eps    1e-9
///===============================///

vector<int>G[MX+2];
int n,Nd[MX+2];
int L[MX+2],P[MX+2][22];
int tmm,St[MX+2],Ed[MX+2];

void Dfs(int u,int p,int l) {
    L[ u ]=l;
    St[ u ]=++tmm;
    Nd[ tmm ]=u;
    P[ u ][ 0 ]=p;
    for(int i=0; i< SZ(G[u]) ; i++) {
        int v=G[u][i];
        if( v==p )continue;
        Dfs( v, u,l+1);
    }
    Ed[ u ]=++tmm;
    Nd[ tmm ]=u;
}

void Par_Sparse( ) {
    for(int j=1; (1<<j)<=n; j++) {
        for(int i=1; i<=n; i++) {
            if( P[i][j-1]!=-1 ) {
                P[i][j]=P[ P[i][j-1] ][ j-1 ];
            }
        }
    }
}

int Kth(int x,int k) {
    int j=0;
    while(k) {
        if(k%2==1)x=P[x][j];
        k/=2,j++;
    }
    return x;
}

int Lca(int x,int y) {
    if( L[x]<L[y] ) swap(x,y);
    x=Kth(x, L[x]-L[y] );
    if( x==y ) return x;
    for(int i=16; i>=0; i--) {
        if( P[x][i]!=P[y][i]) {
            x=P[x][i],y=P[y][i];
        }
    }
    return P[x][0];
}

int sq;
struct data {
    int l,r,id,lc;
    data() {};
    data(int a,int b,int c,int d) {
        l=a,r=b,id=c,lc=d;
    }
    bool friend operator <(data A,data B) {
        if( A.l/sq==B.l/sq ) return A.r<B.r;
        else return ((A.l/sq)<(B.l/sq));
    }
}v[MX+2];

inline int min(int a,int b) {
    return ((a<b)?a:b);
}
inline int max(int a,int b) {
    return ((a>b)?a:b);
}

int ar[MX+2],MP[MX+5];
piii nd[(4*MX)+5]; ///Closest dis,min in seg max in seg;
/// No two nodes have the same value printed on them.

inline void Ins(int id,int l,int r,int p,int f) {
    if( l==r ) {
        if( !f )nd[id].X=nd[id].Y.X=inf,nd[id].Y.Y=-inf;
        else nd[id].Y.X=nd[id].Y.Y=MP[ p ];
        return;
    }
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    if( p<=md ) Ins(lft,l,md,p,f);
    else Ins(rgt,md+1,r,p,f);
    if( nd[lft].Y.X==inf && nd[lft].Y.Y==-inf )nd[ id ]=nd[ rgt ];
    else if( nd[rgt].Y.X==inf && nd[rgt].Y.Y==-inf )nd[ id ]=nd[ lft ];
    else {
        nd[ id ].Y.X=min(nd[lft].Y.X,nd[rgt].Y.X);
        nd[ id ].Y.Y=max(nd[lft].Y.Y,nd[rgt].Y.Y);
        nd[ id ].X=min( nd[lft].X,min( nd[rgt].X, nd[rgt].Y.X-nd[lft].Y.Y ) );
    }
}

inline int Far( ) {
    return (nd[1].Y.Y-nd[1].Y.X);
}

inline int Close( ) {
    return nd[1].X;
}

bool Fr[MX+2];
inline void add(int p) {
    int nx=Nd[ p ];
    int vl=ar[ nx ];
    Fr[ nx ]^=1;
    if( Fr[nx]==1 )Ins(1,1,n,vl,1); ///add
    else Ins(1,1,n,vl,0);  ///remove
}

int ans[MX+2];
bool qr[MX+2];
inline void Solve(int q) {
    sq=600;
    sort( v,v+q );
    int cl=v[0].l,cr=cl-1;
    for(int i=0; i<q; i++) {
        int l=v[i].l;
        int r=v[i].r;
        int lc=v[i].lc;
        ///add frm left to l;
        while(cl<l) {
            add(cl++);
        }
        /// add frm rgt to l
        while(cl>l) {
            add(--cl);
        }
        /// add frm lft to r
        while(cr<r) {
            add(++cr);
        }
        /// rmv frm rgt to r
        while(cr>r) {
            add(cr--);
        }
        if( lc!=-1 ) add( St[lc] );
        ///Special case for adding Lca if endpoint is not lca!!
        int idx=v[i].id;
        if( qr[idx] )ans[ idx ]=Close( );
        else ans[ idx ]=Far( );
        if( lc!=-1 ) add( St[lc] );
    }
}
vector<int>vv;
int main() {
    int tc,cs=1,i,j,k,x,y,q;
    S(n);
    fr(i,1,n) {
        S(x);
        ar[i]=x;
        vv.pb( x );
    }
    ///Compressing data
    sort(all(vv));
    vv.resize( unique( all(vv) )-vv.begin() );
    fr(i,1,n) {
        x=lower_bound( all(vv),ar[i] )-vv.begin()+1;
        MP[x]=ar[i];
        ar[i]=x;
    }
    fr(i,1,n-1) {
        S2(x,y);
        G[x].pb(y);
        G[y].pb(x);
    }
    tmm=0;
    SET(P);
    Dfs(1,-1,1);
    Par_Sparse( );
    S(q);
    for(i=1; i<=q; i++) {
        char ch[2];
        scanf("%s",ch);
        S2(x,y);
        if( ch[0]=='C' )qr[i]=1; ///Close
        else qr[i]=0;///Far

        if( St[x]>St[y] )swap( x, y );
        int lc=Lca(x,y);
        if( lc==y ) v[i-1]=data( St[y],St[x],i,-1 );
        else v[i-1]=data( Ed[x],St[y],i,lc );
    }
    for(i=0; i<4*MX; i++) {
        nd[i].X=nd[i].Y.X=inf;
        nd[i].Y.Y=-inf;
    }
    Solve(q);
    fr(i,1,q) {
        printf("%d\n",ans[i]);
    }
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

HackerRank: Find Maximum Index Product ( Stack, DS, Histogram Logic )

HackerRank: Find Maximum Index Product ( Stack, DS ) (Find me on HackerRank @ Handle: BishalG ) Problem Summary: According to problem, you are given an array A of length n . For each index - i in the array, calculate IndexProduct(i) which is defined as: IndexProduct(i) = Left(i) * Right(i).  Again, Left(i) and Right(i) has following definition: Left(i) = Index on the left side of the array such that j < i and arr[j] > arr[i] Right(i) = Index on the right side of the array such that j > i and arr[j] > arr[i] If such index does not exist then it would be 0 in both cases. Our task is to find maximum of IndexProduct(i) among all values of i. Solution Idea: I'm explaining here the idea for generating values for Left array. Similar concept can be applied to find the values for Right array. After finding both arrays, we can easily calculate IndexProduct for every i and find the maximum value among them which will be our answer. Calculating Left array: If we think ...
Read more

Two Pointers Technique & Binary Search For Beginners

Sample Problem: Electronics Shop ( HackerRank ) (Find me on HackerRank @ Handle:  BishalG  ) Problem Summary: In this problem, you are given two arrays of positive integer numbers of lengths n and m respectively and another positive integer b . Your task is to find out the maximum integer formed by the summation of two integer values taken from different arrays and is less than or equal to b. If there does not exist such summation print -1 . Solution Idea: Since the constraints for n and m are small ( i.e. 1 <= n, m <= 1000 ) , so this problem is very much suitable to test different variants of our solution approaches. Here, we will discuss about 3 different approaches to solve this problem progressively starting from least efficient solution to most efficient one. Approach - 1: Brute-force If we think in brute-force manner, the naive approach to solve this problem will be to try every possible pairing among these two arrays. For this, we can just it...
Read more

HackerRank: Poisonous Plants ( Stacks, DS )

HackerRank: Poisonous Plants ( Stack, DS ) (Find me on HackerRank @ Handle: BishalG ) Problem Summary: In this problem, we are given some value , say pesticide levels of each plants. A plant will dies if all plants to its left side have smaller such value than that of its own. We have to calculate the number of days after which no plants will die!! Solution Idea: For every position find out: "How many times it will be hitted from right side", say hits(i) maximum among all hits(i) is the desired answer!! To find this, keep track of values in stack and try to eliminate all values in current stack which are greater than p(i) from each points !! At certain point, if we find element which is to be counted as kth hit counter but that element itself require more than k hits to be stable then, we count that element as hit source of maximum value. In this way, we will not repetitive actions and one element is added and popped from stack at most one time which leads to the O(n) time ...
Read more