Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <iostream>
- #include <vector>
- using namespace std;
- template<typename T = int>
- struct SqrtDecomp2 {
- vector<T> blocks;
- vector<bool> blocks_flags;
- vector<T> data;
- int sqrt_n;
- void set_values(int from, int to, T val) {
- if (blocks[from / sqrt_n] > -1) {
- for (int i = from / sqrt_n; i < (from / sqrt_n + 1)*sqrt_n && i < data.size(); i++) {
- data[i] = blocks[from / sqrt_n];
- }
- }
- if (blocks[to / sqrt_n] > -1) {
- for (int i = to / sqrt_n; i < (to / sqrt_n + 1)*sqrt_n && i < data.size(); i++) {
- data[i] = blocks[to / sqrt_n];
- }
- }
- for (int i = from; i <= to;) {
- if (i % sqrt_n == 0 && i + sqrt_n - 1 <= to) {
- blocks[i / sqrt_n] = val;
- blocks_flags[i / sqrt_n] = true;
- i += sqrt_n;
- } else {
- blocks[i / sqrt_n] = -1;
- data[i] = val;
- i++;
- }
- }
- check_block(from/sqrt_n);
- check_block(to/sqrt_n);
- }
- void check_block(int block_ind) {
- for (int i = block_ind*sqrt_n; i < (block_ind + 1)*sqrt_n && i < data.size(); i++) {
- if ((*this)[i-1] > (*this)[i] && i > block_ind*sqrt_n) {
- blocks_flags[block_ind] = false;
- return;
- }
- }
- blocks_flags[block_ind] = true;
- }
- bool check(int from, int to) {
- for (int i = from; i <= to;) {
- if (i % sqrt_n == 0 && i + sqrt_n - 1 <= to) {
- if (i > from && (*this)[i-1] > (*this)[i]) return false;
- if (!blocks_flags[i / sqrt_n]) return false;
- i += sqrt_n;
- } else {
- if (i > from && (*this)[i-1] > (*this)[i]) return false;
- i++;
- }
- }
- return true;
- }
- T operator[] (int i) const {
- T result = data[i];
- if (blocks[i / sqrt_n] > -1)
- result = blocks[i / sqrt_n];
- return result;
- }
- SqrtDecomp2(vector<T> a) {
- data = a;
- sqrt_n = static_cast<int>(sqrt(data.size())) + 1;
- blocks.resize(sqrt_n, -1);
- blocks_flags.resize(sqrt_n, false);
- for (int i = 0; i < blocks.size(); i++) {
- check_block(i);
- }
- }
- };
- int main() {
- int n, m;
- cin >> n >> m;
- vector<int> a(n);
- for (int i = 0; i < n; i++)
- cin >> a[i];
- SqrtDecomp2 sd{a};
- for (int i = 0; i < m; i++) {
- int t, l, r, v;
- cin >> t >> l >> r;
- if (t == 1) {
- cin >> v;
- sd.set_values(l-1, r-1, v);
- } else {
- cout << (sd.check(l-1, r-1) ? "Yes" : "No") << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement