Language: C++

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <stdexcept>
#include <utility>
#include <vector>

template <::std::size_t Bitlength> class partially_dynamic_wavelet_matrix {
public:
	using value_type = ::std::bitset<Bitlength>;
	using size_type = ::std::size_t;

private:
	class bitvector {
		using bitfield = ::std::uint_least32_t;
		using size_type = typename ::std::vector<bitfield>::size_type;
		static constexpr size_type wordsize = static_cast<size_type>(32);
		static size_type popcount(bitfield c) {
#ifdef __has_builtin
			return static_cast<size_type>(__builtin_popcount(c));
#else
			c = (c & 0x55555555U) + (c >> 1 & 0x55555555U);
			c = (c & 0x33333333U) + (c >> 2 & 0x33333333U);
			c = (c + (c >> 4)) & 0x0F0F0F0FU;
			return static_cast<size_type>(c * 0x01010101U >> 24 & 0x3FU);
#endif
		}
		static size_type c_size(const size_type size) {
			return size / wordsize + static_cast<size_type>(1);
		}

		::std::vector<bitfield> field;
		::std::vector<bitfield> cum_sum;
		::std::vector<bitfield> tree;
		::std::vector<bitfield> enabled;

		size_type base_size() const { return enabled.size(); }

	public:
		size_type sum_0;
		constexpr bitvector() : field(), cum_sum(), tree(), enabled(), sum_0(0) {}
		bitvector(const size_type size)
			: field(c_size(size), static_cast<bitfield>(0)), cum_sum(c_size(size)),
			tree(c_size(size) * static_cast<size_type>(2),
				static_cast<bitfield>(0)),
			enabled(c_size(size), static_cast<bitfield>(0)) {}
		void set_bit(const size_type index) {
			field[index / wordsize] |= static_cast<bitfield>(1) << index % wordsize;
		}
		void build() {
			const size_type len = field.size() - static_cast<size_type>(1);
			cum_sum.front() = static_cast<bitfield>(0);
			for (size_type i = static_cast<size_type>(0); i != len; ++i)
				cum_sum[i + static_cast<size_type>(1)] =
				cum_sum[i] + static_cast<bitfield>(popcount(field[i]));
		}
		size_type rank(const size_type last) const {
			return static_cast<size_type>(cum_sum[last / wordsize]) +
				popcount(field[last / wordsize] &
				(static_cast<bitfield>(1) << last % wordsize) -
					static_cast<bitfield>(1));
		}
		bool operator[](const size_type index) const {
			return field[index / wordsize] >> index % wordsize & 1;
		}
		void set_enable(size_type index) {
			enabled[index / wordsize] |= static_cast<bitfield>(1) << index % wordsize;
			index = index / wordsize + base_size();
			do
				++tree[index];
			while (index /= static_cast<size_type>(2));
		}
		void unset_enable(size_type index) {
			enabled[index / wordsize] &=
				~(static_cast<bitfield>(1) << index % wordsize);
			index = index / wordsize + base_size();
			do
				--tree[index];
			while (index /= static_cast<size_type>(2));
		}
		size_type fold(size_type first, size_type last) const {
			if (first / wordsize == last / wordsize)
				return popcount((enabled[last / wordsize] &
				(static_cast<bitfield>(1) << last % wordsize) -
					static_cast<bitfield>(1)) >>
					first % wordsize);
			size_type ret = popcount(enabled[first / wordsize] >> first % wordsize) +
				popcount(enabled[last / wordsize] &
				(static_cast<bitfield>(1) << last % wordsize) -
					static_cast<bitfield>(1));
			first = first / wordsize + base_size();
			last = last / wordsize + base_size();
			while (first + static_cast<size_type>(1) != last) {
				if (!(first % static_cast<size_type>(2)))
					ret +=
					static_cast<size_type>(tree[first + static_cast<size_type>(1)]);
				first /= static_cast<size_type>(2);
				if (last % static_cast<size_type>(2))
					ret += static_cast<size_type>(tree[last - static_cast<size_type>(1)]);
				last /= static_cast<size_type>(2);
			}
			return ret;
		}
	};
	::std::array<bitvector, Bitlength> matrix;
	size_type size_;

public:
	constexpr partially_dynamic_wavelet_matrix() : matrix(), size_(0) {}
	template <class InputIterator>
	partially_dynamic_wavelet_matrix(InputIterator first, InputIterator last)
		: matrix(), size_(0) {
		::std::vector<value_type> vec0(first, last);
		const size_type len = vec0.size();
		size_ = len;
		::std::vector<value_type> vec_l(len), vec_r(len);
		size_type l, r;
		for (size_type i = Bitlength; i--;) {
			matrix[i] = bitvector(len);
			l = static_cast<size_type>(0);
			r = static_cast<size_type>(0);
			for (size_type j = static_cast<size_type>(0); j < len; ++j) {
				if (vec0[j].test(i)) {
					vec_r[r++] = vec0[j];
					matrix[i].set_bit(j);
				}
				else {
					vec_l[l++] = vec0[j];
				}
			}
			matrix[i].sum_0 = l;
			matrix[i].build();
			::std::swap(vec0, vec_l);
			::std::copy(vec_r.cbegin(), vec_r.cbegin() + r, vec0.begin() + l);
		}
	}

	size_type size() const noexcept { return size_; }
	bool empty() const noexcept { return size() == 0; }

	value_type operator[](size_type index) const {
		assert(index < size());
		value_type ret;
		for (size_type i = Bitlength; i--;) {
			if (matrix[i][index]) {
				index = matrix[i].sum_0 + matrix[i].rank(index);
				ret.set(i);
			}
			else {
				index -= matrix[i].rank(index);
			}
		}
		return ::std::move(ret);
	}
	value_type at(const size_type index) const {
		if (index < size())
			return operator[](index);
		else
			throw ::std::out_of_range("index out of range");
	}

	size_type rank(size_type first, size_type last,
		const value_type &value) const {
		assert(first <= last);
		assert(last <= size());
		for (size_type i = Bitlength; i--; i) {
			if (value.test(i)) {
				first = matrix[i].sum_0 + matrix[i].rank(first);
				last = matrix[i].sum_0 + matrix[i].rank(last);
			}
			else {
				first -= matrix[i].rank(first);
				last -= matrix[i].rank(last);
			}
		}
		return matrix.fold(first, last);
	}
	size_type less_than(size_type first, size_type last,
		const value_type &value) const {
		assert(first <= last);
		assert(last <= size());
		size_type ret = static_cast<size_type>(0);
		for (size_type i = Bitlength; i--;) {
			const size_type first_rank = matrix[i].rank(first);
			const size_type last_rank = matrix[i].rank(last);
			if (value.test(i)) {
				ret += matrix[i].fold(first - first_rank, last - last_rank);
				first = matrix[i].sum_0 + first_rank;
				last = matrix[i].sum_0 + last_rank;
			}
			else {
				first -= first_rank;
				last -= last_rank;
			}
		}
		return ret;
	}
	size_type greater_than(size_type first, size_type last,
		const value_type &value) const {
		assert(first <= last);
		assert(last <= size());
		size_type ret = static_cast<size_type>(0);
		for (size_type i = Bitlength; i--;) {
			const size_type first_rank = matrix[i].rank(first);
			const size_type last_rank = matrix[i].rank(last);
			if (value.test(i)) {
				first = matrix[i].sum_0 + first_rank;
				last = matrix[i].sum_0 + last_rank;
			}
			else {
				ret += matrix[i].fold(matrix[i].sum_0 + first_rank,
					matrix[i].sum_0 last_rank);
				first -= first_rank;
				last -= last_rank;
			}
		}
		return ret;
	}
	value_type quantile(size_type first, size_type last, size_type k,
		const value_type &upper) const {
		assert(first <= last);
		assert(last <= size());
		if (!upper.all())
			k += greater_than(first, last, upper);
		value_type ret;
		for (size_type i = Bitlength; i--;) {
			const size_type first_rank = matrix[i].rank(first);
			const size_type last_rank = matrix[i].rank(last);
			const size_type enabled_rank = matrix[i].fold(
				matrix[i].sum_0 + first_rank, matrix[i].sum_0 + last_rank);
			if (enabled_rank > k) {
				first = matrix[i].sum_0 + first_rank;
				last = matrix[i].sum_0 + last_rank;
				ret.set(i);
			}
			else {
				first -= first_rank;
				last -= last_rank;
				k -= enabled_rank;
			}
		}
		if (matrix.front().fold(first, last) > k)
			return ::std::move(ret);
		else
			throw ::std::out_of_range("out of range");
	}
	value_type rquantile(size_type first, size_type last, size_type k,
		const value_type &lower) const {
		assert(first <= last);
		assert(last <= size());
		if (lower.any())
			k += less_than(first, last, lower);
		value_type ret;
		for (size_type i = Bitlength; i--;) {
			const size_type first_rank = matrix[i].rank(first);
			const size_type last_rank = matrix[i].rank(last);
			const size_type enabled_rank =
				matrix[i].fold(first - first_rank, last - last_rank);
			if (enabled_rank > k) {
				first -= first_rank;
				last -= last_rank;
			}
			else {
				k -= enabled_rank;
				first = matrix[i].sum_0 + first_rank;
				last = matrix[i].sum_0 + last_rank;
				ret.set(i);
			}
		}
		if (matrix.front().fold(first, last) > k)
			return ::std::move(ret);
		else
			throw ::std::out_of_range("out of range");
	}

	void set(size_type index) {
		assert(index < size());
		for (size_type i = Bitlength; i--;) {
			if (matrix[i][index])
				index = matrix[i].sum_0 + matrix[i].rank(index);
			else
				index -= matrix[i].rank(index);
			matrix[i].set_enable(index);
		}
	}
	void unset(size_type index) {
		assert(index < size());
		for (size_type i = Bitlength; i--;) {
			if (matrix[i][index])
				index = matrix[i].sum_0 + matrix[i].rank(index);
			else
				index -= matrix[i].rank(index);
			matrix[i].unset_enable(index);
		}
	}
};

