题目
传送门 to luogu
思路
给定
n
n
n 个数字
A
1
,
A
2
,
A
3
,
…
,
A
n
A_1,A_2,A_3,\dots,A_n
A1,A2,A3,…,An ，能形成公差为
k
k
k 的等差数列的充要条件是下列三项同时满足。
差值合法。
∀
x
∈
[
1
,
n
)
,
k
∣
(
A
x
+
1
−
A
x
)
\forall x\in[1,n),\;k|(A_{x+1}-A_x)
∀x∈[1,n),k∣(Ax+1−Ax)极差合法。
max
x
=
1
n
A
x
−
min
x
=
1
n
A
x
=
k
(
n
−
1
)
\max_{x=1}^{n}A_x-\min_{x=1}^{n}A_x=k(n-1)
x=1maxnAx−x=1minnAx=k(n−1)未有重复。
∀
{
x
,
y
}
∈
[
1
,
n
]
,
A
x
≠
A
y
\forall \{x,y\}\in[1,n],\;A_x\ne A_y
∀{x,y}∈[1,n],Ax=Ay
其中前两个可以用线段树维护（第一个可以维护两个值之差的最大公约数），最后一个可以用
s
e
t
\tt set
set 和
m
a
p
\tt map
map 维护下一个相同的值的下标。
代码
#include<cstdio>
#include<set>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std
;
const int N
=6e5+50;
inline void rad(int &_
){
static char ch
;
while(ch
=getchar(),ch
<'0'||ch
>'9');_
=ch
-48;
while(ch
=getchar(),ch
<='9'&&ch
>='0')_
=_
*10+ch
-48;
}
int gcd(int u
,int v
){return v
?gcd(v
,u
%v
):u
;}
int n
,m
,x
,y
,z
,cnt
,opt
,las
;
int a
[N
],pre
[N
],net
[N
];
map
<int,int>mp
;
set
<int>s
[N
];
typedef set
<int>::iterator IT
;
struct node
{
int lval
,rval
,mx
,mn
,mnp
,gc
;
node(){}
node(int A
,int B
,int C
,int D
,int E
,int F
):lval(A
),rval(B
),mx(C
),mn(D
),mnp(E
),gc(F
){}
}r
;
struct SegmentTree
{
node tre
[N
<<3];
node
update(node u
,node v
){
return node(u
.lval
,v
.rval
,max(u
.mx
,v
.mx
),min(u
.mn
,v
.mn
),max(u
.mnp
,v
.mnp
),gcd(gcd(u
.gc
,v
.gc
),abs(u
.rval
-v
.lval
)));
}
void mktree(int now
,int ls
,int rs
){
if(ls
==rs
){
tre
[now
]=(node
){a
[ls
],a
[ls
],a
[ls
],a
[ls
],pre
[ls
],0};
return;
}
int noww
=now
<<1,nrs
=(ls
+rs
)>>1;
mktree(noww
,ls
,nrs
);
mktree(noww
|1,nrs
+1,rs
);
tre
[now
]=update(tre
[noww
],tre
[noww
|1]);
}
void change(int now
,int ls
,int rs
,int mb
,node val
){
if(ls
>mb
||rs
<mb
)return;
if(ls
==rs
){tre
[now
]=val
;return;}
int noww
=now
<<1,nrs
=(ls
+rs
)>>1;
change(noww
,ls
,nrs
,mb
,val
);
change(noww
|1,nrs
+1,rs
,mb
,val
);
tre
[now
]=update(tre
[noww
],tre
[noww
|1]);
}
node
query(int now
,int ls
,int rs
,int zuo
,int you
){
if(ls
>=zuo
&&rs
<=you
)return tre
[now
];
int noww
=now
<<1,nrs
=(ls
+rs
)>>1;
if(you
<=nrs
)return query(noww
,ls
,nrs
,zuo
,you
);
if(zuo
>nrs
)return query(noww
|1,nrs
+1,rs
,zuo
,you
);
return update(query(noww
,ls
,nrs
,zuo
,you
),query(noww
|1,nrs
+1,rs
,zuo
,you
));
}
}t
;
int main(){
rad(n
);rad(m
);
for(int i
=1;i
<=n
;i
++){
rad(x
);a
[i
]=x
;
if(mp
.find(x
)==mp
.end())
mp
[x
]=++cnt
,s
[cnt
].insert(i
);
else{
y
=mp
[x
];
z
=*--s
[y
].end();
pre
[i
]=z
;
net
[z
]=i
;
s
[y
].insert(i
);
}
}
t
.mktree(1,1,n
);
for(int i
=1;i
<=m
;i
++){
rad(opt
);
if(opt
==1){
rad(x
);rad(y
);
x
^=las
;y
^=las
;
net
[pre
[x
]]=net
[x
];
pre
[net
[x
]]=pre
[x
];
z
=a
[net
[x
]];
t
.change(1,1,n
,net
[x
],node(z
,z
,z
,z
,pre
[x
],0));
s
[mp
[a
[x
]]].erase(x
);
if(mp
.find(y
)==mp
.end()){
mp
[y
]=++cnt
,s
[cnt
].insert(i
);
pre
[x
]=net
[x
]=0;
}else{
z
=mp
[y
];
IT it
=s
[z
].lower_bound(x
);
if(it
==s
[z
].begin()){
pre
[x
]=0;net
[x
]=*it
;
pre
[*it
]=x
;
t
.change(1,1,n
,*it
,node(a
[*it
],a
[*it
],a
[*it
],a
[*it
],x
,0));
}else if(it
==s
[z
].end()){
--it
;
pre
[x
]=*it
;net
[x
]=0;
net
[*it
]=x
;
}else{
IT It
=--it
;++it
;
pre
[x
]=*It
;net
[x
]=*it
;
net
[*It
]=x
;pre
[*it
]=x
;
t
.change(1,1,n
,*it
,node(a
[*it
],a
[*it
],a
[*it
],a
[*it
],x
,0));
}
}
a
[x
]=y
;
t
.change(1,1,n
,x
,node(y
,y
,y
,y
,pre
[x
],0));
}else{
rad(x
);rad(y
);rad(z
);
x
^=las
;y
^=las
;z
^=las
;
r
=t
.query(1,1,n
,x
,y
);
if((r
.mx
-r
.mn
==z
*(y
-x
))&&(r
.gc
==z
||!r
.gc
)&&(r
.mnp
<x
||!z
))las
++,puts("Yes");
else puts("No");
}
}
}
鸣谢代码来源——luogu题解
神仙做法
真正的大佬是不会打线段树的。
