关于gcd

处理区间max，min，gcd，and，or

时间复杂度：预处理 $O(n)$，查询 $O(1)$

template <typename T>
class St{
		using VT = vector<T>;
		using VVT = vector<VT>;
		using func_type = function<T(const T &, const T &)>;

		VVT ST;

		static T default_func(const T &t1, const T &t2) {
			return t1 & t2;
		}

		func_type op;

	public:
		St(const vector<T> &v, func_type _func = default_func) {
			op = _func;
			int len = v.size(), l1 = ceil(log2(len)) + 1;
			ST.assign(len, VT(l1, 0));
			for (int i = 0; i < len; ++i) {
				ST[i][0] = v[i];
			}
			for (int j = 1; j < l1; ++j) {
				int pj = (1 << (j - 1));
				for (int i = 0; i + pj < len; ++i) {
					ST[i][j] = op(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
				}
			}
		}

		T query(int l, int r) {
			if (l == r) {
				return ST[l][0];
			}
			int lt = r - l + 1;
			int q = floor(log2(lt));
			return op(ST[l][q], ST[r - (1 << q) + 1][q]);
		}
};

void solve() {
	int n;
	read(n);
	vector<int> nums(n);
	for (int i = 0; i < n; i++) read(nums[i]);
	St<int> st(nums);
	
	cout << st.query(1, 2) << '\n';
}