BOJ 18437(회사 문화 5)풀이

solved.ac 티어 : 플래 3

www.acmicpc.net/problem/18437

18437번: 회사 문화 5

컴퓨터가 켜져 있는 상태를 1, 컴퓨터가 꺼져있는 상태를 0으로 두고 구간을 1 또는 0으로 변경한 뒤 구간 합을 출력하면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> nod;
const ll N=1000000;
ll n,m;
vector<ll> graph[N];
nod Qu[N]; 
ll cnf=0,p;
vector<ll>tree(4000000);
vector<ll>tree1(4000000);
void DFS(ll v,ll p){
    Qu[v].first = ++cnf;
    for(ll nv : graph[v]){
        if (nv==p){continue;}
        DFS(nv,v);
    }
    Qu[v].second=cnf;
}
ll seg(ll n,ll s,ll e){
    tree1[n]=-1;
    if(s==e){return tree[n]=1;}
    return tree[n]=seg(n*2,s,(s+e)/2)+seg(n*2+1,(s+e)/2+1,e);
}
void propagate(ll n,ll s,ll e){
    if(tree1[n]!=-1){
        if(s!=e){
            tree1[n*2]=tree1[n];
            tree1[n*2+1]=tree1[n];
        }
        tree[n]=tree1[n]*(e-s+1);
        tree1[n]=-1;
    }
}
ll max1(ll n,ll s,ll e,ll left,ll right){
    propagate(n,s,e);
    if(left>e||right<s){return 0;}
    if(left<=s&&e<=right){return tree[n];}
    return max1(n*2,s,(s+e)/2,left,right)+max1(n*2+1,(s+e)/2+1,e,left,right);
}
void change(ll n,ll s,ll e,ll s1,ll e1,ll f){
    propagate(n,s,e);
    if(s1<=s&&e<=e1){tree1[n]=f;propagate(n,s,e);return;}
    if(e1<s||s1>e){return;}
    change(n*2,s,(s+e)/2,s1,e1,f);
    change(n*2+1,(s+e)/2+1,e,s1,e1,f);
    tree[n]=tree[n*2]+tree[n*2+1];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n;
    ll q,c,d;
    for(int i = 1; i <= n; i++){
        cin >> p;
        if(p!=0){graph[p].push_back(i);}
    }
    cin >> m;
    DFS(1, 0);
    //for(int i=1;i<=n;i++){
    //    cout << Qu[i].first << ' ' << Qu[i].second <<'\n';
    //}
    seg(1,1,n);
    for(int i=0;i<m;i++){
        cin >> q >> c;
        if(q==1){change(1,1,n,Qu[c].first+1,Qu[c].second,1);}
        if(q==2){change(1,1,n,Qu[c].first+1,Qu[c].second,0);}
        if(q==3){cout << max1(1,1,n,Qu[c].first+1,Qu[c].second) << '\n';}
    }
}