fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. template <typename T, class Compare = std::less<T>> class RangeMinQuery : private Compare {
  4. 	static const int BUCKET_SIZE = 32;
  5. 	static const int BUCKET_SIZE_LOG = 5;
  6. 	static_assert(BUCKET_SIZE == (1 << BUCKET_SIZE_LOG), "BUCKET_SIZE should be a power of 2");
  7. 	static const int CACHE_LINE_ALIGNMENT = 64;
  8. 	int n = 0;
  9. 	std::vector<T> data;
  10. 	std::vector<T> pref_data;
  11. 	std::vector<T> suff_data;
  12. 	std::vector<T> sparse_table;
  13. 	std::vector<uint32_t> range_mask;
  14.  
  15. private:
  16. 	int num_buckets() const {
  17. 		return n >> BUCKET_SIZE_LOG;
  18. 	}
  19. 	int num_levels() const {
  20. 		return num_buckets() ? 32 - __builtin_clz(num_buckets()) : 0;
  21. 	}
  22. 	int sparse_table_size() const {
  23. 		return num_buckets() * num_levels();
  24. 	}
  25. private:
  26. 	const T& min(const T& a, const T& b) const {
  27. 		return Compare::operator()(a, b) ? a : b;
  28. 	}
  29. 	void setmin(T& a, const T& b) const {
  30. 		if (Compare::operator()(b, a)) a = b;
  31. 	}
  32.  
  33. 	template <typename Vec> static int get_size(const Vec& v) { using std::size; return int(size(v)); }
  34.  
  35. public:
  36. 	RangeMinQuery() {}
  37. 	template <typename Vec> explicit RangeMinQuery(const Vec& data_, const Compare& comp_ = Compare())
  38. 		: Compare(comp_)
  39. 		, n(get_size(data_))
  40. 		, data(n)
  41. 		, pref_data(n)
  42. 		, suff_data(n)
  43. 		, sparse_table(sparse_table_size())
  44. 		, range_mask(n)
  45. 	{
  46. 		for (int i = 0; i < n; i++) data[i] = data_[i];
  47. 		for (int i = 0; i < n; i++) {
  48. 			if (i & (BUCKET_SIZE-1)) {
  49. 				uint32_t m = range_mask[i-1];
  50. 				while (m && !Compare::operator()(data[(i | (BUCKET_SIZE-1)) - __builtin_clz(m)], data[i])) {
  51. 					m -= uint32_t(1) << (BUCKET_SIZE - 1 - __builtin_clz(m));
  52. 				}
  53. 				m |= uint32_t(1) << (i & (BUCKET_SIZE - 1));
  54. 				range_mask[i] = m;
  55. 			} else {
  56. 				range_mask[i] = 1;
  57. 			}
  58. 		}
  59. 		for (int i = 0; i < n; i++) {
  60. 			pref_data[i] = data[i];
  61. 			if (i & (BUCKET_SIZE-1)) {
  62. 				setmin(pref_data[i], pref_data[i-1]);
  63. 			}
  64. 		}
  65. 		for (int i = n-1; i >= 0; i--) {
  66. 			suff_data[i] = data[i];
  67. 			if (i+1 < n && ((i+1) & (BUCKET_SIZE-1))) {
  68. 				setmin(suff_data[i], suff_data[i+1]);
  69. 			}
  70. 		}
  71. 		for (int i = 0; i < num_buckets(); i++) {
  72. 			sparse_table[i] = data[i * BUCKET_SIZE];
  73. 			for (int v = 1; v < BUCKET_SIZE; v++) {
  74. 				setmin(sparse_table[i], data[i * BUCKET_SIZE + v]);
  75. 			}
  76. 		}
  77. 		for (int l = 0; l+1 < num_levels(); l++) {
  78. 			for (int i = 0; i + (1 << (l+1)) <= num_buckets(); i++) {
  79. 				sparse_table[(l+1) * num_buckets() + i] = min(sparse_table[l * num_buckets() + i], sparse_table[l * num_buckets() + i + (1 << l)]);
  80. 			}
  81. 		}
  82. 	}
  83.  
  84. 	T query(int l, int r) const {
  85. 		assert(l <= r);
  86. 		int bucket_l = (l >> BUCKET_SIZE_LOG);
  87. 		int bucket_r = (r >> BUCKET_SIZE_LOG);
  88. 		if (bucket_l == bucket_r) {
  89. 			uint32_t msk = range_mask[r] & ~((uint32_t(1) << (l & (BUCKET_SIZE-1))) - 1);
  90. 			int ind = (l & ~(BUCKET_SIZE-1)) + __builtin_ctz(msk);
  91. 			return data[ind];
  92. 		} else {
  93. 			T ans = min(suff_data[l], pref_data[r]);
  94. 			bucket_l++;
  95. 			if (bucket_l < bucket_r) {
  96. 				int level = (32 - __builtin_clz(bucket_r - bucket_l)) - 1;
  97. 				setmin(ans, sparse_table[level * num_buckets() + bucket_l]);
  98. 				setmin(ans, sparse_table[level * num_buckets() + bucket_r - (1 << level)]);
  99. 			}
  100. 			return ans;
  101. 		}
  102. 	}
  103. };
  104.  
  105. /*
  106.  * This is mostly inspired by https://g...content-available-to-author-only...g.org/src/index/suffixarray/sais.go.
  107.  */
  108.  
  109. template<class T> int sz(T&& arg) { using std::size; return int(size(std::forward<T>(arg))); }
  110.  
  111. class SuffixArray {
  112. public:
  113. 	using index_t = int;
  114. 	int N;
  115. 	std::vector<index_t> sa;
  116. 	std::vector<index_t> rank;
  117. 	// lcp[i] = get_lcp(sa[i], sa[i+1])
  118. 	std::vector<index_t> lcp;
  119. 	RangeMinQuery<std::pair<index_t, index_t>> rmq;
  120.  
  121. 	SuffixArray() {}
  122.  
  123. 	template <typename String> static SuffixArray construct(const String& S) {
  124. 		int N = sz(S);
  125. 		SuffixArray sa(N);
  126.  
  127. 		sa.build_sa(S);
  128. 		sa.build_rank();
  129. 		sa.build_lcp(S);
  130. 		sa.build_rmq();
  131.  
  132. 		return sa;
  133. 	}
  134.  
  135. 	template <typename String, typename F> static SuffixArray map_and_compress(const String& S, const F& f) {
  136. 		std::vector<decltype(f(S[0]))> mapped(sz(S));
  137. 		for (int i = 0; i < sz(S); i++) {
  138. 			mapped[i] = f(S[i]);
  139. 		}
  140. 		return construct(mapped);
  141. 	}
  142.  
  143. 	template <typename String> static SuffixArray compress_and_construct(const String& S) {
  144. 		using std::begin;
  145. 		using std::end;
  146. 		std::vector<decltype(S[0])> vals(begin(S), end(S));
  147. 		std::sort(vals.begin(), vals.end());
  148. 		vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  149. 		std::vector<decltype(S[0])> compressed_s(sz(S));
  150. 		for (int i = 0; i < sz(S); i++) {
  151. 			compressed_s[i] = lower_bound(vals.begin(), vals.end(), S[i]) - vals.begin();
  152. 		}
  153. 		return construct(compressed_s);
  154. 	}
  155.  
  156. 	static SuffixArray construct_lower_alpha(const std::string& s) {
  157. 		return SuffixArray::map_and_compress(s, [](char c) -> char { return char(c - 'a'); });
  158. 	}
  159.  
  160. 	static SuffixArray construct_upper_alpha(const std::string& s) {
  161. 		return SuffixArray::map_and_compress(s, [](char c) -> char { return char(c - 'A'); });
  162. 	}
  163.  
  164. 	index_t get_lcp(index_t a, index_t b) const {
  165. 		if (a == b) return N-a;
  166. 		a = rank[a], b = rank[b];
  167. 		if (a > b) std::swap(a, b);
  168. 		return rmq.query(a, b-1).first;
  169. 	}
  170.  
  171. 	// Get the split in the suffix tree, using half-open intervals
  172. 	// Returns len, idx
  173. 	std::pair<index_t, index_t> get_split(index_t l, index_t r) const {
  174. 		assert(r - l > 1);
  175. 		return rmq.query(l, r-2);
  176. 	}
  177.  
  178. private:
  179. 	explicit SuffixArray(int N_) : N(N_) {}
  180.  
  181. 	template <typename String> void build_sa(const String& S) {
  182. 		sa = std::vector<index_t>(N+1);
  183. 		for (auto s : S) assert(index_t(s) >= 0);
  184. 		int sigma = N ? *max_element(S.begin(), S.end())+1 : 0;
  185. 		std::vector<index_t> tmp(std::max(N, sigma * 2));
  186. 		SuffixArray::sais<String>(N, S, sa.data(), sigma, tmp.data());
  187. 	}
  188.  
  189. 	template <typename String> static void sais(int N, const String& S, index_t* sa, int sigma, index_t* tmp) {
  190. 		if (N == 0) {
  191. 			sa[0] = 0;
  192. 			return;
  193. 		} else if (N == 1) {
  194. 			sa[0] = 1;
  195. 			sa[1] = 0;
  196. 			return;
  197. 		}
  198.  
  199. 		// Phase 1: Initialize the frequency array, which will let us lookup buckets.
  200. 		index_t* freq = tmp; tmp += sigma;
  201. 		memset(freq, 0, sizeof(*freq) * sigma);
  202. 		for (int i = 0; i < N; i++) {
  203. 			++freq[index_t(S[i])];
  204. 		}
  205. 		auto build_bucket_start = [&]() {
  206. 			int cur = 1;
  207. 			for (int v = 0; v < sigma; v++) {
  208. 				tmp[v] = cur;
  209. 				cur += freq[v];
  210. 			}
  211. 		};
  212. 		auto build_bucket_end = [&]() {
  213. 			int cur = 1;
  214. 			for (int v = 0; v < sigma; v++) {
  215. 				cur += freq[v];
  216. 				tmp[v] = cur;
  217. 			}
  218. 		};
  219.  
  220. 		int num_pieces = 0;
  221.  
  222. 		int first_endpoint = 0;
  223. 		// Phase 2: find the right-endpoints of the pieces
  224. 		{
  225. 			build_bucket_end();
  226.  
  227. 			// Initialize the final endpoint out-of-band this way so that we don't try to look up tmp[-1].
  228. 			// This doesn't count towards num_pieces.
  229. 			sa[0] = N;
  230.  
  231. 			index_t c0 = S[N-1], c1 = -1; bool isS = false;
  232. 			for (int i = N-2; i >= 0; i--) {
  233. 				c1 = c0;
  234. 				c0 = S[i];
  235. 				if (c0 < c1) {
  236. 					isS = true;
  237. 				} else if (c0 > c1 && isS) {
  238. 					isS = false;
  239. 					// insert i+1
  240. 					sa[first_endpoint = --tmp[c1]] = i+1;
  241. 					++num_pieces;
  242. 				}
  243. 			}
  244. 		}
  245.  
  246. 		// If num_pieces <= 1, we don't need to actually run the recursion, it's just sorted automatically
  247. 		// Otherwise, we're going to rebucket
  248. 		if (num_pieces > 1) {
  249. 			// Remove the first endpoint, we don't need to run the IS on this
  250. 			sa[first_endpoint] = 0;
  251.  
  252. 			// Run IS for L-type
  253. 			{
  254. 				build_bucket_start();
  255. 				for (int z = 0; z <= N; z++) {
  256. 					int v = sa[z];
  257. 					if (!v) continue;
  258.  
  259. 					// Leave for the S-round
  260. 					if (v < 0) continue;
  261.  
  262. 					// clear out our garbage
  263. 					sa[z] = 0;
  264.  
  265. 					--v;
  266. 					index_t c0 = S[v-1], c1 = S[v];
  267. 					sa[tmp[c1]++] = (c0 < c1) ? ~v : v;
  268. 				}
  269. 			}
  270.  
  271. 			index_t* const sa_end = sa + N + 1;
  272.  
  273. 			index_t* pieces = sa_end;
  274. 			// Run IS for S-type and compactify
  275. 			{
  276. 				build_bucket_end();
  277. 				for (int z = N; z >= 0; z--) {
  278. 					int v = sa[z];
  279. 					if (!v) continue;
  280.  
  281. 					// clear our garbage
  282. 					sa[z] = 0;
  283.  
  284. 					if (v > 0) {
  285. 						*--pieces = v;
  286. 						continue;
  287. 					}
  288.  
  289. 					v = ~v;
  290.  
  291. 					--v;
  292. 					index_t c0 = S[v-1], c1 = S[v];
  293. 					sa[--tmp[c1]] = (c0 > c1) ? v : ~v;
  294. 				}
  295. 			}
  296.  
  297. 			// Compute the lengths of the pieces in preparation for equality
  298. 			// comparison, and store them in sa[v/2]. We set the length of the
  299. 			// final piece to 0; it compares unequal to everything because of
  300. 			// the sentinel.
  301. 			{
  302. 				int prv_start = N;
  303. 				index_t c0 = S[N-1], c1 = -1; bool isS = false;
  304. 				for (int i = N-2; i >= 0; i--) {
  305. 					c1 = c0;
  306. 					c0 = S[i];
  307. 					if (c0 < c1) {
  308. 						isS = true;
  309. 					} else if (c0 > c1 && isS) {
  310. 						isS = false;
  311.  
  312. 						// insert i+1
  313. 						int v = i+1;
  314. 						sa[v>>1] = prv_start == N ? 0 : prv_start - v;
  315. 						prv_start = v;
  316. 					}
  317. 				}
  318. 			}
  319.  
  320. 			// Compute the alphabet, storing the result into sa[v/2].
  321. 			int next_sigma = 0;
  322. 			{
  323. 				int prv_len = -1, prv_v = 0;
  324. 				for (int i = 0; i < num_pieces; i++) {
  325. 					int v = pieces[i];
  326. 					int len = sa[v>>1];
  327.  
  328. 					bool eq = prv_len == len;
  329. 					for (int a = 0; eq && a < len; ++a) {
  330. 						eq = S[v+a] == S[prv_v+a];
  331. 					}
  332. 					if (!eq) {
  333. 						next_sigma++;
  334. 						prv_len = len;
  335. 						prv_v = v;
  336. 					}
  337.  
  338. 					sa[v>>1] = next_sigma; // purposely leave this 1 large to check != 0
  339. 				}
  340. 			}
  341.  
  342. 			if (next_sigma == num_pieces) {
  343. 				sa[0] = N;
  344. 				memcpy(sa+1, pieces, sizeof(*sa) * num_pieces);
  345. 			} else {
  346. 				index_t* next_S = sa_end;
  347.  
  348. 				// Finally, pack the input to the SA
  349. 				{
  350. 					for (int i = (N-1)>>1; i >= 0; i--) {
  351. 						int v = sa[i];
  352. 						if (v) *--next_S = v-1;
  353. 						sa[i] = 0;
  354. 					}
  355. 				}
  356.  
  357. 				memset(sa, 0, sizeof(*sa) * (num_pieces+1));
  358. 				sais<const index_t*>(num_pieces, next_S, sa, next_sigma, tmp);
  359.  
  360. 				{ // Compute the piece start points again and use those to map up the suffix array
  361. 					next_S = sa_end;
  362. 					index_t c0 = S[N-1], c1 = -1; bool isS = false;
  363. 					for (int i = N-2; i >= 0; i--) {
  364. 						c1 = c0;
  365. 						c0 = S[i];
  366. 						if (c0 < c1) {
  367. 							isS = true;
  368. 						} else if (c0 > c1 && isS) {
  369. 							isS = false;
  370.  
  371. 							int v = i+1;
  372. 							*--next_S = v;
  373. 						}
  374. 					}
  375. 					sa[0] = N;
  376. 					for (int i = 1; i <= num_pieces; i++) {
  377. 						sa[i] = next_S[sa[i]];
  378. 					}
  379. 				}
  380. 			}
  381.  
  382. 			// zero everything else
  383. 			memset(sa+num_pieces+1, 0, sizeof(*sa) * (N - num_pieces));
  384.  
  385. 			{
  386. 				// Scatter the finished pieces
  387. 				build_bucket_end();
  388. 				for (int i = num_pieces; i > 0; i--) {
  389. 					int v = sa[i];
  390. 					sa[i] = 0;
  391.  
  392. 					index_t c1 = S[v];
  393. 					sa[--tmp[c1]] = v;
  394. 				}
  395. 			}
  396. 		}
  397.  
  398. 		// Home stretch! Just finish out with the L-type and then S-type
  399. 		{
  400. 			build_bucket_start();
  401. 			for (int z = 0; z <= N; z++) {
  402. 				int v = sa[z];
  403. 				if (v <= 0) continue;
  404. 				--v;
  405. 				index_t c1 = S[v];
  406. 				index_t c0 = v ? S[v-1] : c1; // if v = 0, we don't want to invert
  407. 				sa[tmp[c1]++] = (c0 < c1) ? ~v : v;
  408. 			}
  409. 		}
  410.  
  411. 		// This just aggressively overwrites our original scattered pieces with the correct values
  412. 		{
  413. 			build_bucket_end();
  414. 			for (int z = N; z >= 0; z--) {
  415. 				int v = sa[z];
  416. 				if (v >= 0) continue;
  417. 				sa[z] = v = ~v;
  418. 				--v;
  419. 				index_t c1 = S[v];
  420. 				index_t c0 = v ? S[v-1] : c1+1;
  421. 				sa[--tmp[c1]] = (c0 > c1) ? v : ~v;
  422. 			}
  423. 		}
  424. 	}
  425.  
  426. 	void build_rank() {
  427. 		rank = std::vector<index_t>(N+1);
  428. 		for (int i = 0; i <= N; i++) rank[sa[i]] = i;
  429. 	}
  430.  
  431. 	template <typename String> void build_lcp(const String& S) {
  432. 		assert(sz(S) == N);
  433. 		lcp = std::vector<index_t>(N);
  434. 		for (int i = 0, k = 0; i < N - 1; i++) {
  435. 			int j = sa[rank[i]-1];
  436. 			while (k < N - std::max(i, j) && S[i+k] == S[j+k]) k++;
  437. 			lcp[rank[i]-1] = k;
  438. 			if (k) --k;
  439. 		}
  440. 	}
  441.  
  442. 	void build_rmq() {
  443. 		std::vector<std::pair<index_t, index_t>> lcp_idx(N);
  444. 		for (int i = 0; i < N; i++) {
  445. 			lcp_idx[i] = {lcp[i], i+1};
  446. 		}
  447. 		rmq = RangeMinQuery<std::pair<index_t, index_t>>(std::move(lcp_idx));
  448. 	}
  449. };
  450.  
  451. template <typename T, int NDIMS> struct tensor_view {
  452. 	static_assert(NDIMS >= 0, "NDIMS must be nonnegative");
  453.  
  454. protected:
  455. 	std::array<int, NDIMS> shape;
  456. 	std::array<int, NDIMS> strides;
  457. 	T* data;
  458.  
  459. 	tensor_view(std::array<int, NDIMS> shape_, std::array<int, NDIMS> strides_, T* data_) : shape(shape_), strides(strides_), data(data_) {}
  460.  
  461. public:
  462. 	tensor_view() : shape{0}, strides{0}, data(nullptr) {}
  463.  
  464. protected:
  465. 	int flatten_index(std::array<int, NDIMS> idx) const {
  466. 		int res = 0;
  467. 		for (int i = 0; i < NDIMS; i++) { res += idx[i] * strides[i]; }
  468. 		return res;
  469. 	}
  470. 	int flatten_index_checked(std::array<int, NDIMS> idx) const {
  471. 		int res = 0;
  472. 		for (int i = 0; i < NDIMS; i++) {
  473. 			assert(0 <= idx[i] && idx[i] < shape[i]);
  474. 			res += idx[i] * strides[i];
  475. 		}
  476. 		return res;
  477. 	}
  478.  
  479. public:
  480. 	T& operator[] (std::array<int, NDIMS> idx) const {
  481. 		return data[flatten_index(idx)];
  482. 	}
  483. 	T& at(std::array<int, NDIMS> idx) const {
  484. 		return data[flatten_index_checked(idx)];
  485. 	}
  486.  
  487. 	template <int D = NDIMS>
  488. 	typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[] (int idx) const {
  489. 		std::array<int, NDIMS-1> nshape; std::copy(shape.begin()+1, shape.end(), nshape.begin());
  490. 		std::array<int, NDIMS-1> nstrides; std::copy(strides.begin()+1, strides.end(), nstrides.begin());
  491. 		T* ndata = data + (strides[0] * idx);
  492. 		return tensor_view<T, NDIMS-1>(nshape, nstrides, ndata);
  493. 	}
  494. 	template <int D = NDIMS>
  495. 	typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) const {
  496. 		assert(0 <= idx && idx < shape[0]);
  497. 		return operator[](idx);
  498. 	}
  499.  
  500. 	template <int D = NDIMS>
  501. 	typename std::enable_if<(0 == D), T&>::type operator * () const {
  502. 		return *data;
  503. 	}
  504.  
  505. 	template <typename U, int D> friend struct tensor_view;
  506. 	template <typename U, int D> friend struct tensor;
  507. };
  508.  
  509. template <typename T, int NDIMS> struct tensor {
  510. 	static_assert(NDIMS >= 0, "NDIMS must be nonnegative");
  511.  
  512. protected:
  513. 	std::array<int, NDIMS> shape;
  514. 	std::array<int, NDIMS> strides;
  515. 	int len;
  516. 	T* data;
  517.  
  518. public:
  519. 	tensor() : shape{0}, strides{0}, len(0), data(nullptr) {}
  520.  
  521. 	explicit tensor(std::array<int, NDIMS> shape_, const T& t = T()) {
  522. 		shape = shape_;
  523. 		strides[NDIMS-1] = 1;
  524. 		for (int i = NDIMS-1; i > 0; i--) {
  525. 			strides[i-1] = strides[i] * shape[i];
  526. 		}
  527. 		len = strides[0] * shape[0];
  528. 		data = new T[len];
  529. 		std::fill(data, data + len, t);
  530. 	}
  531.  
  532. 	tensor(const tensor& o) : shape(o.shape), strides(o.strides), len(o.len), data(new T[len]) {
  533. 		for (int i = 0; i < len; i++) {
  534. 			data[i] = o.data[i];
  535. 		}
  536. 	}
  537.  
  538. 	tensor& operator=(tensor&& o) noexcept {
  539. 		using std::swap;
  540. 		swap(shape, o.shape);
  541. 		swap(strides, o.strides);
  542. 		swap(len, o.len);
  543. 		swap(data, o.data);
  544. 		return *this;
  545. 	}
  546. 	tensor(tensor&& o) : tensor() {
  547. 		*this = std::move(o);
  548. 	}
  549. 	tensor& operator=(const tensor& o) {
  550. 		return *this = tensor(o);
  551. 	}
  552. 	~tensor() { delete[] data; }
  553.  
  554. 	using view_t = tensor_view<T, NDIMS>;
  555. 	view_t view() {
  556. 		return tensor_view<T, NDIMS>(shape, strides, data);
  557. 	}
  558. 	operator view_t() {
  559. 		return view();
  560. 	}
  561.  
  562. 	using const_view_t = tensor_view<const T, NDIMS>;
  563. 	const_view_t view() const {
  564. 		return tensor_view<const T, NDIMS>(shape, strides, data);
  565. 	}
  566. 	operator const_view_t() const {
  567. 		return view();
  568. 	}
  569.  
  570. 	T& operator[] (std::array<int, NDIMS> idx) { return view()[idx]; }
  571. 	T& at(std::array<int, NDIMS> idx) { return view().at(idx); }
  572. 	const T& operator[] (std::array<int, NDIMS> idx) const { return view()[idx]; }
  573. 	const T& at(std::array<int, NDIMS> idx) const { return view().at(idx); }
  574.  
  575. 	template <int D = NDIMS>
  576. 	typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[] (int idx) {
  577. 		return view()[idx];
  578. 	}
  579. 	template <int D = NDIMS>
  580. 	typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) {
  581. 		return view().at(idx);
  582. 	}
  583.  
  584. 	template <int D = NDIMS>
  585. 	typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type operator[] (int idx) const {
  586. 		return view()[idx];
  587. 	}
  588. 	template <int D = NDIMS>
  589. 	typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type at(int idx) const {
  590. 		return view().at(idx);
  591. 	}
  592.  
  593. 	template <int D = NDIMS>
  594. 	typename std::enable_if<(0 == D), T&>::type operator * () {
  595. 		return *view();
  596. 	}
  597. 	template <int D = NDIMS>
  598. 	typename std::enable_if<(0 == D), const T&>::type operator * () const {
  599. 		return *view();
  600. 	}
  601. };
  602.  
  603. int main() {
  604. 	using namespace std;
  605. 	ios_base::sync_with_stdio(false), cin.tie(nullptr);
  606. 	int T; cin >> T;
  607. 	while (T--) {
  608. 		int N, M, K; cin >> N >> M >> K;
  609. 		string A, B; cin >> A >> B;
  610. 		SuffixArray sa = SuffixArray::construct_lower_alpha(A + char('z' + 1) + B);
  611. 		tensor<array<int, 2>, 2> best_loc({K+1,2*K+1}, {-1,-1});
  612. 		tensor<int, 2> prv({K+1,2*K+1}, -1);
  613. 		best_loc[{0,0}] = {0,0};
  614. 		for (int k = 0; k <= K; k++) {
  615. 			for (int i = 0; i <= 2*k; i++) {
  616. 				int a = best_loc[{k,i}][0], b = best_loc[{k,i}][1];
  617. 				if (a == -1 && b == -1) continue;
  618.  
  619. 				int jmp = sa.get_lcp(a, N + 1 + b);
  620. 				a += jmp, b += jmp;
  621. 				if (a == N && b == M) {
  622. 					cout << "YES" << '\n';
  623. 					cout << k << '\n';
  624. 					for (int cur_k = k, cur_i = i; cur_k != 0; cur_i = prv[{cur_k, cur_i}], cur_k--) {
  625. 						int d = cur_i - prv[{cur_k, cur_i}];
  626. 						int a = best_loc[{cur_k, cur_i}][0], b = best_loc[{cur_k, cur_i}][1];
  627. 						if (d == 0) {
  628. 							// we incremented a by 1; delete from this position
  629. 							cout << "DELETE " << a << '\n';
  630. 						} else if (d == 1) {
  631. 							cout << "REPLACE " << a << ' ' << B[b-1] << '\n';
  632. 						} else if (d == 2) {
  633. 							cout << "INSERT " << a+1 << ' ' << B[b-1] << '\n';
  634. 						} else assert(false);
  635. 					}
  636. 					goto found;
  637. 				}
  638. 				if (k == K) continue;
  639. 				if (a < N) {
  640. 					// we can increment a by 1, and i by 0
  641. 					array<int, 2> cnd{a+1, b};
  642. 					if (cnd > best_loc[{k+1, i+0}]) {
  643. 						best_loc[{k+1,i+0}] = cnd;
  644. 						prv[{k+1, i+0}] = i;
  645. 					}
  646. 				}
  647. 				if (b < M) {
  648. 					// we can increment b by 1, and i by 2
  649. 					array<int, 2> cnd{a, b+1};
  650. 					if (cnd > best_loc[{k+1, i+2}]) {
  651. 						best_loc[{k+1,i+2}] = cnd;
  652. 						prv[{k+1, i+2}] = i;
  653. 					}
  654. 				}
  655. 				if (a < N && b < M) {
  656. 					// we can increment both by 1.
  657. 					array<int, 2> cnd{a+1, b+1};
  658. 					if (cnd > best_loc[{k+1, i+1}]) {
  659. 						best_loc[{k+1,i+1}] = cnd;
  660. 						prv[{k+1, i+1}] = i;
  661. 					}
  662. 				}
  663. 			}
  664. 		}
  665. 		cout << "NO" << '\n';
  666. found:;
  667. 	}
  668.  
  669. 	return 0;
  670. }
  671.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
