Thuật toán ngẫu nhiên:

Với mỗi ~x~ thuộc đoạn [~1~, ~n~]: gọi ~P~ (~P_1, P_2,..., P_m~) là tập hợp tất cả những giá trị ~i~ mà ~b_i = x~. Với mọi giá trị ~j~ thuộc đoạn [~1~, ~m~ - ~1~], gán ~c_{P_j}~ là một số ngẫu nhiên trong đoạn [~1~, ~10^8~], và ~c_{P_m} = -(c_{P_1} + c_{P_2} +...+ c_{P_{m - 1})}~. Theo cách này, ta sẽ có ~c_{P_1} + c_{P_2} +...+ c_{P_m} = 0~. Nếu tất cả các giá trị ~a_{P_i}~ là bằng nhau thì ~a_{P_1} \times c_{P_1} + a_{P_2} \times c_{P_2} +...+ a_{P_m} \times c_{P_m} = 0~.

Đặt ~s = a_1 \times c_1 + a_2 \times c_2 +...+ a_n \times c_n~. Nếu đáp án của một truy vấn là "NO" thì ~s = 0~. Nếu ~s \ne 0~, đáp án chắc chắn là "YES".

Vì đây là một thuật toán ngẫu nhiên nên nếu ~s = 0~ thì xem như đáp án là "NO".

Để tính được giá trị ~s~ có thể dùng cấu trúc dữ liệu segment tree.

Xác suất sai một test:

Thuật toán chỉ sai khi đáp án lẽ ra là "YES" nhưng ~s = a_1 \times c_1 + a_2 \times c_2 +...+ a_n \times c_n = 0~

Trong trường hợp này, giá trị ~a_1 \times c_1 + a_2 \times c_2 +...+ a_{n - 1} \times c_{n - 1}~ gần như ngẫu nhiên trong khoảng ~[-10^{13}..10^{13}]~, gọi giá trị này là ~x~. Xác suất để ~a_n \times c_n = -x~ là ~\frac{1}{min(\frac{10^{13}}{a_n}, 10^8)} \times \frac{min(\frac{10^{13}}{a_n}, 10^8)}{10^{13}} = \frac{1}{10^{13}}~.

Vậy xác suất để sai một truy vấn vào khoảng ~\frac{1}{10^{13}}~, xác suất sai một test là khoảng ~\frac{1}{10^8}~.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)1e5+228;
const int MAX = (int)1e8;

int a[N], b[N];
long long c[N];

struct SegmentTree
{
    vector<long long> tree, sum, lazy;
    int n;

    SegmentTree(int _n = 0)
    {
        n = _n;
        tree.assign(n*4+7, 0);
        sum.assign(n*4+7, 0);
        lazy.assign(n*4+7, 0);
    }

    void init(int id, int l, int r)
    {
        if(l == r)
        {
            sum[id] = c[l];
            tree[id] = c[l] * a[l];
            return;
        }
        int mid = (l+r)/2;
        init(id*2, l, mid);
        init(id*2+1, mid+1, r);
        tree[id] = tree[id*2] + tree[id*2+1];
        sum[id] = sum[id*2] + sum[id*2+1];
    }

    void down(int id)
    {
        if(lazy[id] > 0)
        {
            for(int i=id*2; i<=id*2+1; ++i)
            {
                tree[i] = sum[i] * lazy[id];
                lazy[i] = lazy[id];
            }
            lazy[id] = 0;
            return;
        }
    }

    void upd(int id, int l, int r, int u, int v, int x)
    {
        if(l > v || r < u) return;
        if(u <= l && r <= v) 
        {
            tree[id] = sum[id] * x;
            lazy[id] = x;
            return;
        }
        down(id);
        int mid = (l+r)/2;
        upd(id*2, l, mid, u, v, x);
        upd(id*2+1, mid+1, r, u, v, x);
        tree[id] = tree[id*2] + tree[id*2+1];
    }
    void upd(int l, int r, int x)
    {
        upd(1, 1, n, l, r , x);
    }
}it;

int n, q;
vector<int> vt[N];

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

int randnum(int l, int r) {
    vector<int> arr;
    for (int i = 0; i < 10; ++ i) {
        arr.push_back(l + rng() % (r - l + 1));
    }
    return arr[rng() % 10];
}

double randDouble(double l, double r) {
    uniform_real_distribution<double> cc(l, r);
    return cc(rng);
}

void solve()
{
    cin >> n >> q;
    for(int i=1; i<=n; ++i) cin >> a[i];
    for(int i=1; i<=n; ++i) cin >> b[i];

    for(int i=1; i<=n; ++i) vt[b[i]].push_back(i);
    for(int i=1; i<=n; ++i) 
    {
        long long sum = 0;
        for(int j=0; j<(int)vt[i].size(); ++j)
        {
            int id = vt[i][j];
            if(j+1 == (int)vt[i].size()) c[id] = -sum;
            else 
            {
                c[id] = randnum(-MAX, MAX);
                sum += c[id];
            }
        }
    }

    it = SegmentTree(n);
    it.init(1, 1, n);
    while(q--)
    {
        int l, r, x; cin >> l >> r >> x;
        it.upd(l, r, x);
        if(it.tree[1] == 0) cout << "NO\n";
        else cout << "YES\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    solve();
    return 0;
}