HackerEarth Advance search problem solution

In this HackerEarth Advanced search problem solution, You are given a string S of length N consisting of only lower case English alphabets. You will need to answer Q queries of the following types.

1. 1 L R W: Find the number of occurrences of string W in substring [L,R] of string S.
2. 1 L R U: Update the substring [L,R] of string S with string U.

HackerEarth Advanced search problem solution.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 9;
bool grid[MAX_N][MAX_N];
int ans;

void bt() {
    for (int i = 0; i < MAX_N; ++i)
        for (int j = 0; j < MAX_N; ++j)
            if (grid[i][j]) {
                if (grid[i][j + 1]) {
                    grid[i][j] = grid[i][j + 1] = false;
                    bt();
                    grid[i][j] = grid[i][j + 1] = true;
                }
                if (grid[i + 1][j]) {
                    grid[i][j] = grid[i + 1][j] = false;
                    bt();
                    grid[i][j] = grid[i + 1][j] = true;
                }
                return;
            }
    ++ans;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    for (int i = 0; i < MAX_N - 1; ++i)
        for (int j = 0; j < MAX_N - 1; ++j)
            grid[i][j] = i >= 3 && i <= 4 || j >= 3 && j <= 4;
    bt();
    cout << ans << '\n';
}#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

using namespace __gnu_pbds;
using namespace std;

#define ll long long

typedef tree<int, null_type, less<int>, rb_tree_tag,
        tree_order_statistics_node_update> ordered_set;

unordered_map <string, ordered_set> cache;
unordered_set<int> vis;
string s;

void updateSet(ordered_set &o, int sign, int pos) {
    if (sign == -1) {
        o.erase(pos);
    } else {
        o.insert(pos);
    }
}

void cacheStrings(int l, int r, int n, int m, int sign) {
    l = max(l, m - 1);
    for (int i = l; i < n and i - m + 1 <= r; ++i) {
        updateSet(cache[s.substr(i - m + 1, m)], sign, i);
    }
}

void updateAndValidateCache(int l, int r, int n, string &w) {
    for (auto z:vis) {
        cacheStrings(l, r, n, z, -1);
    }
    for (int i = l; i <= r; ++i) {
        s[i] = w[i - l];
    }
    for (auto z:vis) {
        cacheStrings(l, r, n, z, 1);
    }
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int n, q;
    cin >> n >> q >> s;
    while (q-- > 00) {
        int t, l, r;
        string w;
        cin >> t >> l >> r >> w;
        l--, r--;
        if (t == 1) {
            if (!vis.count(w.size())) {
                vis.insert(w.size());
                cacheStrings(0, n - 1, n, w.size(), 1);
            }
            auto &z = cache[w];
            int li = l + w.size() - 1;
            cout << z.order_of_key(r + 1) - z.order_of_key(li) << "\n";
        } else {
            updateAndValidateCache(l, r, n, w);
        }
    }

    return 0;
}