在 Codeforces 上的提交报了 RE，自己造了一组大数据，结果 gcc 爆了 *** stack smashing detected ***: terminated。

调试发现是线段树的建树爆栈，但我查看了调用栈深度正常。

而且我寻思我线段树在堆空间里啊。。。

求助大佬，悬关

造数据:

#include <bits/extc++.h>

int n = 200000, q = 200000;

int main()
{
	srand48(260403);
	printf("%d %d\n", n, q);
	for (int i = 0; i < n; i++)
		putchar('0' + rand() % 10);
	putchar('\n');
	for (int i = 0; i < q; i++)
		printf("%d %d\n", rand() % n + 1, rand() % n + 1);
	return 0;
}

正文：

#include <bits/extc++.h>

// #define inline	__always_inline
#define INF		1000000000
inline void read(int &x)
{
	char ch;
	for (ch = getchar(); !isdigit(ch); ch = getchar());
	for (x = 0; isdigit(ch); ch = getchar())	x = x * 10 + ch - '0';
}
inline void read(char *str)
{
	for (*str = getchar(); !isdigit(*str); *str = getchar());
	for (*++str = getchar(); isdigit(*str); *++str = getchar());
	*++str = '\0';
}

int n, q;
char str[200001];
int l, r;

struct vector_t
{
	int v[5];
	inline void clear() { memset(v, 0x3f, sizeof(v)); };
	inline int &operator[](int pos) { return v[pos]; }
	inline const int &operator[](int pos) const { return v[pos]; }
};

struct matrix_t
{
	int M[5][5];
	inline void clear() { memset(M, 0x3f, sizeof(M)); };
	inline int *operator[](int pos) { return M[pos]; }
	inline const int *operator[](int pos) const { return M[pos]; }
	inline matrix_t operator*(const matrix_t &m) const
	{
		matrix_t ans; ans.clear();
		for (int i = 0; i < 5; i++)
			for (int k = 0; k < 5; k++)
				for (int j = 0; j < 5; j++)
					ans[i][j] = std::min(ans[i][j], M[i][k] + m[k][j]);
		return ans;
	}
	inline vector_t operator*(const vector_t &v) const
	{
		vector_t ans; ans.clear();
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				ans[i] = std::min(ans[i], M[i][j] + v[j]);
		return ans;
	}
};
matrix_t unit = {{
	{0, INF, INF, INF, INF},
	{INF, 0, INF, INF, INF},
	{INF, INF, 0, INF, INF},
	{INF, INF, INF, 0, INF},
	{INF, INF, INF, INF, 0}
}};

class segment_tree_t
{
public:
	struct segment_t
	{
		int l, r;
		inline int size() const { return r - l; }
		inline int mid() const { return l + r >> 1; }
		inline segment_t left() const { return {l, mid()}; }
		inline segment_t right() const { return {mid(), r}; }
		inline bool in(const segment_t &s) const { return s.l <= l && r <= s.r; }
		inline bool out(const segment_t &s) const { return s.r <= l || r <= s.l; }
	};
	struct node_t
	{
		node_t *left, *right;
		segment_t s;
		matrix_t m;
	};
	node_t *stack, *top, *root;
	segment_tree_t(int size) { top = (stack = root = (node_t *)calloc(size, sizeof(node_t *))) + 1; }
	~segment_tree_t() { free(stack); }
	inline void push_up(node_t *u) const { u->m = u->right->m * u->left->m; }
	void build(node_t *u, const segment_t &s, matrix_t *m)
	{
		u->s = s;
		if (s.size() == 1)
			u->m = m[s.l];
		else
			build(u->right = top++, s.right(), m), build(u->left = top++, s.left(), m), push_up(u);
	}
	matrix_t query(node_t *u, const segment_t &s)
	{
		if (u->s.out(s))
			return unit;
		if (u->s.in(s))
			return u->m;
		return query(u->right, s) * query(u->left, s);
	}
};

segment_tree_t tree(400005);
matrix_t m[200005];

void init()
{
	for (int i = 0; i < n; i++)
	{
		m[i].clear();
		m[i][0][0] = str[i] == '2';
		m[i][1][0] = str[i] == '2' ? 0 : INF; m[i][1][1] = str[i] == '0';
		m[i][2][1] = str[i] == '0' ? 0 : INF; m[i][2][2] = str[i] == '1';
		m[i][3][2] = str[i] == '1' ? 0 : INF; m[i][3][3] = str[i] == '7' || str[i] == '6';
		m[i][4][3] = str[i] == '7' ? 0 : INF; m[i][4][4] = str[i] == '6';
	}
	// for (int i = 0; i < n; i++)
	// 	print(i);
	tree.build(tree.root, {0, n}, m);
}

vector_t origin = {0, INF, INF, INF, INF};
void solve(int l, int r)
{
	vector_t ans = origin;
	matrix_t total = tree.query(tree.root, {l, r + 1});
	ans = total * ans;
	printf("%d\n", ans[4] < INF ? ans[4] : -1);
}

int main()
{
	freopen64("test.in", "r", stdin);
	read(n), read(q);
	read(str);
	init();
	for (int i = 0; i < q; i++)
		read(l), read(r), solve(l - 1, r - 1);
	return 0;
}