2022.07.29. (6~9일차 평가) 풀이

A. [23238] Best Student (Diamond V)

의도한 태그: Mo's Algorithm + Square Root Decomposition

문제를 간단히 해석하자면, \( [L, R] \) 구간에서 가장 많이 등장한 학생을 찾는 문제가 됩니다.

그러니 Mo's를 사용하면 간단히 해결할 수 있겠죠.

 

그런데, 가장 많이 등장한 학생을 찾을 때 "등장 횟수"를 Segment Tree 같은 걸로 저장시키면

시간복잡도에 log가 붙으면서 TLE가 나게 됩니다.

 

그러니, "등장 횟수"의 개수를 Square Root Decomposition으로 관리해주면 됩니다.

Square Root Decomposition의 시간 복잡도는 Mo's와 독립적으로 계산되므로, 합하면 \( O(Q \sqrt(N)) \)이 됩니다.

 

+ 번호가 \( 10^9 \)까지 갈 수 있으니, 좌표 압축 등으로 인덱싱을 해주기 편한 값으로 바꿔줘야 합니다.

map<int, int> cvt, tvc; set<int> cs; int cc = 0;
int arr[100020]; pi3 qry[100020];
int sq;
int cnt[123456]; vector<int> sqr[1020]; int sqm[1020];
int ans[100020];

inline void upd(int pos, int val){
	int p = pos / sq;
	if (sqr[p].size() == cnt[pos]+val){ sqr[p].push_back(0); }
	sqr[p][ cnt[pos] ] -= 1; sqr[p][ cnt[pos]+val ] += 1;
	if (val == 1){ sqm[p] = max(sqm[p], cnt[pos]+1); }
	if (val == -1){
		if (sqm[p] == cnt[pos] && sqr[p][ cnt[pos] ] == 0){ sqm[p] -= 1; }
	}
	cnt[pos] += val;
}

void Main(){
	int n, q; cin >> n >> q; sq = sqrt(n);
	int grp = n / sq;
	//cout << "SQ " << sq << endl;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; cs.insert(arr[i]); }
	for (int x : cs){ cc += 1; cvt[x] = cc; tvc[cc] = x; }
	for (int i = 1; i <= q; i++){ cin >> qry[i].fr.fr >> qry[i].fr.sc; qry[i].sc = i; }
	sort(qry+1, qry+q+1, [](pi3 a, pi3 b){
		if (a.fr.fr / sq != b.fr.fr / sq){ return a.fr.fr / sq < b.fr.fr / sq; }
		if ( (a.fr.fr/sq) & 1 ){ return a.fr.sc > b.fr.sc; }
		else{ return a.fr.sc < b.fr.sc; }
	});
	for (int i = 1; i <= n; i++){ arr[i] = cvt[ arr[i] ]; }
	/* cout << "ARR ";
	for (int i = 1; i <= n; i++){ cout << arr[i] << ' '; }
	cout << endl; */
	for (int i = 0; i <= grp; i++){ sqr[i].push_back(sq); }
	int st = 1, ed = 1; upd(arr[1], 1);
	for (int i = 1; i <= q; i++){
		int pst = qry[i].fr.fr, ped = qry[i].fr.sc;
		int qi = qry[i].sc;
		for (int p = pst; p < st; p++){ upd(arr[p], 1); }
		for (int p = ed+1; p <= ped; p++){ upd(arr[p], 1); }
		for (int p = st; p < pst; p++){ upd(arr[p], -1); }
		for (int p = ped+1; p <= ed; p++){ upd(arr[p], -1); }
		st = pst; ed = ped;
		pi2 res = {0, 0};
		int mx = 0, mxp = 0;
		for (int p = 0; p <= grp; p++){
			if (sqm[p] >= mx){ mx = sqm[p]; mxp = p; }
		}
		for (int p = mxp*sq; p < (mxp+1)*sq; p++){
			res = max(res, {cnt[p], p});
		}
		ans[qi] = tvc[res.sc];
	}
	for (int i = 1; i <= q; i++){ cout << ans[i] << endl; }
}

B. [20106] Cave (Platinum V)

의도한 태그: Outside of the Lecture (Binary Search - Parametric Search)

맨 앞에 있는 문의 위치를 찾아봅시다. 이는, 아래와 같은 방식으로 파라메트릭 서치를 써서 찾아줄 수 있습니다.

• \( X \)에 대해서, \( [1, X] \)의 스위치를 켤 때 0번 문이 닫히는가?

위 질문에 Yes라고 답하는 첫 \( X \)의 위치가 정답이 됩니다.

 

그 뒤로는, 0번 문을 열어둔 뒤 1번 문에 대해 동일한 탐색을 적용시키면 됩니다.

주의할 점은, \( [1, X] \) 구간에 0번 문의 스위치가 있다면, 0번 문의 스위치는 건드리면 안 됩니다.

void exploreCave(int N) {
    int flp[5020] = {};
    int dor[5020] = {};
    bool chk[5020] = {};
    for (int i = 0; i < N; i++){
        int st = 0, ed = N-1;
        int res1 = tryCombination(flp);
        while (st < ed){
            int mid = st + ed >> 1;
            for (int j = st; j <= mid; j++){
                if (chk[j]){ continue; }
                flp[j] ^= 1;
            }
            int res2 = tryCombination(flp);
            for (int j = st; j <= mid; j++){
                if (chk[j]){ continue; }
                flp[j] ^= 1;
            }
            if ( (res1==i) ^ (res2==i) ){ ed = mid; }
            else{ st = mid+1; }
        }
        int ptr = st;
        dor[ptr] = i; chk[ptr] = 1;
        if (res1 == i){ flp[ptr] = 1; }
    }
    answer(flp, dor);
}

C. [18484] Eight Sins (Diamond V)

의도한 태그: Square Root Decomposition

\( k/n \)을 기준으로 구간을 \( N \)개로 나눠봅시다.

그럼, 이진 탐색을 진행하기 전에 구간의 끝점에 답이 존재하는지 판별하면서

만약 존재하지 않다면 그 구간 전체를 점프뛰어주면 됩니다.

 

이 때 사용되는 연산의 횟수는 구간에서 이진탐색 \( N \)회 + 구간을 넘기는 횟수 \( N-1 \)회 + 구간에 들어가는 횟수 \( N \)회 = \( N-1 + N + N \left\lceil \log_{2} \frac{K}{N} \right\rceil \)가 되고, 그래프 등을 그려보면 2600보다 조금 작은 수가 나오는 걸 볼 수 있습니다.

진짜 말 그대로 2600보다 조금 작은 수

int num = 0;

int ask(ll x){ num += 1; assert(num <= 2600);
	cout << x << endl << flush;
	char ch; cin >> ch;
	if (ch == '>'){ return 1; } if (ch == '<'){ return -1; } return 0;
}

void Main(){
	ll n, k; cin >> n >> k;
	int idx = 1, cnt = 0; ll lst = 0;
	while (cnt < n){
		int res = (idx < n ? ask(idx*k / n) : -1);
		if (res > 0){ idx += 1; continue; }
		else if (res == 0){ lst = idx*k / n; cnt += 1; idx += 1; continue; }
		else{
			ll st = max((idx-1)*k/n + 1, lst+1), ed = idx*k / n;
			while (st <= ed){
				ll mid = st+ed >> 1;
				int res = ask(mid);
				if (res > 0){ st = mid+1; } else if (res < 0){ ed = mid-1; } else{ lst = mid; break; }
			}
			cnt += 1;
		}
	}
}

D. [21091] Increasing or Decreasing (Platinum III)

의도한 태그: Outside of the Lecture (Ad-Hoc, Constructive)

우선, 크기 비교는 귀찮으니 전체 배열을 오름차순으로 정렬해봅시다.

 

