题意描述

算术天才$⑨$非常喜欢和等差数列玩耍。

有一天，他给了你一个长度为$n$的序列，其中第$i$个数为$a_i$。

他想考考你，每次他会给出询问$l,r,k$，问区间$[l , r]$内的数从小到大排序后能否形成公差为$k$的等差数列。

当然，他还会不断修改其中的某一项。

为了不被他鄙视，你必须要快速并正确地回答完所有问题。

注意：只有一个数的数列也是等差数列。

输入格式

第一行包含两个正整数$n,m$，分别表示序列的长度和操作的次数。

第二行包含$n$个整数，依次表示序列中的每个数$a_i$ 。

接下来$m$行，每行一开始为一个数$opt$。

若$opt=1$，则接下来两个整数$x,y$，表示把$a_x$修改为$y$。

若$opt=2$，则接下来三个整数$l,r,k$，表示一个询问。

在本题中，所有的$x,y,l,r,k$都是经过加密的，都需要异或(即xor , C++中为^)你之前输出的Yes的个数来进行解密。

输出格式

输出若干行，对于每个询问操作，如果可以形成等差数列，请输出Yes，否则输出No。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

No
Yes

数据范围和约定

对于$100\%$的数据，保证$1 < n , m < 3 \times 10^5$，$1 < a_i < 10^9$

$1 < x < n$ ， $1 < y < 10^9$

$1 < l , r < n$ ， $1 < k < 10^9$

分析

~~养生题目警告。~~

首先，我们先来回想一下等差数列的公差公式，即$max - min = (r - l) \times k$

移一下项，就变成了$k = \frac{max - min}{r - l}$

不难看出，如果我们要判断一段序列是否可以形成等差数列，必须要求出这段区间的最值(即$max$与$min$)，这样才能求出公差。

继续考虑等差数列的性质。可以注意到，如果区间内的数能够形成等差数列，必须满足以下两条件之一

公差为$0$。
数列内无相同元素，公差为相邻两个数之差的绝对值的$gcd$（即最大公约数）。

而相邻两数之差的绝对值可以通过差分维护。

这样的话，我们一共需要维护四种元素，分别是区间$max$ & $min$，差分序列上的区间$gcd$，以及每个数前驱相同元素的位置。

其中，维护每个数前驱相同的元素的位置可以map套set，其他的均可以线段树维护

代码的话，~~往死里写就完事了~~

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<map>
#include<set>

#define ll long long
#define I inline
#define N 300001

using namespace std;

ll n , m , a[N] , b[N];

map<int  , int > M;
set<int  > S[N];
int cnt;

int opt , num , x , p , l , r , d;

namespace Segment_tree{
    #define lson(x) x << 1
    #define rson(x) x << 1 | 1
    

    ll maxn[N << 2] , minn[N << 2] , Gcd[N << 2] , l[N << 2] , r[N << 2] , last[N << 2];

    ll gcd(ll a , ll b){
        return !b ? a : gcd(b , a % b);
    }

    void pushup(int x){
        minn[x] = min(minn[lson(x)] , minn[rson(x)]);
        maxn[x] = max(maxn[lson(x)] , maxn[rson(x)]);
        Gcd[x] = gcd(Gcd[lson(x)] , Gcd[rson(x)]);
        last[x] = max(last[lson(x)] , last[rson(x)]);
        return ;
    }

    void build(int x , int ql , int qr){
        l[x] = ql , r[x] = qr;
        if(ql == qr){
            maxn[x] = minn[x] = a[ql];
            Gcd[x] = b[ql];
            last[x] = 0;
            return ;
        }
        int mid = (ql + qr) >> 1;
        build(lson(x) , ql , mid);
        build(rson(x) , mid + 1 , qr);
        pushup(x);
    }

    void change(int k , int p , int x , int opt){
        if(l[k] == r[k]){
            if(opt == 0){
                maxn[k] = minn[k] = x;
            }
            else if(opt == 1){
                Gcd[k] = x;
            }
            else{
                last[k] = x;
            }
            return ;
        }
        int mid = (l[k] + r[k]) >> 1;
        if(p <= mid){
            change(lson(k) , p , x , opt);
        }
        else{
            change(rson(k) , p , x , opt);
        }
        pushup(k);
    }

    ll range_max(int x , int ql , int qr){
        if(l[x] == ql && r[x] == qr){
            return maxn[x];
        }
        int mid = (l[x] + r[x]) >> 1;
        if(mid >= qr){
            return range_max(lson(x) , ql , qr);
        }
        else if(ql > mid){
            return range_max(rson(x) , ql , qr);
        }
        else{
            return max(range_max(lson(x) , ql , mid) , range_max(rson(x) , mid + 1 , qr));
        }
    }

    ll range_min(int x , int ql , int qr){
        if(l[x] == ql && r[x] == qr){
            return minn[x];
        }
        int mid = (l[x] + r[x]) >> 1;
        if(mid >= qr){
            return range_min(lson(x) , ql , qr);
        }
        else if(ql > mid){
            return range_min(rson(x) , ql , qr);
        }
        else{
            return min(range_min(lson(x) , ql , mid) , range_min(rson(x) , mid + 1 , qr));
        }
    }

    ll range_gcd(int x , int ql , int qr){
        if(l[x] == ql && r[x] == qr){
            return Gcd[x];
        }
        int mid = (l[x] + r[x]) >> 1;
        if(mid >= qr){
            return range_gcd(lson(x) , ql , qr);
        }
        else if(ql > mid){
            return range_gcd(rson(x) , ql , qr);
        }
        else{
            return gcd(range_gcd(lson(x) , ql , mid) , range_gcd(rson(x) , mid + 1 , qr));
        }
    }

    ll range_last(int x , int ql , int qr){
        if(l[x] == ql && r[x] == qr){
            return last[x];
        }
        int mid = (l[x] + r[x]) >> 1;
        if(mid >= qr){
            return range_last(lson(x) , ql , qr);
        }
        else if(ql > mid){
            return range_last(rson(x) , ql , qr);
        }
        else{
            return max(range_last(lson(x) , ql , mid) , range_last(rson(x) , mid + 1 , qr));
        }
    }

}


int main(){
    ios :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        b[i] = abs(a[i] - a[i - 1]);
        if(M.find(a[i]) == M.end()){
            M[a[i]] = ++ cnt;
            S[cnt].insert(0);
        }
        S[M[a[i]]].insert(i);
    }
    
    Segment_tree :: build(1 , 1 , n);

    for(int i = 1; i <= m; i ++){
        cin >> opt;
        if(opt == 1){
            cin >> p >> x;
            p ^= num , x ^= num;
            a[p] = x;
            Segment_tree :: change(1 , p , x , 0);
            Segment_tree :: change(1 , p , abs(a[p] - a[p - 1]) , 1);
            if(p <= n){
                Segment_tree :: change(1 , p + 1 , abs(a[p + 1] - a[p]) , 1);
            }
        }

        else{
            cin >> l >> r >> d;
            l ^= num , r ^= num , d ^= num;
            if(Segment_tree :: range_max(1 , l , r) - Segment_tree :: range_min(1 , l , r) == 1ll * d * (r - l) && (d == 0 || l == r || ((Segment_tree :: range_gcd(1 , l + 1 , r) % d == 0) && Segment_tree :: range_last(1 , l , r) < l))){
                ++ num;
                puts("Yes");
            }
            else{
                puts("No");
            }
        }
    }
    return 0;
}