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

[文章目录]

Description

有一天,他给了你一个长度为n的序列,其中第i个数为a[i]。
他想考考你,每次他会给出询问l,r,k,问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
当然,他还会不断修改其中的某一项。
为了不被他鄙视,你必须要快速并正确地回答完所有问题。
注意:只有一个数的数列也是等差数列。n,m(1<=n,m<=300000).

大师讲的题目,好难。也收获颇丰啊。

一个数列是等差数列当且仅当:
1.数列中的最大值-最小值=(公差*个数-1)
2.数列中的每两个数的差都为公差的倍数
3.数列中没有重复的数字
(需要特判数列中只有一个元素和公差为0的情况)

第一个条件线段树就好了。
第二个条件想到只要任意两个相邻的数之间的差能整除公差就行,另外gcd是符合区间加法的,所以我们维护一个差分数组的gcd。
第三个条件,维护每一位上的数在其之前与其最近的相等的数的位置,记为pre[i],所以只要是区间里的pre[i]的最大值小于l,就说明所有的数没有相同的,线段树搞一下。不过pre{i]怎么求???,我们需要维护一个set,优先级为先按值排序,后按位置由小到大排序,每次二分查找,修改就好了。

STL是个好东西。

NOTE:
区间判断没有重复的数:set+seg维护pre[i]。
区间gcd:是符合区间加法的
题目的划归与转化。(想不出来啊)

代码里加了点set的用法,支持结构体,优先级需要重载运算符。

set:插入log(n)后自动排序,log(n)查询的数据结构:
1.提供iterator,是个结构体指针,支持++,--;
2.upper_bound (node )返回迭代器,指向优先级大于node的第一个元素
3.lower_bound (node )返回迭代器,指向优先级大于等于node的第一个元素
4.insert (node ) 插入node
5.erase(node ) 清除node
6.#include <set>
set <node> 不重集合
multiset <node>可重集合

#include <set>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 301000
int n,m,M,sol;
int mx[N<<2],mi[N<<2],g[N<<2],mxpre[N<<2];
int a[N],op;

struct node {int pos,key;};

bool operator < (node x,node y) {return x.key==y.key ? x.pos<y.pos : x.key<y.key;}

multiset <node> s; 
multiset <node>::iterator it;

int read()
{
    char ch=getchar();int re=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
        re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re;
}

int gcd(int x,int y) {return (y==0) ? x:gcd(y,x%y);}

inline int Abs(int x) {return x>0 ? x : -x;}

void pushup(int x)
{
    mx[x]=max(mx[x<<1],mx[x<<1|1]);
    mi[x]=min(mi[x<<1],mi[x<<1|1]);
    g[x]=gcd(g[x<<1],g[x<<1|1]);
    mxpre[x]=max(mxpre[x<<1],mxpre[x<<1|1]);
}

void query_tree(int l,int r,int &mxx,int &mii,int &prex)
{
    prex=mxx=-1<<30;mii=1<<30;
    for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1)
        {
            mxx=max(mxx,mx[l^1]);mii=min(mii,mi[l^1]);
            prex=max(prex,mxpre[l^1]);
        }
        if(r&1)
        {
            mxx=max(mxx,mx[r^1]);mii=min(mii,mi[r^1]);
            prex=max(prex,mxpre[r^1]);
        }
    }
}

int query_gcd(int l,int r)
{
    int re=-1;
    for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1) re= ((re==-1) ? g[l^1]:gcd(g[l^1],re));
        if(r&1) re= ((re==-1) ?g[r^1]:gcd(g[r^1],re));
    }
    return re;
}
void fix()
{
    int x,y,val; x=read();val=read(); x^=sol,val^=sol;
    it=s.upper_bound((node){x,a[x]});
    if(it!=s.end() && it->key==a[x])
    {
        mxpre[it->pos+M]=mxpre[x+M];
        y=it->pos+M; while(y>>=1) mxpre[y]=max(mxpre[y<<1],mxpre[y<<1|1]);
    }
    s.erase((node){x,a[x]}); a[x]=val; s.insert((node){x,a[x]});
    it=s.upper_bound((node){x,a[x]});
    if(it!=s.end() && it->key==a[x])
    {
        mxpre[it->pos+M]=x; y=it->pos+M;
        while(y>>=1) mxpre[y]=max(mxpre[y<<1],mxpre[y<<1|1]);
    }
    it=s.lower_bound((node){x,a[x]});
    mxpre[x+M]= (it!=s.begin()&&(it--,it->key==a[x])) ? it->pos : 0;
    y=x+M; while(y>>=1) mxpre[y]=max(mxpre[y<<1],mxpre[y<<1|1]);
    x+=M; g[x]=Abs(val-a[x-M-1]); mx[x]=mi[x]=val; y=x;
    while(y>>=1) pushup(y);
    if(x!=n+M)
    {
        y=x+1; g[y]=Abs(a[y-M]-a[x-M]);
        while(y>>=1) g[y]=gcd(g[y<<1],g[y<<1|1]);
    }
}

void build()
{
    for(M=1;M<n+2;M<<=1);
    for(int i=M+1;i<=M+n;i++)
    {
        a[i-M]=read(); s.insert((node){i-M,a[i-M]}); it=s.lower_bound((node){i-M,a[i-M]}); it--;
        if(it!=s.begin() && it->key==a[i-M] ) mxpre[i]=it->pos;
        mx[i]=mi[i]=a[i-M];
        g[i]=Abs(a[i-M]-a[i-M-1]);
    }
    for(int i=M-1;i;i--) pushup(i);
}

void query()
{
    int l,r,k;l=read();r=read();k=read();l^=sol,r^=sol,k^=sol;
    if(l==r) {puts("Yes"); sol++; return ;}
    if(l>r) {puts("No"); return ;}
    int mxx,mii,prex;
    query_tree(l,r,mxx,mii,prex);
    if(k==0)
    {
        if(mxx==mii) puts("Yes"),sol++;
        else puts("No");
        return ;
    }
    if((mxx-mii)!=(r-l)*k) {puts("No");return ;}
    if(prex>=l) {puts("No");return ;}
    if(query_gcd(l+1,r)!=k){puts("No");return ;}
    puts("Yes"); sol++; return ;
}
int main()
{
    scanf("%d%d",&n,&m);
    build();
    while(m--)
    {
        op=read();
        switch(op)
        {
            case 1: fix();break;
            case 2: query();break;
        }
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注