그 뒤, 1번 인덱스부터 탐색을 시작해봅시다.

만약 구간 \( [i, N] \)이 오름차순으로 정렬되어있었다면, \( i \)번 위치에는 \( B_{i} \)를 간단히 넣을 수 있습니다.

그냥 \( A_{j} = B_{i} \)가 등창하는 위치 \( j \)를 찾은 뒤, \( [i, j] \)를 내림차순으로 정렬해주면 됩니다.

비슷한 이유로, 구간 \( [i, N] \)이 내림차순으로 정렬되어있었다면, \( [i, j] \)를 오름차순으로 정렬해주면 됩니다.

 

그러니, 아래와 같은 방식으로 오름차순 / 내림차순을 판별해봅시다.

• \( A_{j} = B_{i} \)인 위치 \( j \)를 찾는다. (이는 자명히 \( i \le j \)가 된다)
• \( A_{i} < A_{j} \)라면, 오름차순 정렬된 것으로 보고 \( [i, j] \)를 내림차순 정렬시킨다.
• \( A_{i} > A_{j} \)라면, 내림차순 정렬된 것으로 보고 \( [i, j] \)를 오름차순 정렬시킨다.

그리고 이러면 AC를 받습니다. (??)

연산을 진행시키면서 오름차순/내림차순 정렬의 가정이 깨지는데, 왜 AC를 받는 걸까요?

 

아래와 같은 귀납법으로 증명할 수 있습니다.

• 모든 시점에 대해서, \( A_{i} \)보다 큰 값들만 모으면 오름차순 정렬이고, \( A_{i} \)보다 작은 값들만 모으면 내림차순 정렬이다.

즉, 대강 아래와 같은 상태를 의미합니다.

본격적으로 증명해봅시다.

• 시작할 때 정렬을 하고 시작하므로, 자명하게 초기 상태에서의 위 명제는 참이다.
• \( i \)번째 연산을 수행하기 전 상태에서 위 명제가 참이라고 하자.
  그럼, \( i \)번째 연산을 수행한 뒤에도 위 명제는 참이 되며, 이유는 아래 그림으로 보일 수 있다.

 

근데 이러면 총 \( N+1 \)번의 연산을 수행하는 게 아닐까요?

다행히도, \( N \)번째 위치를 정하는 건 없어도 됩니다.

어차피 배열의 길이가 1이라 알아서 고정되기 때문이죠.

그러니 총 연산 횟수는 \( 1 + N-1 = N \)회가 됩니다.

E. [24271] xor² (Platinum III)

의도한 태그: Segment Tree (4일차, 응용) + Trie

2번 쿼리는 평소에 보던 Update 쿼리지만, 1번 쿼리가 좀 난해합니다.

 

세그먼트 트리의 리프 정점이 \( 2^k \)개일 때 트리가 Trie처럼 구축된다는 사실에서 출발해봅시다.

그럼, 현재 구간에서 비트가 꺼져있다면 평소대로 진행하면 됩니다.

그런데 비트가 켜져 있다면? 왼쪽 구간과 오른쪽 구간을 swap해준 뒤 탐색을 이어나가면 됩니다.

즉, 아래 방식대로 쿼리를 처리해주면 됩니다.

const int N = 262144;
ll seg[524290];

