专栏文章

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

fflower1
P5278题解参与者 6已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miogyevs
此快照首次捕获于
2025/12/02 19:02
3 个月前
此快照最后确认于
2025/12/02 19:02
3 个月前
查看原文

Solution

看了其他人的做法，感觉维护相邻差分的 gcd⁡\gcd 还是有点难想到的，于是就有了这篇暴力随机化做法。
对于一个长度为 nn 的序列 aa，设其最小值为 a1a_1，最大值为 ana_n，如果它排序后能构成公差为 dd 的等差数列，要满足以下几点：
  1. an−a1=d⋅(n−1)a_n-a_1 = d \cdot (n-1) 。
  2. 序列中不存在重复元素。
  3. ∀ai,(ai−a1)∣d\forall a_i,(a_i - a_1) \mid d。
对于第一点，可以用线段树维护区间最大值与最小值。
对于第二点，可以求出每个元素，和它相同元素上一次出现的位置，如果区间所有元素上一次出现的位置小于左端点，那么区间中就没有重复元素。
可以采用线段树维护区间最值，用 mapmap 离散化后套 setset 动态维护。
对于第三点，一个很经典的做法就是随机化。
首先，若每个 ai−a1a_i-a_1 都能整除 dd ，则它们的和也一定能整除 dd。
我们开 10 个树状数组维护区间和，对于序列的每个位置，树状数组都随机以 12\frac{1}{2} 的概率维护这个值，如果有任意一个树状数组的区间和不能整除 dd ，那么就不合法，这样做程序错误的概率很低。
时间复杂度 O(nlog⁡2n)O(n \log^2 n)，空间复杂度 O(nlog⁡n)O(n \log n)，理论上难以通过，但由于数据极水可以 AC。
CPP
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ls k<<1
#define rs k<<1|1
using namespace std;
typedef long long ll;
const int N=3e5+5,M=10;
int n,m,idx,a[N],pr[N],sf[N],ans;
map<int,int>mp;
set<int>st[N<<1];
struct node{
	int mi,mx,p,gd;
};
struct tree1{
	node tr[N<<2];
	node pushup(node x,node y,int mid){
		node k;
		k.mi=min(x.mi,y.mi);
		k.mx=max(x.mx,y.mx); 
		k.p=max(x.p,y.p);
		k.gd=__gcd(__gcd(x.gd,y.gd),abs(a[mid]-a[mid+1]));
		return k;
	}
	void build(int k,int l,int r){
		if(l==r){
			tr[k]=(node){a[l],a[l],pr[l],0};
			return;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		tr[k]=pushup(tr[ls],tr[rs],mid);
	}
	void modify(int k,int l,int r,int x){
		if(l==r){
			tr[k]=(node){a[l],a[l],pr[l],0};
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid) modify(ls,l,mid,x);
		if(mid+1<=x) modify(rs,mid+1,r,x);
		tr[k]=pushup(tr[ls],tr[rs],mid);
	}
	node query(int k,int l,int r,int x,int y){
		if(x<=l&&r<=y)
			return tr[k];
		int mid=(l+r)>>1;
		if(x<=mid&&mid+1<=y) return pushup(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y),mid);
		else if(x<=mid) return query(ls,l,mid,x,y);
		else return query(rs,mid+1,r,x,y);
	}
}stk;
struct tree2{
	ll c[N];
	int d[N];
	bool vis[N];
	void build(){
		for(int i=1;i<=n;i++){
			if(rand()%2==0)
				vis[i]=true;
			add(i,a[i]);
		}
	}
	void add(int x,int v){
		if(vis[x]) return;
		for(int i=x;i<=n;i+=lowbit(i)){
			c[i]+=v;
			if(v>0) d[i]++;
			else d[i]--; 
		}
	}
	ll sum(int x){
		ll res=0;
		for(int i=x;i>=1;i-=lowbit(i))
			res+=c[i];
		return res;	
	}
	ll query(int x,int y){
		return sum(y)-sum(x-1);
	}
	int sum2(int x){
		ll res=0;
		for(int i=x;i>=1;i-=lowbit(i))
			res+=d[i];
		return res;	
	}
	int query2(int x,int y){
		return sum2(y)-sum2(x-1);
	}
}str[12];
int read(){
	int k=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
		k=k*10+ch-'0',ch=getchar();
	return k; 
}
int main(){
    srand(time(NULL));
	int opt,l,r,x,y;
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(!mp.count(a[i]))
			mp[a[i]]=++idx;
		auto it=st[mp[a[i]]].end(); 
		if(it!=st[mp[a[i]]].begin()){
			it--;
			pr[i]=*it,sf[*it]=i;
		}
		st[mp[a[i]]].insert(i);
	}
	stk.build(1,1,n);
	for(int i=1;i<=M;i++)
		str[i].build();
	for(int i=1;i<=m;i++){
		opt=read();
		if(opt==1){
			x=read()^ans,y=read()^ans;
			if(a[x]==y)
				continue;
			if(pr[x]) sf[pr[x]]=sf[x];
			if(sf[x]) pr[sf[x]]=pr[x],stk.modify(1,1,n,sf[x]);
			st[mp[a[x]]].erase(x);
			if(!mp.count(y))
				mp[y]=++idx;
			if(st[mp[y]].size()>0){
				auto it=st[mp[y]].lower_bound(x);
				if(it==st[mp[y]].end()){
					sf[x]=0;
					if(it!=st[mp[y]].begin()){
						it--;
						sf[*it]=x;
						pr[x]=*it;
					}
					else
						pr[x]=0;
				}
				else{
					sf[pr[*it]]=x,pr[x]=pr[*it];
					sf[x]=*it,pr[*it]=x;
					stk.modify(1,1,n,sf[x]);
				}
			}
			else
				pr[x]=0,sf[x]=0;
			for(int j=1;j<=M;j++)
				str[j].add(x,-a[x]),str[j].add(x,y);
			a[x]=y;
			stk.modify(1,1,n,x);
			st[mp[y]].insert(x);
		}
		else{
			l=read()^ans,r=read()^ans,x=read()^ans;
			node t=stk.query(1,1,n,l,r);
			if((r-l!=0)&&((x>0&&t.p>=l)||t.mx-t.mi!=(r-l)*x))
				printf("No\n");
			else if(x==0)
				printf("Yes\n"),ans++;
			else{
				int vl=0;
				for(int j=1;j<=M;j++){
					if((str[j].query(l,r)-1ll*t.mi*str[j].query2(l,r))%x!=0){
						vl=1;
						break;
					}
				}
				if(vl)
					printf("No\n");
				else
					printf("Yes\n"),ans++; 
			}
		}
	}
	return 0;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...