Advertisement
Guest User

Untitled

a guest
May 21st, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.83 KB | None | 0 0
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. template<typename T = int>
  8. struct SqrtDecomp2 {
  9.     vector<T> blocks;
  10.     vector<bool> blocks_flags;
  11.     vector<T> data;
  12.     int sqrt_n;
  13.  
  14.     void set_values(int from, int to, T val) {
  15.         if (blocks[from / sqrt_n] > -1) {
  16.             for (int i = from / sqrt_n; i < (from / sqrt_n + 1)*sqrt_n && i < data.size(); i++) {
  17.                 data[i] = blocks[from / sqrt_n];
  18.             }
  19.         }
  20.         if (blocks[to / sqrt_n] > -1) {
  21.             for (int i = to / sqrt_n; i < (to / sqrt_n + 1)*sqrt_n && i < data.size(); i++) {
  22.                 data[i] = blocks[to / sqrt_n];
  23.             }
  24.         }
  25.         for (int i = from; i <= to;) {
  26.             if (i % sqrt_n == 0 && i + sqrt_n - 1 <= to) {
  27.                 blocks[i / sqrt_n] = val;
  28.                 blocks_flags[i / sqrt_n] = true;
  29.                 i += sqrt_n;
  30.             } else {
  31.                 blocks[i / sqrt_n] = -1;
  32.                 data[i] = val;
  33.                 i++;
  34.             }
  35.         }
  36.         check_block(from/sqrt_n);
  37.         check_block(to/sqrt_n);
  38.     }
  39.  
  40.     void check_block(int block_ind) {
  41.         for (int i = block_ind*sqrt_n; i < (block_ind + 1)*sqrt_n && i < data.size(); i++) {
  42.             if ((*this)[i-1] > (*this)[i] && i > block_ind*sqrt_n) {
  43.                 blocks_flags[block_ind] = false;
  44.                 return;
  45.             }
  46.         }
  47.         blocks_flags[block_ind] = true;
  48.     }
  49.  
  50.     bool check(int from, int to) {
  51.         for (int i = from; i <= to;) {
  52.             if (i % sqrt_n == 0 && i + sqrt_n - 1 <= to) {
  53.                 if (i > from && (*this)[i-1] > (*this)[i]) return false;
  54.                 if (!blocks_flags[i / sqrt_n]) return false;
  55.                 i += sqrt_n;
  56.             } else {
  57.                 if (i > from && (*this)[i-1] > (*this)[i]) return false;
  58.                 i++;
  59.             }
  60.         }
  61.         return true;
  62.     }
  63.  
  64.     T operator[] (int i) const {
  65.         T result = data[i];
  66.         if (blocks[i / sqrt_n] > -1)
  67.             result = blocks[i / sqrt_n];
  68.         return result;
  69.     }
  70.  
  71.     SqrtDecomp2(vector<T> a) {
  72.         data = a;
  73.         sqrt_n = static_cast<int>(sqrt(data.size())) + 1;
  74.         blocks.resize(sqrt_n, -1);
  75.         blocks_flags.resize(sqrt_n, false);
  76.         for (int i = 0; i < blocks.size(); i++) {
  77.             check_block(i);
  78.         }
  79.     }
  80. };
  81.  
  82. int main() {
  83.     int n, m;
  84.     cin >> n >> m;
  85.     vector<int> a(n);
  86.     for (int i = 0; i < n; i++)
  87.         cin >> a[i];
  88.     SqrtDecomp2 sd{a};
  89.     for (int i = 0; i < m; i++) {
  90.         int t, l, r, v;
  91.         cin >> t >> l >> r;
  92.         if (t == 1) {
  93.             cin >> v;
  94.             sd.set_values(l-1, r-1, v);
  95.         } else {
  96.             cout << (sd.check(l-1, r-1) ? "Yes" : "No") << endl;
  97.         }
  98.     }
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement