RT,P7466 喜提4pts剩下一堆RE和TLE求条

#include<bits/stdc++.h>

//#define INF 2147483647
#define HDF_LOVES_YDMY 1

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
} 

using namespace IO;
using namespace std;

const int maxn = 4e5 + 500;
const int qmaxn = 500 + 5;

int n, m;
int a[maxn], L[qmaxn], R[qmaxn], num[maxn], f[maxn], lazy[maxn], lastans;

void init() {
	int x = sqrt(n);

    for (int i = 1;i <= x;i++) {
        L[i] = (i - 1) * x + 1;
        R[i] = i * x;
        for (int j = L[i];j <= R[i];j++) {
            num[j] = i;
            f[j] = (a[j] < L[i]) ? a[j] : f[a[j]];
        }
    }

    if (R[x] != n) {
        x++;
        L[x] = R[x - 1] + 1;
        R[x] = n;
        for (int i = L[x];i <= R[x];i++) {
            num[i] = x;
            f[i] = (a[i] < L[x]) ? a[i] : f[a[i]];
        }
    }

    return;
}

void renewf(int l, int r) {
	for (int i = l;i <= r;i++) {
		int fa = max(a[i] - lazy[num[i]], 1);
		(fa < L[num[i]]) ? f[i] = fa : f[i] = f[fa];
	}

	return;
}

void update(int l, int r, int x) {
    int lk = num[l], rk = num[r];

	if (lk == rk) {
		for (int i = l;i <= r;i++) a[i] -= x;
		renewf(l, r);	
		return;
	} 

	for (int i = l;i <= R[lk];i++) a[i] -= x;

	for (int i = lk + 1;i < rk;i++) lazy[i] += x;

	for (int i = L[rk];i <= r;i++) a[i] -= x;
	
	renewf(l, r);
	
	return; 
}

int query(int x, int y) {
	int xk, yk;
	
	while (HDF_LOVES_YDMY) { 
		
		if (x == y) return x;
		if (a[y] == x) return x;
		if (a[x] == y) return y;
	
		xk = num[x], yk = num[y];
		
		renewf(min(x, y) - sqrt(n) - 1, max(x, y));
		
		if (xk != yk) (xk < yk) ? y = f[y] : x = f[x];
		else {
			if (f[x] == f[y]) {
				while (HDF_LOVES_YDMY) {
					int ax = max(a[x] - lazy[xk], 1), ay = max(a[y] - lazy[yk], 1);
					if (ax == ay) return ax;
					else if (ax < ay) y = a[y];
					else x = a[x];
				}
			}
			else x = f[x], y = f[y];
		}
	} 
}

int main() {
	n = read(), m = read();
	a[1] = 1;f[1] = 1;
	for (int i = 2;i <= n;i++) a[i] = read();
	
	init();
	
	while (m--) {
		int op = read(), j = read(), k = read(), l;
		if (op == 1) l = read(), update(j ^ lastans, k ^ lastans, l ^ lastans);
		else lastans = query(j ^ lastans, k ^ lastans), write(lastans), puts("");
	}
	
	return 0;
}