API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Mar 24th, 2019
68
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 22.96 KB | None | 0 0
raw download clone embed print report
  1. //██████╗ ██╗ ██╗██╗ ██████╗ ███████╗
  2. //██╔══██╗██║ ██║██║ ██╔══██╗██╔════╝
  3. //██████╔╝██║ ██║██║█████╗██║ ██║█████╗
  4. //██╔══██╗██║ ██║██║╚════╝██║ ██║██╔══╝
  5. //██║ ██║╚██████╔╝██║ ██████╔╝███████╗
  6. //╚═╝ ╚═╝ ╚═════╝ ╚═╝ ╚═════╝ ╚══════╝
  7. #include <bits/stdc++.h>
  8.  
  9. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
  10. #pragma GCC optimize("Ofast")
  11. #pragma GCC optimize("unroll-loops")
  12. using namespace std;
  13.  
  14. #define f first
  15. #define s second
  16. #define mp make_pair
  17. #define mt make_tuple
  18. #define pb push_back
  19. #define eb emplace_back
  20.  
  21. #define all(v) (v).begin(), (v).end()
  22. #define sz(v) ((int)(v).size())
  23. #define sqr(x) ((x) * (x))
  24.  
  25. #define ADD_OPERATORS_IN(T, COMP) \
  26. bool operator < (const T& ot) const { return COMP(ot) == -1; } \
  27. bool operator > (const T& ot) const { return COMP(ot) == 1; } \
  28. bool operator == (const T& ot) const { return COMP(ot) == 0; } \
  29. bool operator != (const T& ot) const { return COMP(ot) != 0; }
  30.  
  31. #define ADD_OPERATORS_OUT(T, COMP) \
  32. bool operator < (const T& a, const T& b) const { return COMP(a, b) == -1; } \
  33. bool operator > (const T& a, const T& b) const { return COMP(a, b) == 1; } \
  34. bool operator == (const T& a, const T&b) const { return COMP(a, b) == 0; } \
  35. bool operator != (const T& a, const T&b) const { return COMP(a, b) != 0; }
  36.  
  37.  
  38. typedef long long ll;
  39. typedef long double ld;
  40. typedef pair <int, int> pii;
  41. typedef pair <ll, ll> pll;
  42. typedef vector<int> vi;
  43.  
  44. #define next ajksdslk
  45. #define prev aklsfjk
  46.  
  47. mt19937_64 mt_rand(chrono::system_clock::now().time_since_epoch().count());
  48.  
  49. template<typename T1, typename T2> inline bool upmax(T1& a, T2 b) { return (a < b ? (a = b, true) : false); }
  50. template<typename T1, typename T2> inline bool upmin(T1& a, T2 b) { return (b < a ? (a = b, true) : false); }
  51.  
  52.  
  53.  
  54. using uint = unsigned int;
  55. // Buffer size should be 2^12 or 2^13 for optimal performance with files.
  56. const uint BUFFER_SIZE = 1 << 12;
  57. // Maximum possible length of a string representing primitive type
  58. // assuming we won't encounter huge double values.
  59. const uint MAX_LENGTH = 1 << 7;
  60.  
  61. namespace Detail {
  62. struct Width { uint value; };
  63. struct Fill { char value; };
  64. struct Base { uint value; };
  65. struct Precision { uint value; };
  66. struct Delimiter { const char* value; };
  67. } // namespace Detail
  68.  
  69. Detail::Width setWidth(uint value = 0) { return {value}; }
  70. Detail::Fill setFill(char value = ' ') { return {value}; }
  71. Detail::Base setBase(uint value = 10) { assert(2 <= value && value <= 36); return {value}; }
  72. Detail::Precision setPrecision(uint value = 9) { assert(value < MAX_LENGTH); return {value}; }
  73. Detail::Delimiter setDelimiter(const char* value = " ") { return {value}; }
  74.  
  75. /*************************************************** input classes ****************************************************/
  76. class InputDevice {
  77. protected:
  78. const char* head;
  79. const char* tail;
  80.  
  81. InputDevice(const char* head, const char* tail) : head(head), tail(tail), base(setBase().value) {}
  82. InputDevice(InputDevice const&) = delete;
  83. InputDevice& operator = (InputDevice const&) = delete;
  84.  
  85. virtual void fillInput() = 0;
  86.  
  87. inline char nextChar() {
  88. if (__builtin_expect(head >= tail, false)) fillInput();
  89. return *head++;
  90. }
  91.  
  92. template <class I> int readUnsignedIntGeneral(I& arg, char c) {
  93. I value = 0;
  94. int length = 0;
  95. for (;; ++length, c = nextChar()) {
  96. if (isDigit(c)) c -= '0';
  97. else if (isUpper(c)) c -= 'A' - 10;
  98. else if (isLower(c)) c -= 'a' - 10;
  99. else c = base;
  100. if (c >= base) break;
  101. value = base * value + c;
  102. }
  103. arg = value;
  104. return --head, length;
  105. }
  106.  
  107. template <class I> inline int readUnsignedInt(I& arg, char c) {
  108. if (__builtin_expect(base > 10, false)) return readUnsignedIntGeneral(arg, c);
  109. I value = 0;
  110. int length = 0;
  111. for (; static_cast<unsigned char>(c - '0') < base; ++length, c = nextChar())
  112. value = base * value + c - '0';
  113. arg = value;
  114. return --head, length;
  115. }
  116.  
  117. template <class I> inline int readSignedInt(I& arg, char c) {
  118. bool negative = c == '-';
  119. if (negative) c = nextChar();
  120. typename make_unsigned<I>::type unsignedArg;
  121. if (readUnsignedInt(unsignedArg, c) == 0) return 0;
  122. arg = negative ? ~static_cast<I>(unsignedArg - 1) : static_cast<I>(unsignedArg);
  123. return 1;
  124. }
  125.  
  126. template <class F> int readFloatingPoint(F& arg, char c) {
  127. bool negative = c == '-';
  128. if (negative) c = nextChar();
  129. unsigned long long integerPart;
  130. if (readUnsignedInt(integerPart, c) == 0) return 0;
  131. if (nextChar() == '.') {
  132. unsigned long long fractionalPart = 0;
  133. int fractionalLength = readUnsignedInt(fractionalPart, nextChar());
  134. if (fractionalLength > 0) {
  135. unsigned long long basePower = 1;
  136. for (; fractionalLength; --fractionalLength) basePower *= base;
  137. arg = static_cast<F>(fractionalPart) / basePower;
  138. }
  139. } else --head;
  140. arg += integerPart;
  141. if (negative) arg = -arg;
  142. return 1;
  143. }
  144.  
  145. public:
  146. static inline bool isSpace(char c) { return static_cast<unsigned char>(c - '\t') < 5 || c == ' '; }
  147. static inline bool isDigit(char c) { return static_cast<unsigned char>(c - '0') < 10; }
  148. static inline bool isUpper(char c) { return static_cast<unsigned char>(c - 'A') < 26; }
  149. static inline bool isLower(char c) { return static_cast<unsigned char>(c - 'a') < 26; }
  150. static inline bool isOneOf(char c, const char* str) { return strchr(str, c) != nullptr; }
  151.  
  152. uint base;
  153. void putBack() { --head; } // can be called only once directly after successfully reading a character
  154.  
  155. inline int readChar(char& arg) {
  156. if (__builtin_expect(head >= tail, false)) {
  157. fillInput();
  158. if (__builtin_expect(head >= tail, false)) return arg = '\0', 0;
  159. }
  160. return arg = *head++, 1;
  161. }
  162.  
  163. template <class UnaryPredicate>
  164. inline char skipCharacters(UnaryPredicate isSkipped) {
  165. char c;
  166. do { c = nextChar(); } while (isSkipped(c));
  167. return c;
  168. }
  169. inline char skipCharacters() { return skipCharacters(isSpace); }
  170.  
  171. template <class UnaryPredicate>
  172. inline int readString(char* arg, int limit, UnaryPredicate isTerminator) {
  173. skipCharacters(isTerminator);
  174. // put back first non-skipped character, reserve space for null character
  175. for (--head, --limit; head < tail; fillInput()) {
  176. ptrdiff_t chunkSize = find_if(head, min(tail, head + limit), isTerminator) - head;
  177. arg = copy_n(head, chunkSize, arg);
  178. head += chunkSize;
  179. limit -= chunkSize;
  180. if (chunkSize == 0 || head < tail) break;
  181. }
  182. return *arg = '\0', 1;
  183. }
  184.  
  185. template <class I> inline int readUnsignedInt(I& arg) { return readUnsignedInt(arg, skipCharacters()) > 0 ? 1 : 0; }
  186. template <class I> inline int readSignedInt(I& arg) { return readSignedInt(arg, skipCharacters()); }
  187. template <class F> inline int readFloatingPoint(F& arg) { return readFloatingPoint(arg, skipCharacters()); }
  188. };
  189.  
  190. class InputFile : public InputDevice {
  191. FILE* file;
  192. bool lineBuffered;
  193. bool owner;
  194. char buffer[BUFFER_SIZE];
  195.  
  196. void fillInput() override {
  197. head = buffer;
  198. *buffer = '\0';
  199. if (__builtin_expect(!lineBuffered, true)) {
  200. tail = head + fread(buffer, 1, BUFFER_SIZE, file);
  201. } else {
  202. tail = head;
  203. if (fgets(buffer, BUFFER_SIZE, file)) while (*tail) ++tail;
  204. }
  205. }
  206.  
  207. public:
  208. InputFile(FILE* file = stdin, bool lineBuffered = true, bool takeOwnership = false)
  209. : InputDevice(buffer, buffer) , file(file), lineBuffered(lineBuffered), owner(takeOwnership) {}
  210. InputFile(const char* fileName) : InputFile(fopen(fileName, "r"), false, true) {}
  211. ~InputFile() { if (owner) fclose(file); }
  212. };
  213.  
  214. // Picks up data appended to the string but doesn't handle reallocation.
  215. class InputString : public InputDevice {
  216. void fillInput() override { while (*tail) ++tail; }
  217.  
  218. public:
  219. InputString(const string& s) : InputDevice(s.data(), s.data() + s.size()) {}
  220. InputString(const char* s) : InputDevice(s, s + strlen(s)) {}
  221. };
  222.  
  223. /*************************************************** output classes ***************************************************/
  224. class OutputDevice {
  225. protected:
  226. char buffer[BUFFER_SIZE + MAX_LENGTH];
  227. char* output;
  228. char* end;
  229. bool separate;
  230.  
  231. OutputDevice() : output(buffer), end(buffer + BUFFER_SIZE + MAX_LENGTH), separate(false), width(setWidth().value)
  232. , fill(setFill().value), base(setBase().value), precision(setPrecision().value), delimiter(setDelimiter().value) {}
  233. OutputDevice(OutputDevice const&) = delete;
  234. OutputDevice& operator = (OutputDevice const&) = delete;
  235.  
  236. virtual void writeToDevice(uint count) = 0;
  237.  
  238. inline void flushMaybe() {
  239. if (__builtin_expect(output >= buffer + BUFFER_SIZE, false)) {
  240. writeToDevice(BUFFER_SIZE);
  241. output = copy(buffer + BUFFER_SIZE, output, buffer);
  242. }
  243. }
  244.  
  245. template <class I> inline char* writeUnsignedInt(I arg, char* last) {
  246. if (__builtin_expect(arg == 0, false)) *--last = '0';
  247. if (__builtin_expect(base == 10, true)) {
  248. for (; arg; arg /= 10) *--last = '0' + arg % 10;
  249. } else for (; arg; arg /= base) {
  250. I digit = arg % base;
  251. *--last = digit < 10 ? '0' + digit : 'A' - 10 + digit;
  252. }
  253. return last;
  254. }
  255.  
  256. template <class I> inline char* writeSignedInt(I arg, char* last) {
  257. auto unsignedArg = static_cast<typename make_unsigned<I>::type>(arg);
  258. if (arg < 0) {
  259. last = writeUnsignedInt(~unsignedArg + 1, last);
  260. *--last = '-';
  261. return last;
  262. }
  263. return writeUnsignedInt(unsignedArg, last);
  264. }
  265.  
  266. template <class F> char* writeFloatingPoint(F arg, char* last) {
  267. bool negative = signbit(arg);
  268. if (negative) arg = -arg;
  269. if (isnan(arg)) for (int i = 0; i < 3; ++i) *--last = i["NaN"];
  270. else if (isinf(arg)) for (int i = 0; i < 3; ++i) *--last = i["fnI"];
  271. else {
  272. auto integerPart = static_cast<unsigned long long>(arg);
  273. arg -= integerPart;
  274. for (int i = 0; i < precision; ++i) arg *= base;
  275. auto fractionalPart = static_cast<unsigned long long>(arg);
  276. if ((arg - fractionalPart) * 2 >= static_cast<F>(1)) {
  277. if (precision == 0) ++integerPart;
  278. else ++fractionalPart;
  279. }
  280. if (precision > 0) {
  281. char* point = last - precision;
  282. last = writeUnsignedInt(fractionalPart, last);
  283. ::fill(point, last, '0');
  284. last = point;
  285. *--last = '.';
  286. }
  287. last = writeUnsignedInt(integerPart, last);
  288. }
  289. if (negative) *--last = '-';
  290. return last;
  291. }
  292.  
  293. inline int writeT(char* first) {
  294. int delimiterLenght = separate ? writeDelimiter() : 0;
  295. separate = true;
  296. int charsWritten = static_cast<int>(end - first);
  297. if (__builtin_expect(charsWritten < width, false))
  298. charsWritten += writeFill(width - charsWritten);
  299. output = copy(first, end, output);
  300. flushMaybe();
  301. return delimiterLenght + charsWritten;
  302. }
  303.  
  304. inline int writeFill(int count) {
  305. int result = count;
  306. if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
  307. if (count == 1) *output++ = fill;
  308. else output = fill_n(output, count, fill);
  309. } else for (uint chunkSize = static_cast<uint>(buffer + BUFFER_SIZE - output);; chunkSize = BUFFER_SIZE) {
  310. if (chunkSize > count) chunkSize = count;
  311. output = fill_n(output, chunkSize, fill);
  312. flushMaybe();
  313. if ((count -= chunkSize) == 0) break;
  314. }
  315. return result;
  316. }
  317.  
  318. public:
  319. int width;
  320. char fill;
  321. uint base;
  322. uint precision;
  323. string delimiter;
  324.  
  325. inline int writeChar(char arg) { separate = false; *output++ = arg; flushMaybe(); return 1; }
  326.  
  327. inline int writeString(const char* arg, int count, bool checkWidth = true) {
  328. separate = false;
  329. int result = count + (checkWidth && count < width ? writeFill(width - count) : 0);
  330. if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
  331. if (count == 1) *output++ = *arg;
  332. else output = copy_n(arg, count, output);
  333. } else for (int chunkSize = static_cast<int>(buffer + BUFFER_SIZE - output);; chunkSize = BUFFER_SIZE) {
  334. if (chunkSize > count) chunkSize = count;
  335. output = copy_n(arg, chunkSize, output);
  336. flushMaybe();
  337. if ((count -= chunkSize) == 0) break;
  338. arg += chunkSize;
  339. }
  340. return result;
  341. }
  342.  
  343. inline int writeDelimiter() { return writeString(delimiter.c_str(), static_cast<int>(delimiter.size()), false); }
  344.  
  345. template <class I> inline int writeUnsignedInt(I arg) { return writeT(writeUnsignedInt(arg, end)); }
  346. template <class I> inline int writeSignedInt(I arg) { return writeT(writeSignedInt(arg, end)); }
  347. template <class F> inline int writeFloatingPoint(F arg) { return writeT(writeFloatingPoint(arg, end)); }
  348.  
  349. inline void flush() {
  350. writeToDevice(static_cast<uint>(output - buffer));
  351. output = buffer;
  352. }
  353. virtual ~OutputDevice() {};
  354. };
  355.  
  356. class OutputFile : public OutputDevice {
  357. FILE* file;
  358. bool owner;
  359.  
  360. void writeToDevice(uint count) override {
  361. fwrite(buffer, 1, count, file);
  362. fflush(file);
  363. }
  364.  
  365. public:
  366. OutputFile(FILE* file = stdout, bool takeOwnership = false) : file(file), owner(takeOwnership) {}
  367. OutputFile(const char* fileName) : OutputFile(fopen(fileName, "w"), true) {}
  368. ~OutputFile() override { flush(); if (owner) fclose(file); }
  369. };
  370.  
  371. class OutputString : public OutputDevice {
  372. string& str;
  373.  
  374. void writeToDevice(uint count) override { str.append(buffer, count); }
  375.  
  376. public:
  377. OutputString(string& str) : OutputDevice(), str(str) {}
  378. ~OutputString() override { flush(); }
  379. };
  380.  
  381. /**************************************************** read & write ****************************************************/
  382. unique_ptr<InputDevice> input;
  383. unique_ptr<OutputDevice> output;
  384.  
  385. // property setters
  386. inline int read(Detail::Base base) { input->base = base.value; return 0; }
  387. // primitive types
  388. inline int read() { return 0; }
  389. inline int read(char& arg) { return input->readChar(arg); }
  390. template <class I> inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
  391. int>::type read(I& arg) { return input->readUnsignedInt(arg); }
  392. template <class I> inline typename enable_if<is_integral<I>::value && is_signed<I>::value,
  393. int>::type read(I& arg) { return input->readSignedInt(arg); }
  394. template <class F> inline typename enable_if<is_floating_point<F>::value,
  395. int>::type read(F& arg) { return input->readFloatingPoint(arg); }
  396. // characters skip
  397. inline int read(const char& arg) { input->skipCharacters([arg](char c) { return arg != c; }); return 0; }
  398. inline int read(const char* arg) {
  399. if (*arg) input->skipCharacters([arg](char c) { return InputDevice::isOneOf(c, arg); });
  400. else input->skipCharacters();
  401. input->putBack(); return 0;
  402. }
  403. inline int read(bool (*isSkipped)(char)) { input->skipCharacters(isSkipped); input->putBack(); return 0; }
  404. // forward declarations so everything compiles
  405. template <class... Ts> int read(char* arg, int limit, bool (*isTerminator)(char), Ts&&... args);
  406. template <class... Ts> int read(char* arg, int limit, const char* terminators, Ts&&... args);
  407. template <class Iterator, class... Ts, typename = decltype(*std::declval<Iterator>())>
  408. int read(Iterator first, Iterator last, Ts&&... args);
  409. template <class Iterator, class... Ts, typename = decltype(*std::declval<Iterator>())>
  410. int read(Iterator first, int count, Ts&&... args);
  411. template <class T, class... Ts, typename = typename enable_if<!is_convertible<T, char*>::value, void>::type>
  412. int read(T&& arg1, Ts&&... args);
  413. // C strings
  414. inline int read(char* arg, int limit, const char* terminators = "") {
  415. if (!*terminators) return input->readString(arg, limit, InputDevice::isSpace);
  416. else return input->readString(arg, limit, [terminators](char c) { return InputDevice::isOneOf(c, terminators); });
  417. }
  418. template <class... Ts>
  419. inline int read(char* first, char* last, Ts&&... args) {
  420. return read(first, static_cast<int>(last - first), forward<Ts>(args)...);
  421. }
  422. template <int N, class... Ts>
  423. inline int read(char (&arg)[N], Ts&&... args) { return read(static_cast<char*>(arg), N, forward<Ts>(args)...); }
  424. template <class... Ts>
  425. inline int read(char* arg, int limit, bool (*isTerminator)(char), Ts&&... args) {
  426. int argsRead = input->readString(arg, limit, isTerminator);
  427. return argsRead + read(forward<Ts>(args)...);
  428. }
  429. template <class... Ts>
  430. inline int read(char* arg, int limit, const char* terminators, Ts&&... args) {
  431. int argsRead = read(arg, limit, terminators);
  432. return argsRead + read(forward<Ts>(args)...);
  433. }
  434. // complex types and ranges
  435. template <class T1, class T2>
  436. inline int read(pair<T1, T2>& arg) { return read(arg.first) == 1 && read(arg.second) == 1 ? 1 : 0; }
  437. template <class T>
  438. inline int read(vector<T>& arg) {
  439. uint n;
  440. if (read(n) == 0) return 0;
  441. arg.resize(n);
  442. return read(arg.begin(), arg.end());
  443. }
  444. template <class Iterator, class... Ts, typename>
  445. int read(Iterator first, Iterator last, Ts&&... args) {
  446. int success = 1;
  447. for (; first != last; ++first) success &= read(*first);
  448. return success + read(forward<Ts>(args)...);
  449. }
  450. template <class Iterator, class... Ts, typename>
  451. int read(Iterator first, int count, Ts&&... args) { return read(first, first + count, forward<Ts>(args)...); }
  452. template <class T, class... Ts, typename>
  453. inline int read(T&& arg1, Ts&&... args) {
  454. int argsRead = read(forward<T>(arg1));
  455. return argsRead + read(forward<Ts>(args)...);
  456. }
  457.  
  458. // property setters
  459. inline int write(Detail::Width width) { output->width = static_cast<int>(width.value); return 0; }
  460. inline int write(Detail::Fill fill) { output->fill = fill.value; return 0; }
  461. inline int write(Detail::Base base) { output->base = base.value; return 0; }
  462. inline int write(Detail::Precision precision) { output->precision = precision.value; return 0; }
  463. inline int write(Detail::Delimiter delimiter) { output->delimiter = delimiter.value; return 0; }
  464. // primitive types
  465. inline int write() { return 0; }
  466. inline int write(char arg) { return output->writeChar(arg); }
  467. template <class I> inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
  468. int>::type write(I arg) { return output->writeUnsignedInt(arg); }
  469. template <class I> inline typename enable_if<is_integral<I>::value && is_signed<I>::value,
  470. int>::type write(I arg) { return output->writeSignedInt(arg); }
  471. template <class F> inline typename enable_if<is_floating_point<F>::value,
  472. int>::type write(F arg) { return output->writeFloatingPoint(arg); }
  473. // complex types
  474. inline int write(const char* arg) { return output->writeString(arg, static_cast<int>(strlen(arg))); }
  475. template <int N>
  476. inline int write(char (&arg)[N]) { return output->writeString(arg, static_cast<int>(strlen(arg))); }
  477. inline int write(const string& arg) { return output->writeString(arg.c_str(), static_cast<int>(arg.size())); }
  478. template <class T1, class T2>
  479. inline int write(const pair<T1, T2>& arg) {
  480. int charsWritten = write(arg.first);
  481. charsWritten += output->writeDelimiter();
  482. return charsWritten + write(arg.second);
  483. }
  484. // forward declarations so everything compiles
  485. template <class Iterator, class... Ts,
  486. typename = typename enable_if<!is_convertible<Iterator, const char*>::value, decltype(*std::declval<Iterator>())>::type>
  487. int write(Iterator first, Iterator last, Ts&&... args);
  488. template <class Iterator, class... Ts,
  489. typename = typename enable_if<!is_convertible<Iterator, const char*>::value, decltype(*std::declval<Iterator>())>::type>
  490. int write(Iterator first, int count, Ts&&... args);
  491. template <class T, class T2, class... Ts> int write(T&& arg, T2&& arg2, Ts&&... args);
  492. // ranges
  493. template <class Iterator, class... Ts, typename>
  494. int write(Iterator first, Iterator last, Ts&&... args) {
  495. int charsWritten = 0;
  496. for (; first != last; charsWritten += ++first == last ? 0 : output->writeDelimiter()) charsWritten += write(*first);
  497. return charsWritten + write(forward<Ts>(args)...);
  498. }
  499. template <class Iterator, class... Ts, typename>
  500. int write(Iterator first, int count, Ts&&... args) { return write(first, first + count, forward<Ts>(args)...); }
  501. template <class T, class T2, class... Ts>
  502. inline int write(T&& arg, T2&& arg2, Ts&&... args) {
  503. int charsWritten = write(forward<T>(arg));
  504. return charsWritten + write(forward<T2>(arg2), forward<Ts>(args)...);
  505. }
  506. template <class... Ts>
  507. inline int writeln(Ts&&... args) { return write(forward<Ts>(args)..., '\n'); }
  508.  
  509. void flush() { output->flush(); }
  510.  
  511.  
  512. const int maxn = (int) 1e6 + 5;
  513. const int maxlog = 21;
  514. const int base = (int) 1e9 + 7;
  515. const ld eps = (ld) 1e-12;
  516. const ld PI = acos(-1.);
  517. //const int pp = 41;
  518. const int inf = 2e9;
  519. const ll llinf = 1e18;
  520.  
  521. #define PR(var) \
  522. cerr << #var << " - " << var <<'\n'; \
  523.  
  524. const int buben = 1550;
  525.  
  526. int n, q;
  527. int a[maxn];
  528. short inc[maxn / buben + 2][maxn];
  529.  
  530. inline void build(int b) {
  531. int l = b * buben, r = (b + 1) * buben - 1;
  532. upmin(r, n - 1);
  533.  
  534. for (int i = r; i >= l; i--)
  535. inc[b][a[i]] = inc[b][a[i] + 1] + 1;
  536. }
  537.  
  538. inline void upd(int x, int y) {
  539. int b = x / buben;
  540. int l = b * buben, r = (b + 1) * buben - 1;
  541. upmin(r, n - 1);
  542.  
  543. for (int i = l; i <= r; i++)
  544. inc[b][a[i]] = 0;
  545.  
  546. a[x] = y;
  547. build(b);
  548. }
  549.  
  550. int main() {
  551. // freopen("input.txt", "r", stdin);
  552. input.reset(new InputFile(stdin, false));
  553. // input.reset(new InputFile("input.txt"));
  554. output.reset(new OutputFile());
  555. // output.reset(new OutputFile("output.txt"));
  556. // ios_base::sync_with_stdio(0);
  557.  
  558. read(n, q);
  559. // return 0;
  560.  
  561. for (int i = 0; i < n; i++) {
  562. read(a[i]);
  563. }
  564.  
  565. for (int i = 0; i <= (n - 1) / buben; i++)
  566. build(i);
  567.  
  568. for (int i = 0; i < q; i++) {
  569. int t;
  570. read(t);
  571. if (t == 1) {
  572. int x, y;
  573. read(x, y);
  574. upd(x, y);
  575. } else {
  576. int l, r, k;
  577. read(l,r , k);
  578. r--;
  579.  
  580. int c = k;
  581.  
  582. if (l / buben == r / buben) {
  583. for (int i = l; i <= r; i++)
  584. if (a[i] == c)
  585. c++;
  586. writeln(c - 1);
  587. } else {
  588. int db = l / buben;
  589. db++;
  590. int nxs = db * buben;
  591.  
  592. for (int i = l; i < nxs; i++)
  593. if (a[i] == c)
  594. c++;
  595.  
  596. int lb = r / buben;
  597. for (int b = db; b < lb; b++) {
  598. c += inc[b][c];
  599. }
  600.  
  601. int prs = lb * buben;
  602. for (int i = prs; i <= r; i++)
  603. if (a[i] == c)
  604. c++;
  605. writeln(c - 1);
  606. }
  607. }
  608. }
  609. return 0;
  610. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!