void upd(int pos, ll val){ pos += N;
	seg[pos] ^= val; pos >>= 1;
	while (pos > 0){
		seg[pos] = seg[pos<<1] ^ seg[pos<<1|1];
		pos >>= 1;
	}
}
ll qry(int ni, int ns, int ne, int st, int ed, int x, int bit){
	//cout << "Q " << ni << "   " << ns << ' ' << ne << "   " << st << ' ' << ed << "   " << x << ' ' << bit << endl;
	if (st > ed){ return 0; }
	if (st <= ns && ne <= ed){ return seg[ni]; }
	if (ne < st || ed < ns){ return 0; }
	bool flg = x & bit;
	int mid = st+ed >> 1, nm = ns+ne >> 1;
	int s1 = st, e1 = min(ed, nm);
	int s2 = max(st, nm+1), e2 = ed;
	if (flg){
		s1 += bit; e1 += bit;
		s2 -= bit; e2 -= bit;
		swap(s1, s2); swap(e1, e2);
	}
	return qry(ni<<1, ns, nm, s1, e1, x, bit>>1)
		 ^ qry(ni<<1|1, nm+1, ne, s2, e2, x, bit>>1);
}
inline ll qry(int st, int ed, int x){ return qry(1, 0, N-1, st, ed, x, N>>1); }

void Main(){
	int n, q; cin >> n;
	for (int i = 0; i < n; i++){ ll x; cin >> x; upd(i, x); }
	cin >> q;
	while (q--){
		int m; cin >> m;
		if (m == 1){
			int st, ed, x; cin >> st >> ed >> x;
			cout << qry(st, ed, x) << endl;
		}
		if (m == 2){
			ll pos, x; cin >> pos >> x;
			upd(pos, x);
		}
	}
}

F. [3176] 도로 네트워크 (Platinum IV)

의도한 태그: Lowest Common Ancestor

\( v \)에서 \( w \)로 가는 경로는 \( v \Rightarrow \text{lca}(v, w) \Rightarrow w \)가 됩니다.

그러니, \( v \Rightarrow \text{lca}(v, w) \)와 \( \text{lca}(v, w) \Leftarrow w \)에서의 답을 구해주면 됩니다.

 

Sparse Table에 (부모 정점, 가장 길었던 간선, 가장 짧았던 간선)을 저장하면

LCA를 구하는 과정에서 문제의 답도 같이 구할 수 있습니다.

vector<pii> v[100020];
piii par[100020][30];
int dp[100020];
bool chk[100020];

void dfs(int now, int dep){
	dp[now] = dep;
	chk[now] = true;
	for (pii nod : v[now]){
		int nxt = nod.fr, dis = nod.sc;
		if (chk[nxt]) continue;
		par[nxt][0] = {now, {dis, dis}};
		dfs(nxt, dep+1);
	}
}

int main(){
	Fast;
	int n;
	cin >> n;
	for (int i = 1; i < n; i++){
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back({y, z});
		v[y].push_back({x, z});
	}
	dfs(1, 0);
	for (int j = 1; j <= 20; j++){
		for (int i = 1; i <= n; i++){
			par[i][j].fr = par[par[i][j-1].fr][j-1].fr;
			par[i][j].sc.fr = max(par[i][j-1].sc.fr, par[par[i][j-1].fr][j-1].sc.fr);
			par[i][j].sc.sc = min(par[i][j-1].sc.sc, par[par[i][j-1].fr][j-1].sc.sc);
		}
	}
	int m;
	cin >> m;
	while (m--){
		int x, y;
		cin >> x >> y;
		int mx = 0, mn = 1e9;
		if (dp[x] > dp[y]){
			int d = dp[x] - dp[y];
			for (int i = 20; i >= 0; i--){
				if (d & (1 << i)){
					mx = max(mx, par[x][i].sc.fr);
					mn = min(mn, par[x][i].sc.sc);
					x = par[x][i].fr;
				}
			}
		}
		if (dp[y] > dp[x]){
			int d = dp[y] - dp[x];
			for (int i = 20; i >= 0; i--){
				if (d & (1 << i)){
					mx = max(mx, par[y][i].sc.fr);
					mn = min(mn, par[y][i].sc.sc);
					y = par[y][i].fr;
				}
			}
		}
		if (x == y){
			cout << mn << ' ' << mx << endl;
			continue;
		}
		for (int i = 20; i >= 0; i--){
			if (par[x][i].fr != par[y][i].fr){
				mx = max(mx, par[x][i].sc.fr);
				mn = min(mn, par[x][i].sc.sc);
				x = par[x][i].fr;
				mx = max(mx, par[y][i].sc.fr);
				mn = min(mn, par[y][i].sc.sc);
				y = par[y][i].fr;
			}
		}
		mx = max(mx, par[x][0].sc.fr);
		mn = min(mn, par[x][0].sc.sc);
		mx = max(mx, par[y][0].sc.fr);
		mn = min(mn, par[y][0].sc.sc);
		cout << mn << ' ' << mx << endl;
	}
}

