Language: C++

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <utility>
#include <vector>

template <typename T, size_t bitsize> class WaveletMatrix {
public:
	using value_type = T;
	using size_type = std::size_t;

private:
	using uint64 = std::uint_fast64_t;
	static size_type popcount64(uint64 c) {
#ifdef __GNUC__
		return __builtin_popcountll(c);
#elif _MSC_VER_
		return _mm_popcnt_u64(c);
#else
		c = (c & 0x5555555555555555ULL) + ((c >> 1) & 0x5555555555555555ULL);
		c = (c & 0x3333333333333333ULL) + ((c >> 2) & 0x3333333333333333ULL);
		c = (c + (c >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
		c += c >> 8;
		c += c >> 16;
		c += c >> 32;
		return static_cast<size_type>(c) & 0x7F;
#endif
	}
	struct FID {
		std::vector<uint64> dic;
		size_type cnt;
		value_type bit;
		FID() {}
		FID(const size_type &bsize) : dic(bsize, 0) {}
		void set(const size_type &index) {
			dic[index >> 5 | 1] |= static_cast<uint64>(1) << (index & 0x3f);
		}
		void build() {
			const size_type &len = dic.size();
			for (size_type j = 2; j < len; j += 2)
				dic[j] = dic[j - 2] + popcount64(dic[j - 1]);
		}
		size_type rank(const size_type &index) const {
			return static_cast<size_type>(
				dic[index >> 5 & ~static_cast<size_type>(1)]) +
				popcount64(dic[index >> 5 | 1] &
				(static_cast<size_type>(1) << (index & 0x3f)) - 1);
		}
		bool access(const size_type &index) const {
			return dic[index >> 5 | 1] >> (index & 0x3f) & 1;
		}
	};
	std::array<FID, bitsize> matrix;

public:
	WaveletMatrix(std::vector<value_type> data) {
		const size_type &len = data.size(), block = ((len >> 6) + 1) << 1;
		std::vector<value_type> L(len), R(len);
		size_type l, r;
		value_type temp = static_cast<value_type>(1) << (bitsize - 1);
		for (auto &x=matrix) {
			x = FID(block);
			x.bit = temp;
			temp >>= 1;
			l = 0;
			r = 0;
			for (size_type j = 0; j < len; ++j)
				if (data[j] &x.bit)
					R[r++] = data[j], x.set(j);
				else
					L[l++] = data[j];
			x.cnt = l;
			x.build();
			std::swap(data, L);
			std::copy(R.begin(), R.begin() + r, data.begin() + l);
		}
	}
	T operator[](size_type index) const {
		T ret = 0;
		for (const auto &x : matrix)
			if (x.access(index))
				ret |= x.bit, index = x.rank(index) + x.cnt;
			else
				index -= x.rank(index);
		return ret;
	}
	T rank(size_type begin, size_type end, const T data) const {
		for (const auto &x : matrix)
			if (data & x.bit)
				begin = x.rank(begin) + x.cnt, end = x.rank(end) + x.cnt;
			else
				begin -= x.rank(begin), end -= x.rank(end);
		return end - begin;
	}
	T quantile(size_type begin, size_type end, size_type k) const {
		T ret = 0;
		for (const auto &x : matrix) {
			if (x.rank(end) - x.rank(begin) > k)
				begin = x.rank(begin) + x.cnt, end = x.rank(end) + x.cnt, ret |= x.bit;
			else
				k -= x.rank(end) - x.rank(begin),begin -= x.rank(begin), end -= x.rank(end) ;
		}
		return ret;
	}
	T rquantile(const size_type &begin,const size_type &end, size_type k) const {
		return quantile(begin, end, end - begin - k - 1);
	}
	size_type less_than(size_type begin, size_type end, const T data) const {
		size_type ret = 0;
		for (const auto &x : matrix) {
			if (data & x.bit) {
				ret += end - begin + x.rank(begin) - x.rank(end);
				begin = x.rank(begin) + x.cnt;
				end = x.rank(end) + x.cnt;
			}
			else {
				begin -= x.rank(begin);
				end -= x.rank(end);
			}
		}
		return ret + end - begin;
	}
	size_type more_than(size_type begin, size_type end, const T data) const {
		size_type ret = 0;
		for (const auto &x : matrix) {
			if (data & x.bit) {
				begin = x.rank(begin) + x.cnt;
				end = x.rank(end) + x.cnt;
			}
			else {
				ret += x.rank(end) - x.rank(begin);
				begin -= x.rank(begin);
				end -= x.rank(end);
			}
		}
		return ret;
	}
	size_type rangefreq(size_type begin, size_type end, const T lower,
		const T upper) const {
		return end - begin - less_than(begin, end, lower) -
			more_than(begin, end, upper);
	}
};

#include<cstdio>
#include<vector>
int main() {
	int n, l;
	scanf("%d %d", &n, &l);
	std::vector<int> a(n);
	for (auto &x : a)scanf("%d", &x);
	WaveletMatrix<int, 30> W(a);
	for (int i = 0;i <= n - l;++i)
		printf("%d%c", W.quantile(i, i + l, l-1), " \n"[i == n - l]);
	return 0;
}


Compiler output:
a.cc: In constructor 'WaveletMatrix<T, bitsize>::WaveletMatrix(std::vector<T>)':
a.cc:63:36: error: expected ';' before ')' token
   63 |                 for (auto &x=matrix) {
      |                                    ^
a.cc:63:36: error: expected primary-expression before ')' token
a.cc:63:36: error: expected ';' before ')' token
a.cc: In instantiation of 'WaveletMatrix<T, bitsize>::WaveletMatrix(std::vector<T>) [with T = int; long unsigned int bitsize = 30]':
a.cc:154:28:   required from here
  154 |         WaveletMatrix<int, 30> W(a);
      |                                   ^
a.cc:64:27: error: no match for 'operator=' (operand types are 'std::array<WaveletMatrix<int, 30>::FID, 30>' and 'WaveletMatrix<int, 30>::FID')
   64 |                         x = FID(block);
      |                         ~~^~~~~~~~~~~~
In file included from a.cc:3:
/usr/include/c++/14/array:100:12: note: candidate: 'std::array<WaveletMatrix<int, 30>::FID, 30>& std::array<WaveletMatrix<int, 30>::FID, 30>::operator=(const std::array<WaveletMatrix<int, 30>::FID, 30>&)'
  100 |     struct array
      |            ^~~~~
/usr/include/c++/14/array:100:12: note:   no known conversion for argument 1 from 'WaveletMatrix<int, 30>::FID' to 'const std::array<WaveletMatrix<int, 30>::FID, 30>&'
/usr/include/c++/14/array:100:12: note: candidate: 'std::array<WaveletMatrix<int, 30>::FID, 30>& std::array<WaveletMatrix<int, 30>::FID, 30>::operator=(std::array<WaveletMatrix<int, 30>::FID, 30>&&)'
/usr/include/c++/14/array:100:12: note:   no known conversion for argument 1 from 'WaveletMatrix<int, 30>::FID' to 'std::array<WaveletMatrix<int, 30>::FID, 30>&&'
a.cc:65:27: error: 'struct std::array<WaveletMatrix<int, 30>::FID, 30>' has no member named 'bit'
   65 |                         x.bit = temp;
      |                         ~~^~~
a.cc:70:48: error: 'struct std::array<WaveletMatrix<int, 30>::FID, 30>' has no member named 'bit'
   70 |                                 if (data[j] &x.bit)
      |                                              ~~^~~
a.cc:71:61: error: 'struct std::array<WaveletMatrix<int, 30>::FID, 30>' has no member named 'set'
   71 |                                         R[r++] = data[j], x.set(j);
      |                                                           ~~^~~
a.cc:74:27: error: 'struct std::array<WaveletMatrix<int, 30>::FID, 30>' has no member named 'cnt'
   74 |                         x.cnt = l;
      |                         ~~^~~
a.cc:75:27: error: 'struct std::array<WaveletMatrix<int, 30>::FID, 30>' has no member named 'build'
   75 |                         x.build();
      |                         ~~^~~~~