bzoj 4373 洛谷 5728 算术天才⑨与等差数列 题解

题意简述

给定给一个序列，每次支持：

1. 单点修改
2. 询问一段区间是否能排列成一个公差为$d$的等差数列
   （强制在线）

区间长度$3e5$，其它的值域都在$[0,1e9]$之间。

思路框架

维护区间和？显然能构造出一种情况卡掉。

那怎么办？维护区间平方和！然后看看是否和等差数列的平方和相等即珂。和很容易相等，但是平方和在$1e9$的范围内，就不太容易相等了。然后为了防止溢出，我们把答案对一个大质数取膜。

然后就是高能线段树+高能数论了。

求等差数列平方和

等差数列，首项为$a$，公差为$d$，项数为$n$。

要求$\sum\limits_{i=0}^{n-1} (a+id)^2$。

拆开括号，然后把$d$提出来，套各种公式，得到结果为：

$na^2+2ad\times s(n-1)+d^2s2(n-1)$

其中$s(n)=1+2+3…+n=n(n+1)/2$，$s_2(n)=1^2+2^2+3^2…+n^2=\dfrac{n(n+1)(2n+1)}{6}$。

代码

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define int long long 
    #define N 555555
    #define mod 2305843009213693967ll
    //这个质数是2^63-1的下一个质数
    #define i6  384307168202282328ll
    //6的逆元
    #define i2  1152921504606846984ll
    //2的逆元
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }

    class SegmentTree
    {
    public:
        struct node
        {
            int l,r;
            int s,mn,mx;
        }tree[N<<2];
        #define ls index<<1
        #define rs index<<1|1

        #define L tree[index].l
        #define R tree[index].r
        #define S tree[index].s
        #define M tree[index].mn
        #define X tree[index].mx

        #define lL tree[ls].l
        #define lR tree[ls].r
        #define lS tree[ls].s
        #define lM tree[ls].mn
        #define lX tree[ls].mx

        #define rL tree[rs].l
        #define rR tree[rs].r
        #define rS tree[rs].s
        #define rM tree[rs].mn
        #define rX tree[rs].mx
        void Update(int index=1)
        {
            M=min(lM,rM); X=max(lX,rX);
            S=(lS+rS)%mod;
        }
        void Build(int l,int r,int index=1)
        {
            L=l,R=r;
            if (l==r)
            {
                int x;R1(x);S=(x*x)%mod;M=X=x;
                return;
            }
            int mid=(l+r)>>1;
            Build(l,mid,ls);
            Build(mid+1,r,rs);
            Update(index);
        }
        void Change(int pos,int x,int index=1) //单点修改
        {
            if (pos<L or R<pos) return;
            if (L==R) {S=(x*x)%mod;M=X=x;return;}
            Change(pos,x,ls); Change(pos,x,rs);
            Update(index);
        }
        int QueryMin(int l,int r,int index=1) 
        {
            if (l>R or L>r) return mod; //INF
            if (l<=L and R<=r) return M;
            return min(QueryMin(l,r,ls),QueryMin(l,r,rs));
        }
        int QueryMax(int l,int r,int index=1)
        {
            if (l>R or L>r) return -mod; //-INF
            if (l<=L and R<=r) return X;
            return max(QueryMax(l,r,ls),QueryMax(l,r,rs));
        }
        int QuerySum(int l,int r,int index=1) //最小，最大，平方和
        {
            if (l>R or L>r) return 0;
            if (l<=L and R<=r) return S;
            return (QuerySum(l,r,ls)+QuerySum(l,r,rs))%mod;
        }
    }T;

    int n,q;
    void Input()
    {
        Rd(2,&n,&q);
        T.Build(1,n);
    }

    int smul(int a,int b)
    {
        int r=0;
        while(b)
        {
            if (b&1) r=(r+a)%mod;
            a=(a<<1)%mod;
            b>>=1;
        }
        return r;
    }
    int sqrs(int x){return smul(i6,smul(x,smul(x+1,2*x+1)))%mod;}
    //1~x的平方和
    int ArethSum(int a1,int d,int n) //首项a1，公差d，项数n的等差数列和
    {
        int ans1=smul(n,smul(a1,a1))%mod; //n*a1^2
        int ans2=smul(a1<<1,smul(d,smul(n,smul(n-1,i2))))%mod;
        //2ad*n*(n-1)/2
        int ans3=smul(smul(d,d),sqrs(n-1))%mod; 
        //d^2*sqrs(n-1)
        return (ans1+ans2+ans3)%mod;
    }
    void Soviet()
    {
        int yes_cnt=0;
        F(i,1,q)
        {
            int o;R1(o);
            if (o==1)
            {
                int pos,x;Rd(2,&pos,&x);
                pos^=yes_cnt; x^=yes_cnt;
                T.Change(pos,x);
            }
            if (o==2)
            {
                int l,r,d;Rd(3,&l,&r,&d); l^=yes_cnt;r^=yes_cnt;d^=yes_cnt;
                int Min=T.QueryMin(l,r),Max=T.QueryMax(l,r),s=T.QuerySum(l,r);
                int len=r-l+1;
                if (len==1) {puts("Yes");++yes_cnt;  continue;}
                //这个特判下
                if (Min+(len-1)*d!=Max) {puts("No"); continue;} 
                //这个项数不对的也要特判下

                int ss=ArethSum(Min,d,len);
                if (ss==s) puts("Yes"),++yes_cnt;
                else puts("No");
            }
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long 
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}