G. [19550] 빛의 전사 크리퓨어 (Diamond V)

의도한 태그: Sparse Table

원형 쿼리를 관리하는 건 귀찮은 일이니, 선형으로 바꿔봅시다.

그리고 바꾸는 김에, 포함 관계의 두 직선이 생기지 않도록 만들어봅시다.

 

원형 → 선형의 변경은 \( [st, ed] | [st+L, ed+L] \)과 \( [ed, st+L] \) 중 더 짧은 걸로 고르면 되고,

포함 관계의 두 직선은 긴 건 짧은 걸 제거할 때 알아서 제거되므로 짧은 것만 남기면 됩니다.

 

이제, 남은 직선들을 \( st \)를 기준으로 정렬한 뒤, Sparse Table을 통해 답을 구할 수 있습니다. (??)

 

\( SPR_{i, j} = i \)번 구간부터 제거를 시작할 때, \( 2^{j} \)번의 제거 연산 후 남는 구간 중 맨 앞에 있는 구간의 번호, 그리고 cyclic하게 계속 제거할 때 시작 부분을 지난 횟수를 저장해봅시다.

그럼 \( SPR_{i, 0} \)은 \( ed_{i} \)에 빔을 날린 상태가 되고, \( SPR_{i, j-1} \)은 \( SPR_{i, j-1} \)과 \( SPR_{SPR_{i, j-1}, j-1} \)로 구해주면 됩니다.

 

어떤 직선을 제거할 때는, \( ed_{i} \)에 쿼리를 날리면 되고,

이 때 제거되지 않는 직선은 \( ed_{i}+1 \)의 위치로 찾아주면 됩니다.

중간에 점프 뛰는 직선이 있지 않을까 고민될 수 있는데, 포함 관계의 직선을 다 없애줬으니 그런 경우는 없습니다.

 

+ 최종 답은 \( i \)번 직선에서부터 시작해서 1바퀴 돌아오기 위해 필요한 제거 연산의 수를 아까 구한 \( SPR \)을 사용해서 \( 2^{20} \)회부터 시뮬레이션을 돌려주면 됩니다.

const int N = 20;
pi2 spr[200020][22];
set<pl2> chk;
vector<pl2> v;

