题意：一个序列，两种操作：1.单点修改 2.查询[l,r]内的数由小到大排序后能否形成公差k的等差数列
1<=n,m<=300000，0<=a[i]<=10^9，强制在线
正解是这么说的。。。若能形成公差为k的等差数列则：1.最大值=最小值+(r-l)*k ，2.相邻两数之差都为k的倍数 ，3.没有重复元素
第一个好维护，第二个差分后维护，由于公共gcd从下到上是单调不增的所以均摊log，关键在于第三个。
用set求出每个元素i后面第一个和它相等的元素nex[i]，判断[l,r]中的最小nex是否>r即可。
然而注意公差为0要特判，上面这种“不能有重复元素”的判断方法就挂了。。。
l==r也要特判。
然而还有单点修改，第一个第二个也好改，为了维护第三个，每个元素除了记录nex，还要记录前面最近的相等元素pre，修改时像双向链表那样pre->nex=nex,nex->pre=pre就好，新的pre->nex=nex->pre=this。这个过程中涉及到的点都要去线段树里更新信息。
这题还有一种哈希做法。差分后实际上就是比较一个集合是否是k,2k,3k…(n-1)k，分别维护一段区间的和与平方和（由于很大所以需要取模），比较是否与预期相等即可。
平方和公式：
文章图片
，由于有/6，维护时直接乘以6，就可以该取模取模了。
我写的是第一种。
#ifdef ONLINE_JUDGE
#define NDEBUG
#define null_type null_mapped_type
#endif
#include
#include
#define gm 1<<20
using namespace __gnu_pbds;
typedef std::pair pr;
typedef tree【线段树|BZOJ4373: 算术天才⑨与等差数列 线段树】 set;
set s;
inline int __gcd(int a,int b)
{
int c;
while(b) c=a,a=b,b=c%b;
return a;
}
int n,m;
int gcd[gm],las[gm],minn[gm],maxx[gm];
inline int max(int a,int b){return a>1,ls=o<<1,rs=ls|1;
segtree(l,mid,ls);
segtree(mid+1,r,rs);
gcd[o]=__gcd(gcd[ls],gcd[rs]);
las[o]=min(las[ls],las[rs]);
minn[o]=min(minn[ls],minn[rs]);
maxx[o]=max(maxx[ls],maxx[rs]);
}
inline void modify(int x)
{
int o=pos[x],ls,rs;
gcd[o]=cf[x],minn[o]=maxx[o]=val[x],las[o]=nex[x];
while(o>>=1)
{
ls=o<<1,rs=ls|1;
gcd[o]=__gcd(gcd[ls],gcd[rs]);
las[o]=min(las[ls],las[rs]);
minn[o]=min(minn[ls],minn[rs]);
maxx[o]=max(maxx[ls],maxx[rs]);
}
}
inline void modify_cf(int x)
{
int o=pos[x];
gcd[o]=cf[x];
while(o>>=1)
gcd[o]=__gcd(gcd[o<<1],gcd[(o<<1)|1]);
}
inline void modify_nex(int x)
{
int o=pos[x];
las[o]=nex[x];
while(o>>=1)
las[o]=min(las[o<<1],las[(o<<1)|1]);
}
inline void change_val(int x,int v)
{
int l,r;
s.erase(pr(val[x],x));
cf[x]+=v-val[x],cf[x+1]+=val[x]-v;
if(xfirst==v?a->second:0,r=b->first==v?b->second:n+1;
nex[l]=pre[r]=x;
if(l) modify_nex(l);
pre[x]=l,nex[x]=r;
s.insert(pr(val[x],x));
modify(x);
}
int get_l,get_r;
int get_gcd,get_las,get_minn,get_maxx;
void get(int l=1,int r=n,int o=1)
{
if(get_l<=l&&r<=get_r)
{
get_las=min(las[o],get_las);
get_minn=min(minn[o],get_minn);
get_maxx=max(maxx[o],get_maxx);
return;
}
int mid=l+r>>1,ls=o<<1,rs=ls|1;
if(get_l<=mid) get(l,mid,ls);
if(mid>1,ls=o<<1,rs=ls|1;
if(get_l<=mid) __get_gcd(l,mid,ls);
if(midfirst==val[i]?a->second:0;
nex[i]=b->first==val[i]?b->second:n+1;
}
segtree();
for(int i=1;
i<=m;
++i)
{
scanf("%d%d%d",&op,&x,&y);
x^=cnt,y^=cnt;
if(op==1)
change_val(x,y);
else
{
scanf("%d",&k);
k^=cnt;
puts(check(x,y,k));
}
}
return 0;
} 推荐阅读
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- 牛客 C. 子段乘积（线段树）
- 牛客挑战赛39 C 牛牛的等差数列（线段树）（*）
- 牛客 数据结构（区间修改+求区间元素平方和）
- 校门外的树 线段树版
- 树链剖分|牛客练习赛51 F-ABCBA（树链剖分，线段树，状态转移）
- 数论|bzoj 1938 - 类欧几里得+线段树
- 线段树|FZU - 2277(树链剖分或dfs序+线段树)
- 并查集|[CF938G] Shortest Path Queries
- 牛客网 练习赛25 B最长区间