백준 32991 폭죽놀이

https://www.acmicpc.net/problem/32991

 

차수에 대한 루트질인줄 알고 큐에 담아뒀는데 교환법칙이 성립하지 않아 안 된다.. 어디선가 ETT를 희안하게 하면 된다는 것까지만 들었었고, 며칠 전에 jsj0412에게 풀이를 듣고 열심히 짰다.

 

2번 쿼리는 그냥 ETT 슥삭 하면 되고, 1번 쿼리를 잘 처리할 수 있어야 한다. 정점에 번호를 매길 때 dfs 방문 순으로 매기는 대신 정점 v를 방문했을 때 v의 자식들에 순서대로 번호를 매기는 작업을 재귀적으로 반복하자. 예제 2에서 주어지는 트리는 다음과 같이 번호가 매겨진다.

이렇게 번호를 매기면 임의의 정점의 자식들은 하나의 구간을 이루고, 자신을 제외한 서브트리의 모든 정점이 하나의 구간을 이루니 필요에 따라 부모, 자신에는 쿼리를 따로 적용하면 1번, 2번 연산에 세그를 쓸 수 있다.

 

dfs를 하며 자신을 제외한 서브트리의 구간을 담아야 하는데, 이거 짜면서 실수해서 한참 디버깅했다. 

 

그냥 발상이 개어려운것같다. 이런 생각을 어떻게하지

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
 
ll id[202020], in[202020], out[202020], p[202020], N, Q, x[202020], lazy[202020 << 2][2];
vector<int> T[202020];
 
void init(int now, int l, int r){
    lazy[now][0] = 1;
    if (l == r) return;
    int m = l+r >> 1;
    init(now*2, l, m);
    init(now*2+1, m+1, r);
}
 
void push(int now, int l, int r) {
    if (l != r) {
        lazy[now*2][0] = lazy[now*2][0]*lazy[now][0] % MOD;
        lazy[now*2][1] = (lazy[now][0]*lazy[now*2][1] + lazy[now][1]) % MOD;
        lazy[now*2+1][0] = lazy[now*2+1][0]*lazy[now][0] % MOD;
        lazy[now*2+1][1] = (lazy[now][0]*lazy[now*2+1][1] + lazy[now][1]) % MOD;
        lazy[now][0] = 1;
        lazy[now][1] = 0;
    }
}
void update(int now, int l, int r, int s, int e, ll a, ll b) {
    push(now, l, r);
    if (r < s or e < l) return;
    if (s <= l and r <= e) {
        lazy[now][0] = lazy[now][0]*a % MOD;
        lazy[now][1] = (lazy[now][1]*a + b) % MOD;
        push(now, l, r);
        return;
    }
    int m = l+r >> 1;
    update(now*2, l, m, s, e, a, b);
    update(now*2+1, m+1, r, s, e, a, b);
}
ll query(int now, int l, int r, int i, int ii) {
    push(now,l,r);
    if (l == r) return (lazy[now][0]*x[ii] + lazy[now][1]) % MOD;
    int m = l+r >> 1;
    if (i <= m) return query(now*2, l, m, i, ii);
    else return query(now*2+1, m+1, r, i, ii);
}
 
void dfs(int v) {
    static int ii = 1;
    for (int i : T[v]) 
        id[i] = ++ii;
    for (int i : T[v]) {
        dfs(i);
        if (!in[v]) in[v] = id[i];
        out[v] = ii;
    }
}
 
int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
 
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> x[i];
    init(1,1,N);
    for (int i = 2; i <= N; i++){
        cin >> p[i];
        T[p[i]].push_back(i);
    }
    id[1] = 1;
    dfs(1);
    cin >> Q;
    while (Q--){
        int op, v, a, b;
        cin >> op >> v;
        if (op == 1) {
            cin >> a >> b;
            if (T[v].size()) update(1,1,N,id[T[v][0]],id[T[v].back()],a,b);
            update(1,1,N,id[v],id[v],a,b);
            if (p[v]) update(1,1,N,id[p[v]],id[p[v]],a,b);
        }
        else if (op == 2){
            cin >> a >> b;
            if (in[v]) update(1,1,N,in[v],out[v],a,b);
            update(1,1,N,id[v],id[v],a,b);
        }
        else cout << query(1,1,N,id[v],v) << '\n';
    }
}