void Main(){
	int n, l; cin >> n >> l;
	for (int i = 1; i <= n; i++){
		ll st, ed; cin >> st >> ed;
		if (st > ed){ swap(st, ed); }
		ll cnt = ed-st;
		if (cnt*2 >= l){
			v.push_back({ed, st+l});
			//cout << "V " << ed << ' ' << st+l << endl;
		}
		else{
			v.push_back({st, ed}); v.push_back({st+l, ed+l});
			//cout << "V " << st << ' ' << ed << endl;
			//cout << "V " << st+l << ' ' << ed+l << endl;
		}
	}
	sort(all(v), [](pl2 a, pl2 b){
		if (a.fr != b.fr){ return a.fr > b.fr; }
		return a.sc < b.sc;
	});
	vector<pl2> pos;
	ll mn = 1e15; int m = 0;
	for (pl2 p : v){
		if (p.sc >= mn){ continue; }
		mn = min(mn, p.sc);
		if (p.fr < l && p.sc >= l){
			pos.push_back(p); m += 1;
			pos.push_back({p.fr+l, p.sc+l});
		}
		else if (p.fr >= l && p.sc >= l){ chk.insert(p); }
		else{
			if (chk.find({p.fr+l, p.sc+l}) != chk.end()){
				pos.push_back(p); m += 1;
				pos.push_back({p.fr+l, p.sc+l});
			}
		}
	}
	sort(all(pos));
	//for (pl2 p : pos){ cout << "P " << p.fr << ' ' << p.sc << endl; }
	for (int i = 0; i < m; i++){
		pl2 tar = {pos[i].sc+1, 0};
		auto it = lower_bound(all(pos), tar);
		int res = it - pos.begin();
		if (res < m){ spr[i][0] = {res, 0}; }
		else{
			pl2 p = *it; tar = {p.fr-l, p.sc-l};
			it = lower_bound(all(pos), tar);
			spr[i][0] = {it - pos.begin(), 1};
		}
		//cout << "SPR " << i << ' ' << 0 << " = " << spr[i][0].fr << ' ' << spr[i][0].sc << endl;
	}
	for (int j = 1; j <= N; j++){
		for (int i = 0; i < m; i++){
			spr[i][j].fr = spr[ spr[i][j-1].fr ][j-1].fr;
			spr[i][j].sc = spr[i][j-1].sc + spr[ spr[i][j-1].fr ][j-1].sc;
			spr[i][j].sc = min(spr[i][j].sc, 2);
			//cout << "SPR " << i << ' ' << j << " = " << spr[i][j].fr << ' ' << spr[i][j].sc << endl;
		}
	}
	int ans = 1e9;
	for (int i = 0; i < m; i++){
		int res = 0; pi2 p = {i, 0};
		for (int j = N; j >= 0; j--){
			if (p.sc + spr[p.fr][j].sc == 0 ||
				p.sc + spr[p.fr][j].sc == 1 && spr[p.fr][j].fr < i){
					res += 1<<j;
					p.sc += spr[p.fr][j].sc;
					p.fr = spr[p.fr][j].fr;
			}
		}
		ans = min(ans, res+1);
	}
	cout << ans;
}

H. [5446] 용량 부족 (Platinum III)

의도한 태그: Trie

모든 파일명을 가지고 있는 트라이를 구축해봅시다.

이 때, 각 정점에 "지워야 하는 파일이 이 안에 있는지 / 지우지 말아야 하는 파일이 이 안에 있는지" 추가로 저장해봅시다.

 

그럼, 루트 정점에서부터 탐색을 시작해서

어떤 정점에 "지워야 하는 파일"만 있다면, 그 정점에 delete 쿼리를 날려주면 되니, 답에 1을 더하고 탐색을 멈추면 됩니다.

"지우지 말아야 하는 파일만 있다면", 그 정점 및 그 뒤에 나올 정점들은 지우지 말아야 하니 탐색을 멈추면 됩니다.

두 종류의 파일이 모두 있다면, 다음 정점들에게 계산을 맡기면 됩니다.

inline int idx(char c){
	if ('0' <= c && c <= '9'){ return c-'0'; }
	if ('A' <= c && c <= 'Z'){ return c-'A' + 10; }
	if ('a' <= c && c <= 'z'){ return c-'a' + 36; }
	return 62;
}

class Node{ public:
	bool mid, chk;
	bool ed1, ed2;
	int nxt[70];

	Node(){
		mid = chk = 0;
		ed1 = ed2 = 0;
		memset(nxt, -1, sizeof(nxt));
	}
};

vector<Node> v;

void push(string s, int m){
	int sl = s.size();
	int now = 0;
	for (int i = 0; i <= sl; i++){
		if (i == sl){
			if (m == 1){ v[now].ed1 = 1; }
			else{ v[now].ed2 = 1; }
		}
		else{
			if (m == 1){ v[now].mid = 1; }
			else{ v[now].chk = 1; }
			int val = v[now].nxt[ idx(s[i]) ];
			if (val == -1){
				v[now].nxt[ idx(s[i]) ] = v.size();
				v.push_back(Node());
			}
			now = v[now].nxt[ idx(s[i]) ];
		}
	}
}

