HackerEarth: Comrades - III ( DS-LazyPropagation )

HackerEarth: Comrades - III ( DS-LazyProp )
///==================================================///
///                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 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++)
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     100005
#define inf    1000000010
#define MD     1000000000LL
#define eps    1e-9
///===============================///

vector<int>G[MX+2];
int St[MX+2],Ed[MX+2],tmm;
void Dfs(int u,int p) {
    St[u]=++tmm;
    for(int i=0; i<SZ(G[u]); i++) {
        int v=G[u][i];
        if( v==p ) continue;
        Dfs(v,u);
    }
    Ed[u]=tmm;
}

int nd[(4*MX)+2],mk[(4*MX)+2];
void Upd(int id,int l,int r,int q1,int q2,int v) { ///make all val from l to rgt v;
    if( q1>q2 )return;
    if( l==q1 && r==q2 ) {
        nd[id]=(v*(r-l+1));
        mk[id]=v;
        return;
    }
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    if( mk[id]!=-1 ) {
        int vl=mk[id];
        nd[lft]=(md-l+1)*vl;
        nd[rgt]=(r-md)*vl;
        mk[lft]=mk[rgt]=vl;
        mk[id]=-1;
    }
    if( q2<=md ) Upd(lft,l,md,q1,q2,v);
    else if(q1>md) Upd(rgt,md+1,r,q1,q2,v);
    else {
        Upd(lft,l,md,q1,md,v);
        Upd(rgt,md+1,r,md+1,q2,v);
    }
    nd[id]=nd[lft]+nd[rgt];
}

int Qry(int id,int l,int r,int q1,int q2) {
    if( q1>q2 ) return 0;
    if(l==q1 && r==q2) return nd[id];
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    if( mk[id]!=-1 ) {
        int vl=mk[id];
        nd[lft]=(md-l+1)*vl;
        nd[rgt]=(r-md)*vl;
        mk[lft]=mk[rgt]=vl;
        mk[id]=-1;
    }
    nd[id]=nd[lft]+nd[rgt];
    if(q2<=md) return Qry(lft,l,md,q1,q2);
    else if(q1>md) return Qry(rgt,md+1,r,q1,q2);
    else return Qry(lft,l,md,q1,md)+Qry(rgt,md+1,r,md+1,q2);
}

int main() {
    int tc,cs=1,i,j,k,q,n,x,y;
    //S(tc);
    tc=1;
    while(tc--) {
        S(n);
        fr(i,1,n)G[i].clear();
        int rt=1;
        fr(i,1,n) {
            S(x);
            if(x==0)rt=i;
            else {
                G[ x ].pb(i);
                G[ i ].pb(x);
            }
        }
        tmm=0;
        Dfs(rt,0);
        SET(mk);
        Upd(1,1,n,1,n,1);
        S(q);
        while(q--) {
            S2(x,y);
            if(x==1) {///soldiers who have S as one of their superior will wake up
                Upd(1,1,n,St[y]+1,Ed[y],1);
            } else if(x==2) { ///soldiers who have S as one of their superior will go to sleep
                Upd(1,1,n,St[y]+1,Ed[y],0);
            } else { ///number of soldiers who are awake and have S as one of their superior
                int ans=Qry(1,1,n,St[y]+1,Ed[y]);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}