**Refereances:**
- Rolling Hash: https://cp-algorithms.com/string/string-hashing.html#calculation-of-the-hash-of-a-string
# Content
[toc]

# Bài toán 1 (Rolling Hash)
## Bài toán
- Đề bài: Cho hai $string$ $s$ và $p$ gồm các chữ cái viết thường trong Tiếng Anh. Đếm số lần xuất hiện của $p$ trong $s$.
- Input:
Dòng đầu ghi $string$ $s$ và dòng sau ghi $string$ $p$ $(1 \le |p| \le |s| \le 1e6)$
- Sample test:

:::info
**Input:**
saippuakauppias
pp

**Output:**
2
:::
- Link bài: https://cses.fi/problemset/task/1753
## Thuật toán Ngây thơ
Với mỗi vị trí $i$ trên $s$, chạy vòng lặp $j$ từ $0$ đến $|p|-1$, nếu tất cả $s_i+j$ bằng $p_j$ thì ta có một lần xuất hiện. Dễ thấy thuật toán này có thời gian chạy là $|s|*|p|$, nói cách khác độ phức tạp là $O(N^2)$, quá chậm để có thể chạy.
## Thuật toán tối ưu
- Ta thấy rằng việc so sách $|p|$ lần cho mỗi vị trí $i$ làm cho thuật toán trở nên rất chậm. Vậy ta có thể nghĩ đến một cách nào đó để so sách ít hơn mà vẫn đảm bảo tính đúng đắn không? Đáp án là có, ta có thể chuyển từ so sánh string sang so sánh số.
- Ai cũng biết rằng 26 chữ cái trong Tiếng Anh đều có thể chuyển thành số theo bảng mã ASCII, do đó ta có thể chuyển một string thành một dãy số theo công thức:
$Hash=(\sum_{i=0}^{s.size()-1} (s[i]-'a'+1)*P^i)$ $mod$ $M$
- Với $P$ là một số nguyên tố bất kỳ(thường là các số có hai chữ số) và %M% là một số nguyên tố cực lớn(thường lớn hơn $1e9$) dùng để tránh tràn số và giảm khả năng sai.
- Vì ta có thao tác $mod$ $M$ nên các số được tạo ra sẽ trải dài trong khoảng từ $0$ đến $M-1$ nhưng số lượng string tồn tại lớn hơn có thể lớn hơn $M$ nhiều nên $HashA=HashB$ thì chưa chắc $A=B$. Do có khả năng sai như vậy nên ta mới cần số $P$ để ta có thể sinh ra nhiều số $hash$ khác nhau với cùng một $string$ ban đầu, từ đó làm giảm khả năng sai đi.
- Tuy nhiên với bài này thì việc $hash$ nhiều lần là không cần thiết vì tỉ lệ có hai $string$ bị trùng trên khoảng $M$ số là  $\approx \frac{1}{m}$  nhưng ở đây ta chỉ so sánh $string$ cùng lắm $1e6$ lần mà thôi.
- Quay lại với bài toán thì ta sẽ $hash$ $string$ $p$ sau đó $hash$ $string$ $s$ theo từng cửa sổ độ dài $|p|$ và chỉ việc so sánh chúng. Thuật toán này sẽ chỉ tốn độ phức tạp $O(n)$.
## Code mẫu
:::spoiler If you know, you know
:::success :::

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M=1e9+7, P=97;
string s, p;
int cnt, add=1, hashs=0, power1=1, power2=1, hashp=0;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>s>>p;
    int n=s.size(), m=p.size();
    for(int i=0; i<m; ++i) (hashp+=(p[i]-'a'+1)*add)%=M, (add*=P)%=M;
    for(int i=0; i<n; ++i)
    {
        (hashs+=(s[i]-'a'+1)*power1)%=M, (power1*=P)%=M;
        if(i>=m-1)
        {
            if(hashs==hashp) ++cnt;
            (hashp*=P)%=M;
            hashs-=((s[i+1-m]-'a'+1)*power2%M), (power2*=P)%=M;
            if(hashs<0) hashs+=M;
        }
    }
    cout<<cnt;
    return 0;
}

:::
# Bài toán 2 (The another way of hashing)
## Bài toán
- Cho mảng $a$ gồm $n$ phần tử, trả lờ $q$ truy vấn thuộc một trong hai dạng:
_ $1$ $i$ $x$: thay đổi $a_i$ thành $x$
_ $2$ $l$ $r$ $k$: kiểm tra xem số lần xuất hiện của mọi số trong khoảng $a_l$ đến $a_r$ có chia hết cho $k$ không.
- Input:
_Dòng đầu gồm hai số $n$ và $q$ $(1 \le n, q \le 3e5)$.
_Dòng thứ hai gồm $n$ số nguyên là mảng $a$ $(1 \le a_i \le 1e9)$ được cho.
_$q$ dòng tiếp theo mỗi dòng gồm một trong hai loại truy vấn:
$1$ $i$ $x,$ $(1 \le i \le n, 1 \le x \le 1e9)$
$2$ $l$ $r$ $k, $(1 \le l \le r \le n, 1 \le k \le n)$
:::info
**Input:**
10 8
1234 2 3 3 2 1 1 2 3 4
2 1 6 2
1 1 1
2 1 6 2
2 1 9 2
1 10 5
2 1 9 3
1 3 5
2 3 10 2

