题解 P5278 【算术天才⑨与等差数列】

· · 题解

这是一种乱搞做法，非正解。

这里用了hash的思想，类比这个题目：
P3792 由乃与大母神原型和偶像崇拜

我们可以考虑维护区间平方和，由于出题人非常良心，所以这个方法没有被卡掉。
对于可以重排为公差为 k 的区间 [l,r]，设其最小值为 x，则一定有：

\sum\limits_{i=l}^ra_i^2=\sum\limits_{i=0}^{r-l}(x+ki)^2

注意这个只是充分条件，不具有必要性。

然后我们把等式右边展开一下

\sum\limits_{i=0}^{r-l}(x+ki)^2 =\sum\limits_{i=0}^{r-l}(x^2+2xki+k^2i^2) =(r-l+1)x^2+kx(r-l)(r-l+1)+k^2\sum\limits_{i=0}^{r-l}i^2

式子展开到这里，就可以直接计算了。
区间最小值 x 用线段树维护，最右边那一项套平方和公式即可。

\sum\limits_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}

最后，把算出来的结果与区间实际平方和进行比较。
如果一样，就输出 Yes，否则输出 No。
注意平方和的结果可能很大，所以我们随便找个质数膜一下，几乎不会影响到答案的正确性。

然后我的非正解就水过了这个题 23333

代码： 

#include<cstdio> 
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define int long long
#define N 300003
#define reg register
#define p 998244353
#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
#define inf 0x3f3f3f3f
using namespace std;

int w[N],a[N<<2],minn[N<<2],s[N<<2];
int n,q,key;

inline void read(int &x);
inline int power(int a,int t);
void build(int l,int r,int u);
inline void pushup(int u);
inline int min(int x,int y);
void modify(int t,int k,int l,int r,int u);
int qmin(int nl,int nr,int l,int r,int u);
int qsqr(int nl,int nr,int l,int r,int u);
inline int inv(int x);

signed main(){
    int op,l,r,x,y,k,t,sum,sqr;
    int len,inv6;
    inv6 = inv(6);
    read(n),read(q);
    for(int i=1;i<=n;++i) read(w[i]);
    build(1,n,1);
    while(q--){
        read(op);
        if(op==1){
            read(x),read(y);
            x ^= key,y ^= key;
            modify(x,y,1,n,1);
            w[x] = y;
        }else{
            read(l),read(r),read(k);
            l ^= key,r ^= key;
            k ^= key;
            len = r-l+1;
            x = qmin(l,r,1,n,1);
            sqr = qsqr(l,r,1,n,1);
            t = len*x%p*x%p;
            t = t+x*k%p*len%p*(len-1)%p;
            t %= p;
            --len;
            sum = k*k%p*(len*(len+1)%p*((len<<1)+1)%p*inv6%p)%p;
            t = (t+sum)%p;
            if(t!=sqr){
                printf("No\n");
                continue;
            } 
            printf("Yes\n");
            ++key;
        }
    }
    return 0;
}

inline int inv(int x){
    return power(x,p-2);
}

int qsqr(int nl,int nr,int l,int r,int u){
    if(nl<=l&&r<=nr) return s[u];
    int res = 0;
    if(nl<=mid) res += qsqr(nl,nr,l,mid,ls);
    if(nr>mid) res += qsqr(nl,nr,mid+1,r,rs);
    return res%p;
}

int qmin(int nl,int nr,int l,int r,int u){
    if(nl<=l&&r<=nr) return minn[u];
    int res = inf;
    if(nl<=mid) res = min(res,qmin(nl,nr,l,mid,ls));
    if(nr>mid) res = min(res,qmin(nl,nr,mid+1,r,rs));
    return res;
}

void modify(int t,int k,int l,int r,int u){
    if(l==r){
        a[u] = minn[u] = k;
        s[u] = k*k%p;
        return;
    }
    if(t<=mid) modify(t,k,l,mid,ls);
    else modify(t,k,mid+1,r,rs);
    pushup(u);
}

inline void pushup(int u){
    a[u] = (a[ls]+a[rs])%p;
    s[u] = (s[ls]+s[rs])%p;
    minn[u] = min(minn[ls],minn[rs]);
}

void build(int l,int r,int u){
    if(l==r){
        a[u] = minn[u] = w[l];
        s[u] = w[l]*w[l]%p;
        return;
    }
    build(l,mid,ls);
    build(mid+1,r,rs);
    pushup(u);
}

inline int min(int x,int y){
    return x<y?x:y;
}

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
}

inline int power(int a,int t){
    int res = 1;
    while(t){
        if(t&1) res = res*a%p;
        a = a*a%p;
        t >>= 1;
    }
    return res;
}