bzoj 4373: 算术天才⑨与等差数列

.

题意：在一个长度为n的序列中，询问l到r排序后是不是公差为k的等差数列，或修改其中一个数。
题解：线段树
$l\sim r$为等差数列，那么它们差分后的$\gcd$一定是k，最小值和最大值也要满足$min+k\cdot(r-l)=max$。还有一点就是区间内没有重复的数，（不过这题数据好像没卡这个点。。。）这个可以用set实现，具体可以看WorldWide_D大佬的博客我就不打了
丑到炸裂代码：

#include<bits/stdc++.h>
#define pa pair<int,int>
using namespace std;

int n,m,a[300010],ans=0,tot=1;
struct tree
{
    int l,r,mx,mn,g;
} tr[5000010];
struct ret
{
    int mn,mx,g;
};

char B[1<<14],*S=B,*T=B;
#define gc (S==T&&(T=(S=B)+fread(B,1,1<<14,stdin),S==T)?-1:*S++)
inline int read(){
    int x=0,f=1; char ch=gc;
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=gc;}
    while(ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=gc;}
    return x*f;
}
int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}
inline void pushup(int i)
{
    int lc=i<<1,rc=lc|1;
    tr[i].mx=max(tr[lc].mx,tr[rc].mx);
    tr[i].mn=min(tr[lc].mn,tr[rc].mn);
    tr[i].g=abs(gcd(gcd(tr[lc].g,tr[rc].g),tr[rc].l-tr[lc].r));
    tr[i].l=tr[lc].l;
    tr[i].r=tr[rc].r;
}
inline void chg(int p,int x)
{
    int i=p+tot;
//    printf("%d\n",i);
    tr[i].mn=tr[i].mx=x;
    a[p]=x;
    tr[i].l=tr[i].r=x;
    for(i>>=1;i;i>>=1)
    pushup(i);
}
inline ret get(int l,int r)
{
    ret ans={2147483647,0,0};
    int ll=-1,rr=-1;
    for(l+=tot-1,r+=tot+1;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1)
        {
            ans.mn=min(ans.mn,tr[l^1].mn);
            ans.mx=max(ans.mx,tr[l^1].mx);
            ans.g=gcd(ans.g,tr[l^1].g);
            if(~ll)
            ans.g=gcd(ans.g,tr[ll].l-tr[l^1].r);
            ll=l^1;
//            printf("l:%d %d\n",tr[l^1].l,tr[l^1].r);
        }
        if(r&1)
        {
            ans.mn=min(ans.mn,tr[r^1].mn);
            ans.mx=max(ans.mx,tr[r^1].mx);
            ans.g=gcd(ans.g,tr[r^1].g);
            if(~rr)
            ans.g=gcd(ans.g,tr[r^1].l-tr[rr].r);
            rr=r^1;
//            printf("r:%d %d\n",tr[r^1].l,tr[r^1].r);
        }
    }
//    printf("ll:%d rr:%d\n",ll,rr);
    if((~ll)&&(~rr))
    ans.g=gcd(ans.g,tr[rr].l-tr[ll].r);
    ans.g=abs(ans.g);
    return ans;
}
int main()
{
    n=read();
    m=read();
    while(tot<=n+3)
    tot<<=1;
    for(int i=1; i<=n; i++)
    {
        a[i]=read();
        int p=i+tot;
        tr[p].mn=tr[p].mx=a[i];
        tr[p].l=tr[p].r=a[i];
    }
    for(int i=1; i<=n; i++)
    for(int j=(i+tot>>1);j;j>>=1)
    pushup(j);/*
    for(int i=1;i<=tot*2+1;i++)
    printf("i:%d l:%d r:%d mn:%d mx:%d g:%d\n",i,tr[i].l,tr[i].r,tr[i].mn,tr[i].mx,tr[i].g);*/
    while(m--)
    {
        int op;
        op=read();
        if(op==1)
        {
            int x=read(),y=read();
#ifdef ONLINE_JUDGE
            x^=ans;
            y^=ans;
#endif
            chg(x,y);
        }
        else
        {
            int l=read(),r=read(),k=read();
#ifdef ONLINE_JUDGE
            l^=ans;
            r^=ans;
            k^=ans;
#endif
//              assert(l<=r);
            if(l>r)
            swap(l,r);
            ret hh=get(l,r);
//            printf("%d %d %d\n",hh.mn,hh.mx,hh.g);
            if(hh.g!=0&&hh.g!=k||hh.mx!=hh.mn+(r-l)*k)
                puts("No");
            else
            {
                puts("Yes");
                ans++;
            }
        }/*
    for(int i=1;i<=tot*2+1;i++)
    printf("i:%d l:%d r:%d mn:%d mx:%d g:%d\n",i,tr[i].l,tr[i].r,tr[i].mn,tr[i].mx,tr[i].g);*/
    }
}