2
3 4 3
kot
plot
5 7 3
zycie
porazka
compilation info 
prog.cpp: In static member function ‘static int RangeMinQuery<T, Compare>::get_size(const Vec&)’:
prog.cpp:33:73: error: ‘std::size’ has not been declared
  template <typename Vec> static int get_size(const Vec& v) { using std::size; return int(size(v)); }
                                                                         ^~~~
prog.cpp: In function ‘int sz(T&&)’:
prog.cpp:109:48: error: ‘std::size’ has not been declared
 template<class T> int sz(T&& arg) { using std::size; return int(size(std::forward<T>(arg))); }
                                                ^~~~
prog.cpp: In instantiation of ‘int sz(T&&) [with T = const std::__cxx11::basic_string<char>&]’:
prog.cpp:136:43:   required from ‘static SuffixArray SuffixArray::map_and_compress(const String&, const F&) [with String = std::__cxx11::basic_string<char>; F = SuffixArray::construct_lower_alpha(const string&)::<lambda(char)>]’
prog.cpp:157:87:   required from here
prog.cpp:109:69: error: ‘size’ was not declared in this scope
 template<class T> int sz(T&& arg) { using std::size; return int(size(std::forward<T>(arg))); }
                                                                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
prog.cpp:109:69: note: suggested alternative: ‘sz’
 template<class T> int sz(T&& arg) { using std::size; return int(size(std::forward<T>(arg))); }
                                                                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
                                                                 sz
