BZOJ4373 算术天才⑨与等差数列
Description
算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。
他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。
Input
第一行包含两个正整数n,m(1<=n,m<=300000)，分别表示序列的长度和操作的次数。
第二行包含n个整数，依次表示序列中的每个数ai。
接下来m行，每行一开始为一个数op，
若op=1，则接下来两个整数x,y(1<=x<=n，0<=y<=10^9)，表示把a[x]修改为y。
若op=2，则接下来三个整数l,r,k(1<=l<=r<=n，0<=k<=10^9)，表示一个询问。
在本题中，x,y,l,r,k都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。
Output
输出若干行，对于每个询问，如果可以形成等差数列，那么输出Yes，否则输出No。
Sample Input
5 3
1 3 2 5 6
2 1 5 1
1 5 4
2 1 5 1
Sample Output
No
满足等差数列的条件：
1.gcd(ai−ai+1)%k=0(l≤i<r)
2.max(ai)−min(ai)=(r−l)∗k(l≤i≤r)
3.区间内没有重复的数3.区间内没有重复的数3.区间内没有重复的数
对于第一个，我们可以用线段树维护相邻两点值的差的gcd
对于第二个，直接维护最大最小值
对于第三个，我们记录区间内所有数上一次出现的位置，取max，如果这个位置大于l就重复了
然后对于上一次出现的数，可以直接暴力开set，大概只需要n∗2个set就够用了
然后别挥霍内存就可以了
还有一个需要注意
就是k=0的情况要特判掉
#include<bits/stdc++.h>
using namespace std;
#define N 300001
#define LD (t<<1)
#define RD (t<<1|1)
int t1;
map<int,int> mp;
set<int> s[N<<];
int n,m,val[N],pre[N];
struct Node{int gcd,minv,maxv,pre;}T[N<<],tmp1,tmp2,res;
int t2;
int read(){
int ans=,w=;char c=getchar();
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')w=-,c=getchar();
while(isdigit(c))ans=(ans<<)+(ans<<)+c-'',c=getchar();
return ans*w;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
Node merge(Node l,Node r){
res.gcd=gcd(l.gcd,r.gcd);
res.maxv=max(l.maxv,r.maxv);
res.minv=min(l.minv,r.minv);
res.pre=max(l.pre,r.pre);
return res;
}
void build(int t,int l,int r){
if(l>r)return;
if(l==r){
T[t].gcd=abs(val[l]-val[l+]);
T[t].minv=T[t].maxv=val[l];
T[t].pre=pre[l];
return;
}
int mid=(l+r)>>;
build(LD,l,mid);
build(RD,mid+,r);
T[t]=merge(T[LD],T[RD]);
}
void modify(int t,int l,int r,int pos){
if(l==r){
T[t].gcd=abs(val[l]-val[l+]);
T[t].minv=T[t].maxv=val[l];
T[t].pre=pre[l];
return;
}
int mid=(l+r)>>;
if(pos<=mid)modify(LD,l,mid,pos);
else modify(RD,mid+,r,pos);
T[t]=merge(T[LD],T[RD]);
}
Node query(int t,int l,int r,int L,int R){
if(L<=l&&r<=R)return T[t];
int mid=(l+r)>>;
if(R<=mid)return query(LD,l,mid,L,R);
if(L>mid)return query(RD,mid+,r,L,R);
return merge(query(LD,l,mid,L,mid),query(RD,mid+,r,mid+,R));
}
int main(){
freopen("4373.in","r",stdin);
freopen("4373.out","w",stdout);
scanf("%d%d",&n,&m);
int cnt=;
for(int i=;i<=n;i++){
val[i]=read();
if(!mp[val[i]]){
mp[val[i]]=++cnt;
s[cnt].insert();
s[cnt].insert(n+);
s[cnt].insert(i);
pre[i]=;
}else{
s[mp[val[i]]].insert(i);
pre[i]=*--(s[mp[val[i]]].lower_bound(i));
}
}
val[n+]=val[n];
build(,,n);
int las=;
while(m--){
int op=read();
if(op==){
int x=read()^las,y=read()^las;
int t=mp[val[x]];
int tmp=*s[t].upper_bound(x);
if(tmp!=n+){
pre[tmp]=pre[x];
modify(,,n,tmp);
}
s[t].erase(x);
if(!mp[y]){
mp[y]=++cnt;
s[cnt].insert();
s[cnt].insert(n+);
s[cnt].insert(x);
pre[x]=;
}else{
s[mp[y]].insert(x);
pre[x]=*--s[t].lower_bound(x);
}
t=mp[y];
tmp=*s[t].upper_bound(x);
if(tmp!=n+){
pre[tmp]=x;
modify(,,n,x);
}
if(x==n)val[n+]=y;
val[x]=y;
modify(,,n,x);
if(x>)modify(,,n,x-);
}else{
int l=read()^las,r=read()^las,k=read()^las;
if(l==r){printf("Yes\n");++las;continue;}
tmp1=query(,,n,l,r-);
tmp2=merge(tmp1,query(,,n,r,r));
if(!k){
if(tmp2.minv==tmp2.maxv)++las,printf("Yes\n");
else printf("No\n");
continue;
}
if(tmp1.gcd%k){printf("No\n");;continue;}
if(tmp2.pre>=l){printf("No\n");continue;}
if(tmp2.maxv-tmp2.minv!=(r-l)*k){printf("No\n");continue;}
las++;
printf("Yes\n");
}
}
printf("\n");
return ;
}