#include<bitset>
#include<iostream>
#include<vector>

struct query {
	int t, x, y;
};

int main() {
	
	static constexpr int Bitlength = 31;

	int n, q;
	::std::cin >> n >> q;
	::std::vector<query> queries(q);
	::std::vector<int> count(n, 1);

	for (auto &e : queries) {
		::std::cin >> e.t >> e.x >> e.y;
		if (e.t == 0)
			++count[e.x];
	}
	count.insert(count.cbegin(), 0);
	for (int i = 0;i < n;++i)
		count[i + 1] += count[i];
	::std::vector<::std::bitset<Bitlength>>
		a(count.back(), ~::std::bitset<Bitlength>(0));
	{
		auto c1 = count;
		for (const auto &e : queries) {
			if (e.t == 0) {
				a[++c1[e.x]] = e.y;
			}
		}
	}

	partially_dynamic_wavelet_matrix<Bitlength> pdwm(a.cbegin(), a.cend());

	for (int i = 0;i < n;++i)
		pdwm.set(count[i]);

	for (const auto &e : queries) {
		if (e.t == 0) {
			pdwm.unset(count[e.x]);
			pdwm.set(++count[e.x]);
		}
		else {
			::std::cout
				<< pdwm.rquantile(count[e.x], count[e.y] + 1, 0, 0).to_ulong()
				<< ::std::endl;
		}
	}

	return 0;
}



Compiler output:
a.cc: In member function 'partially_dynamic_wavelet_matrix<Bitlength>::size_type partially_dynamic_wavelet_matrix<Bitlength>::greater_than(size_type, size_type, const value_type&) const':
a.cc:215:57: error: expected ')' before 'last_rank'
  215 |                                         matrix[i].sum_0 last_rank);
      |                                                         ^~~~~~~~~
a.cc:214:54: note: to match this '('
  214 |                                 ret += matrix[i].fold(matrix[i].sum_0 + first_rank,
      |                                                      ^