**Output:**
NO
YES
NO
YES
YES
:::
- Link bài: https://codeforces.com/contest/1746/problem/F
## Thuật toán ngây thơ
- Dễ thấy rằng, nếu số lần xuất hiện của mọi số trong khoảng $a_l$ đến $a_r$ mà chia hết $k$ thì $\sum_{i=l}^r a_i$ sẽ chia hết cho $k$.
- Từ đó ta bài toán trở về dạng cập nhật điểm và tìm tổng đoạn cơ bản nên có thể dễ dàng giải bằng một số cấu trúc dữ liệu như $ST$ hoặc $BIT$.
- Tuy nhiên rõ ràng sẽ có một số trường hợp đặc biệt như nếu trong khoảng $a_l$ đến $a_r$ có một số không có số lần xuất hiện chia hết cho $k$ nhưng chính nó chia hết cho $k$ thì cũng dẫn tới $WA$.
## Thuật toán tối ưu
- Vấn đề ta gặp phải ở thuật toán ngây thơ là việc các số trong đoạn $l$ $r$ rơi vào trường hợp đặc biệt, vậy tại sao ta không nghĩ tới việc biến nó thành một số khác và vì bài toán chỉ yêu cầu thực hiện truy vấn trên số lần xuất hiện của các số nên ta có thể biến đổi một cách tùy ý mà không cần quan tâm đến giá trị.
- Và ta nhận thấy rằng trường hợp dễ gây ra kết quả sai nhất là $k=2$ với khả năng sai là $\approx \frac{1}{2^T}$ nếu ta thức hiện T lần biến đổi nên ta chỉ cần thực hiện ít nhất $T=18$ lần là đủ cho một dãy $3e5$ số nhưng khuyến khích nên làm với $T \ge 25$.
- Đây chính là ý tưởng chính của đa phần các thuật toán $hash$ nói chung, biến đổi tham số đầu vào từ dạng này sang dạng khác mà vẫn giữ được tính chất mà đề bài yêu cầu để chạy bài toán nhiều lần nhằm lược bỏ các trường hợp đặc biệt.
- Quay lại với bài toán, vì mảng nhập vào và tổng số lượng truy vấn $1$ chỉ có tối đa $6e5$ nên ta sẽ nén các giá trị $a_i$ và $x$ có thể lên tới $1e9$ lại để thuận tiện cho việc $hash$. Sau đó, với mỗi số nguyên $i$ $(1 \le i \le 6e5)$ ta random $T$ lần trong khoảng từ $1$ đến $P$ ($P$ là một số nguyên tố rất lớn) biểu thị rằng $i$ sau khi $hash$ sẽ trở thành số đó. Từ đó ta build được $T$ mảng mới, sau cùng ta chỉ cần tạo thêm $T$ cấu trúc dữ liệu cho mỗi mảng và thực hiện các truy vấn. Khi thực hiện truy vấn $2$ thì chỉ cần $1$ trong $T$ lần trả ra kết quả là sai thì tổng kết quả là sai, còn không thì là đúng.
## Code mẫu
:::spoiler If you know again, you know
:::success :::

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define INT_MAX LLONG_MAX
#define INT_MIN LLONG_MIN
// pairs
#define mp make_pair
#define f first
#define s second
//loops
#define For(i, a, b) for (int i = (a); i < (b); ++i)
#define Rof(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define For2(i, a, b) for (int i = (a); (b) ; ++i)
#define Rof2(i, a, b) for (int i = (b)-1; (a) ; --i)
#define trav(a, x) for (auto &a : x)
//declarations
#define V vector
#define pr pair
#define prr<x> pair<x,x>
#define pq priority_queue
#define pqg<x> priority_queue<x, vector<x>, greater<x>>
// max min
#define max(x, y) max((int)x, (int)y)
#define min(x, y) min((int)x, (int)y)
// function
#define pb push_back
#define all(x) x.begin(),x.end();
const int N=3e5+10, T=26, M=2147483647;
int n, q, a[N], hashh[T][2*N], after[N];
long long bit[T][N];
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
ordered_set compress;
vector<int> query[N];
long long getSum(int p, int times)
{
    int idx=p;
    long long ans=0;
    while(idx>0)
    {
        ans+=bit[times][idx];
        idx-=(idx&(-idx));
    }
    return ans;
}
void update(int u, long long v, int times)
{
    int idx = u;
    while(idx<=n)
    {
        bit[times][idx]+=v;
        idx+=(idx&(-idx));
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    freopen("TEST1.out", "w", stdout);
    cin>>n>>q;
    For(i, 1, n+1) cin>>a[i], compress.insert(a[i]);
    For(i, 0, q)
    {
        int type, x, y, z;
        cin>>type;
        query[i].pb(type);
        if(type-1)
        {
            cin>>x>>y>>z;
            query[i].pb(x), query[i].pb(y), query[i].pb(z);
        }
        else
        {
            cin>>x>>y;
            compress.insert(y);
            query[i].pb(x), query[i].pb(y);
        }
    }
    For(i, 0, T) For(j, 1, n+q) hashh[i][j]=Rand()%M;
    For(i, 1, n+1) after[i]=compress.order_of_key(a[i])+1;
    For(i, 0, T) For(j, 1, n+1) update(j, 1LL*hashh[i][after[j]], i);
    For(i, 0, q)
    {
        int type=query[i][0];
        if(type-1)
        {
            long long sum;
            bool check=1;
            For(j, 0, T)
            {
                sum=getSum(query[i][2], j)-getSum(query[i][1]-1, j);
                if(sum%(1LL*query[i][3]))
                {
                    check=0;
                    break;
                }
            }
            if(check) cout<<"YES\n";
            else cout<<"NO\n";
        }
        else
        {
            For(j, 0, T)
                update(query[i][1], 1LL*(hashh[j][compress.order_of_key(query[i][2])+1]-hashh[j][after[query[i][1]]]), j);
            after[query[i][1]]=compress.order_of_key(query[i][2])+1;
        }
    }
    return 0;
}

:::