AC日记——算术天才⑨与等差数列 bzoj 4373

4373

思路：

　　判断一个数列是否是等差数列：

　　　　1，最大值减去最小值==（区间个数-1）*k；

　　　　2，gcd==k；

　　　　3，不能有重复（不会这判断这一条，但是数据水就过了）；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 300005

struct TreeNodeType {

    int l, r, max, min, gcd, mid;

};

struct TreeNodeType tree[maxn << ];

int n, m, ai[maxn], ty;

inline void in(int &now)

{

    char Cget = getchar(); now = ;

    while (Cget > '' || Cget < '') Cget = getchar();

    while (Cget >= ''&&Cget <= '')

    {

        now = now *  + Cget - '';

        Cget = getchar();

    }

}

int gcd(int a, int b)

{

    int tmp;

    while(b!=) tmp=b,b=a%b,a=tmp;

    return a;

}

void tree_build(int now, int l, int r)

{

    tree[now].l = l, tree[now].r = r;

    if (l == r)

    {

        tree[now].gcd = ai[l] - ai[l - ];

        tree[now].min = ai[l], tree[now].max = ai[l];

        return;

    }

    tree[now].mid = l + r >> ;

    tree_build(now << , l, tree[now].mid);

    tree_build(now <<  | , tree[now].mid + , r);

    tree[now].gcd = gcd(tree[now << ].gcd, tree[now <<  | ].gcd);

    tree[now].max = max(tree[now << ].max, tree[now <<  | ].max);

    tree[now].min = min(tree[now << ].min, tree[now <<  | ].min);

}

void pre()

{

    in(n), in(m);

    for (int i = ; i <= n; i++) in(ai[i]);

    tree_build(, , n);

}

int tree_do(int now, int l, int r)

{

    if (tree[now].l == l&&tree[now].r == r)

    {

        if (ty == ) return tree[now].max;

        if (ty == ) return tree[now].min;

        if (ty == ) return tree[now].gcd;

        tree[now].gcd = ai[l] - ai[l - ];

        tree[now].max = ai[l], tree[now].min = ai[l];

        return ;

    }

    int res=;

    if (l > tree[now].mid) res = tree_do(now <<  | , l, r);

    else if (r <= tree[now].mid) res = tree_do(now << , l, r);

    else

    {

        res = tree_do(now << , l, tree[now].mid);

        if (ty == ) res = max(res, tree_do(now <<  | , tree[now].mid + , r));

        if (ty == ) res = min(res, tree_do(now <<  | , tree[now].mid + , r));

        if (ty == ) res = gcd(res, tree_do(now <<  | , tree[now].mid + , r));

    }

    if (ty == )

    {

        tree[now].gcd = gcd(tree[now << ].gcd, tree[now <<  | ].gcd);

        tree[now].max = max(tree[now << ].max, tree[now <<  | ].max);

        tree[now].min = min(tree[now << ].min, tree[now <<  | ].min);

    }

    return res;

}

void solve()

{

    int op, l, r, x, y, last = ;

    for (int t = ; t <= m; t++)

    {

        in(op);

        if (op == )

        {

            in(x), in(y);

            x^=last,y^=last,ty=,ai[x]=y;

            tree_do(,x,x);

            if(x!=n) tree_do(,x+,x+);

        }

        else

        {

            in(l),in(r),in(x);

            l^=last,r^=last,x^=last;

            if(l==r)

            {

                last++;

                printf("Yes\n");

                continue;

            }

            int ma,mi,gcdd;

            ty=,ma=tree_do(,l,r);

            ty=,mi=tree_do(,l,r);

            ty=,gcdd=tree_do(,l+,r);

            if((ma-mi)==x*(r-l)&&abs(gcdd)==x) printf("Yes\n"),last++;

            else printf("No\n");

        }

    }

}

int main()

{

    pre();

    solve();

    return ;

}