RT，为什么线段树堆式建树开 4 倍空间 RE 但是八倍空间 AC？

#include<bits/stdc++.h>
using namespace std;
#define ll long long
template <class T> inline void read(T &x)
{
	x = 0;
	int f = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		f |= ch == '-';
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + (ch - 48);
		ch = getchar();
	}
	x = f ? -x : x;
	return;
}
#define N 100005
int n, m, q, a[N], b[N];
struct node
{
	int l, r, val, tag;
};
node tree[N << 3];
inline void pushup(int root)
{
	tree[root].val = tree[root << 1].val + tree[root << 1 | 1].val;
	return;
}
inline void addtag(int root, int v)
{
	tree[root].tag = v;
	tree[root].val = v * (tree[root].r - tree[root].l + 1);
	return;
}
inline void pushdown(int root)
{
	if(tree[root].tag != -1)
	{
		addtag(root << 1, tree[root].tag), addtag(root << 1 | 1, tree[root].tag);
		tree[root].tag = -1;
	}
	return;
}
void build(int root, int l, int r)
{
	tree[root].l = l, tree[root].r = r;
	tree[root].tag = -1;
	if(l == r)
	{
		tree[root].val = b[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(root << 1, l, mid), build(root << 1 | 1, mid + 1, r);
	pushup(root);
	return;
}
void update(int root, int L, int R, int v)
{
	if(L <= tree[root].l && tree[root].r <= R)
	{
		addtag(root, v);
		return;
	}
	pushdown(root);
	int mid = (tree[root].l + tree[root].r) >> 1;
	if(L <= mid)
	{
		update(root << 1, L, R, v);
	}
	if(mid < R)
	{
		update(root << 1 | 1, L, R, v);
	}
	pushup(root);
	return;
}
int query(int root, int L, int R)
{
	if(L <= tree[root].l && tree[root].r <= R)
	{
		return tree[root].val;
	}
	pushdown(root);
	int mid = (tree[root].l + tree[root].r) >> 1, ret = 0;
	if(L <= mid)
	{
		ret += query(root << 1, L, R);
	}
	if(mid < R)
	{
		ret += query(root << 1 | 1, L, R);
	}
	return ret;
}
int typ[N];
pair<int, int> opt[N];
bool check(int x)
{
	for(int i = 1; i <= n; i++)
	{
		b[i] = (a[i] >= x);
	}
	build(1, 1, n);
	for(int i = 1; i <= m; i++)
	{
		int num = query(1, opt[i].first, opt[i].second);
		if(!typ[i])
		{
			update(1, opt[i].first, opt[i].second - num, 0);
			update(1, opt[i].second - num + 1, opt[i].second, 1);
		}
		else
		{
			update(1, opt[i].first, opt[i].first + num - 1, 1);
			update(1, opt[i].first + num, opt[i].second, 0);
		}
	}
	return (query(1, q, q) == 1);
}
signed main()
{
	read(n), read(m);
	for(int i = 1; i <= n; i++)
	{
		read(a[i]);
	}
	for(int i = 1; i <= m; i++)
	{
		read(typ[i]), read(opt[i].first), read(opt[i].second);
	}
	read(q);
	int l = 1, r = n, mid;
	while(l < r)
	{
		mid = (l + r + 1) >> 1;
		if(check(mid))
		{
			l = mid;
		}
		else
		{
			r = mid - 1;
		}
	}
	printf("%d", l);
	return 0;
}