# 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 longtypedef 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;}`