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

lndjy · 2021-01-22 19:23:46 · 题解

这不是正解，而且很容易卡，只是这题数据不是一般的水才能过去。怀疑数据是用脚造的。

如果一个区间能重排成等差序列，那么它的首项和尾项的差一定是 k\times (len-1)，其中 k 是公差，len 是长度。

所以我们得到了一个错误率很高的方法：维护区间 max,min,若它们的差符合要求，那么就是，否则就不是。由于数据不是一般的水，所以这个做法有 50。

考虑提高正确性。维护一个区间和，用等差数列求和（(max+min)\times len/2）求出如果是等差数列的话所有数的和，在前面条件满足的情况下和一样，那么就是，否则就不是。这样的很容易卡，但是数据不是一般的水，所以这个做法有 100。

然后就愉快的水过这题。

#include<iostream>
#define int long long
using namespace std;
const int N=3e5+5;
int n,q,lst;
int a[N];
struct tree
{
    int l,r,sum,minn,maxx;
    tree operator +(tree x)
    {
        tree ans;
        ans.sum=sum+x.sum;
        ans.maxx=max(maxx,x.maxx);
        ans.minn=min(minn,x.minn);
        return ans;
    }
}t[N*4];
void pushup(int k)
{
    t[k].sum=t[k*2].sum+t[k*2+1].sum;
    t[k].maxx=max(t[k*2].maxx,t[k*2+1].maxx);
    t[k].minn=min(t[k*2].minn,t[k*2+1].minn); 
}
void build(int k,int l,int r)
{
    t[k].l=l;t[k].r=r;
    if(l==r)
    {
        t[k].sum=t[k].maxx=t[k].minn=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    pushup(k);
}
void change(int k,int p,int v)
{
    if(t[k].l==t[k].r)
    {
        t[k].sum=t[k].maxx=t[k].minn=v;
        return;
    }
    if(p<=t[k*2].r) change(k*2,p,v);
    else change(k*2+1,p,v);
    pushup(k);
}
const int qwq=1e16;
tree ask(int k,int l,int r)
{
    if(l<=t[k].l&&t[k].r<=r) return t[k];
    tree ans=(tree){0,0,0,qwq,0};
    if(l<=t[k*2].r) ans=ans+ask(k*2,l,r);
    if(t[k*2+1].l<=r) ans=ans+ask(k*2+1,l,r);
    return ans;
}
signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    build(1,1,n);
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x,y;
            cin>>x>>y;
            x^=lst;y^=lst;
            change(1,x,y);
        }
        else
        {
            int l,r,k;
            cin>>l>>r>>k;
            l^=lst;r^=lst;k^=lst;
            tree ans=ask(1,l,r);
            if(ans.maxx-ans.minn==(r-l)*k&&ans.sum==(ans.minn+ans.maxx)*(r-l+1)/2)
            {
                lst++;
                cout<<"Yes\n";
            }
            else cout<<"No\n";
        }
    }
    return 0;
}