int ans = 0;

void dfs(int now){
	Node& nod = v[now];
	if (!nod.chk && !nod.ed2){
		ans += (nod.mid | nod.ed1);
		return;
	}
	if (nod.ed1 && (nod.chk || nod.ed2)){
		ans += 1;
	}
	for (int i = 0; i <= 62; i++){
		if (nod.nxt[i] == -1){
			continue;
		}
		dfs(nod.nxt[i]);
	}
}

void Main(){
	int t;
	cin >> t;
	while (t--){
		v.push_back(Node());
		int n;
		cin >> n;
		while (n--){
			string s;
			cin >> s;
			push(s, 1);
		}
		int m;
		cin >> m;
		while (m--){
			string s;
			cin >> s;
			push(s, 2);
		}
		ans = 0;
		dfs(0);
		cout << ans << endl;
		v.clear();
	}
}

I. [14288] 회사 문화 4 (Platinum III)

의도한 태그: Euler Tour Technique

부하직원에게 하는 내리 칭찬은 서브트리에 대한 Update 쿼리이고, 이는 Euler Tour Technique로 구간 쿼리로 변경해준 뒤 처리해주면 됩니다.

그럼 상사에게 하는 내리 칭찬은 어떻게 처리할까요?

 

현재 정점에 저장하는 값이 상사에게 해준 내리 칭찬의 값이라고 해봅시다.

그럼, 어떤 정점이 부하 직원에게 받은 내리 칭찬의 값은, 모든 부하 직원들이 상사에게 해준 칭찬의 총합이 됩니다.

즉, 서브트리의 합 쿼리가 되고, Euler Tour Technique로 구간 쿼리로 변경시켜서 처리해주면 됩니다.

 

그러니, 부하 직원에게 해주는 내리 칭찬과 상사에게 해주는 내리 칭찬을 따로 처리해준 뒤, 출력할 떄만 합해서 출력하면 됩니다.

 

7일차의 "회사 문화 2"와 동일하게, 서브트리의 쿼리는 Difference 배열로 처리했습니다.

vector<int> chl[100020];

pi2 ord[100020]; int cnt;
void dfs(int now){
	cnt += 1; ord[now].fr = cnt;
	for (int nxt : chl[now]){ dfs(nxt); }
	ord[now].sc = cnt;
}

int dir = 0;
const int N = 131072; ll seg[2][262150];
void upd(int pos, int val){ pos += N-1;
	seg[dir][pos] += val; pos >>= 1;
	while (pos){
		seg[dir][pos] = seg[dir][pos<<1] + seg[dir][pos<<1|1]; pos >>= 1;
	}
}
inline void upd(int st, int ed, int val){ upd(st, val); upd(ed+1, -val); }
ll qry(int dir, int st, int ed){ st += N-1; ed += N-1;
	ll res = 0;
	while (st <= ed){
		if (st & 1){ res += seg[dir][st]; st += 1; }
		if (~ed & 1){ res += seg[dir][ed]; ed -= 1; }
		if (st > ed){ break; } st >>= 1; ed >>= 1;
	}
	return res;
}
inline ll qry(int vtx){
	return qry(0, 1, ord[vtx].fr) + qry(1, ord[vtx].fr, ord[vtx].sc);
}

void Main(){
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++){
		int par; cin >> par; if (i > 1){ chl[par].push_back(i); }
	}
	dfs(1);
	while (q--){
		int typ; cin >> typ;
		if (typ == 1){
			int vtx, val; cin >> vtx >> val;
			if (dir == 0){ upd(ord[vtx].fr, ord[vtx].sc, val); }
			else{ upd(ord[vtx].fr, val); }
		}
		if (typ == 2){
			int vtx; cin >> vtx;
			cout << qry(vtx) << endl;
		}
		if (typ == 3){ dir ^= 1; }
	}
}