prog.cpp: In instantiation of ‘static int RangeMinQuery<T, Compare>::get_size(const Vec&) [with Vec = std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >; T = std::pair<int, int>; Compare = std::less<std::pair<int, int> >]’:
prog.cpp:39:15:   required from ‘RangeMinQuery<T, Compare>::RangeMinQuery(const Vec&, const Compare&) [with Vec = std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >; T = std::pair<int, int>; Compare = std::less<std::pair<int, int> >]’
prog.cpp:447:70:   required from here
prog.cpp:33:94: error: ‘size’ was not declared in this scope
  template <typename Vec> static int get_size(const Vec& v) { using std::size; return int(size(v)); }
                                                                                          ~~~~^~~
prog.cpp:33:94: note: suggested alternative: ‘sz’
  template <typename Vec> static int get_size(const Vec& v) { using std::size; return int(size(v)); }
                                                                                          ~~~~^~~
                                                                                          sz
prog.cpp: In instantiation of ‘int sz(T&&) [with T = const std::vector<char, std::allocator<char> >&]’:
prog.cpp:124:13:   required from ‘static SuffixArray SuffixArray::construct(const String&) [with String = std::vector<char, std::allocator<char> >]’
prog.cpp:140:19:   required from ‘static SuffixArray SuffixArray::map_and_compress(const String&, const F&) [with String = std::__cxx11::basic_string<char>; F = SuffixArray::construct_lower_alpha(const string&)::<lambda(char)>]’
prog.cpp:157:87:   required from here
prog.cpp:109:69: error: ‘size’ was not declared in this scope
 template<class T> int sz(T&& arg) { using std::size; return int(size(std::forward<T>(arg))); }
                                                                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
prog.cpp:109:69: note: suggested alternative: ‘sz’
 template<class T> int sz(T&& arg) { using std::size; return int(size(std::forward<T>(arg))); }
                                                                 ~~~~^~~~~~~~~~~~~~~~~~~~~~
                                                                 sz
stdout
copy 
Standard output is empty
https://ideone.com/karLpl
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!