【数据结构】你能凑出一个等差数列吗？

一个静态问题

CF407E k-d-sequence

找一个最长的子区间使得加入至多 \(k\) 个数以后，排序后是一个公差为 \(d\) 的等差数列。

多解输出 \(l\) 最小的。

\(1 \leq n \leq 2 \times 10^5,0 \leq k \leq 2 \times 10^5,0 \leq d \leq 10^9\) 。

考虑可以形成一个等差数列的条件：

1. \([l,r]\) 中所有数模 \(d\) 同余。

2. 极差不超过 \((r - l + k)d\) 。

3. 没有重复数字

考虑扫描线，从右至左扫描左端点，对于极差这个东西，可以用线段树和单调栈维护最大最小值。

记录一个 “可用的右端点” \(nr\) ，对于模 \(d\) 同余，记录 \(a_l\) 模 \(d\) 的余数，如果和 \(a_{l + 1}\) 不同，就

将 \(nr\) 直接改成 \(l\) 。对于没有重复数字这个条件，记录一个 \(set\) ，如果有重复数字就将 \(nr--\) 即可。

考虑极差不超过某个值，就是 \(max_r - min_r - rd \leq kd - ld\) 。这个更新 \(min\) 和 \(max\) 的时候顺便更新一下这个玩意的区间最小值，然后把 \(ld\) 带进去二分即可。

时间复杂度 \(\Theta(n \log n)\) 。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,M = 2e9;
typedef long long ll;
int n,k,d;
struct Seg_Tree{
	ll a[N << 2],tag[N << 2];
	inline void pushup(int pos) {a[pos] = max(a[pos << 1],a[pos << 1 | 1]);}
	inline void pushdown(int pos) 
	{
		a[pos << 1] += tag[pos];
		a[pos << 1 | 1] += tag[pos];
		tag[pos << 1] += tag[pos];
		tag[pos << 1 | 1] += tag[pos];
		tag[pos] = 0;
	}
	inline void build(int l,int r,int pos)
	{
		if(l == r) {a[pos] = 1ll * l * d + 1ll * k * d; return;}
		int mid = (l + r) >> 1;
		build(l,mid,pos << 1); build(mid + 1,r,pos << 1 | 1);
		pushup(pos);
	}
	inline void modify(int l,int r,int L,int R,ll k,int pos)
	{
		if(L <= l && r <= R) {a[pos] += k; tag[pos] += k; return;}
		int mid = (l + r) >> 1;
		pushdown(pos);
		if(L <= mid) modify(l,mid,L,R,k,pos << 1);
		if(R > mid) modify(mid + 1,r,L,R,k,pos << 1 | 1);
		pushup(pos);
	}
	inline int query(int l,int r,int L,int R,ll req,int pos)
	{
		if(!(L <= l && r <= R))
		{
			int mid = (l + r) >> 1;
			pushdown(pos); pushup(pos);
			int ret = 0;
			if(L <= mid) ret = max(ret,query(l,mid,L,R,req,pos << 1));
			if(R > mid) ret = max(ret,query(mid + 1,r,L,R,req,pos << 1 | 1));
			return ret;
		}
		if(l == r) {return (a[pos] >= req) ? l : L;}
		int mid = (l + r) >> 1;
		pushdown(pos);
		pushup(pos);
		if(a[pos << 1 | 1] >= req) return query(mid + 1,r,L,R,req,pos << 1 | 1);
		else return query(l,mid,L,R,req,pos << 1);
	}
	inline ll qval(int l,int r,int x,int pos)
	{
		if(l == r) return a[pos];
		pushdown(pos); pushup(pos); 
		int mid = (l + r) >> 1;
		if(x <= mid) return qval(l,mid,x,pos << 1);
		else return qval(mid + 1,r,x,pos << 1 | 1); 
	}
}t;
int a[N];
inline void solve1()
{
	int ansl = 1,ansr = 1;
	for(int i = 1,j;i <= n;i++)
	{
		j = i;
		while(j < n && a[j + 1] == a[i]) ++j;
		if(j - i + 1 > ansr - ansl + 1) ansr = j,ansl = i; 
	}
	cout<<ansl<<" "<<ansr;
}
struct Stack{
	int s[N],top = 0;
	inline int front() {return s[top];}
	inline int scd() {return s[top - 1];}
	inline void push(int x) {s[++top] = x;}
}mx,mn;
set <int> s;
int main()
{
	cin>>n>>k>>d;
	for(int i = 1;i <= n;i++) cin>>a[i],a[i] += 1e9;
	if(!d) {solve1(); return 0;}
	int ansl = n,ansr = n;
	t.build(1,n,1); mx.s[0] = n + 1; mn.s[0] = n + 1;
	for(int l = n,r = n,nr = n,mod = a[n] % d;l >= 1;l--) 
	{
		int lst = l + 1;
		while(mx.top > 0 && a[l] >= a[mx.front()]) 
		{
			t.modify(1,n,lst,mx.scd() - 1,a[mx.front()],1);
			lst = mx.scd();
			--mx.top;
		}
		mx.push(l);
		t.modify(1,n,l,lst - 1,-a[l],1);
		
		lst = l + 1;
		while(mn.top > 0 && a[l] <= a[mn.front()])
		{
			t.modify(1,n,lst,mn.scd() - 1,-a[mn.front()],1);
			lst = mn.scd();
			--mn.top;
		}
		mn.push(l);
		t.modify(1,n,l,lst - 1,a[l],1);
		
		if(mod != a[l] % d) nr = l,s.clear(),mod = a[l] % d;
		while(s.find(a[l]) != s.end()) s.erase(a[nr]),nr--;
		s.insert(a[l]);
		
		int ar = t.query(1,n,l,nr,1ll * l * d,1);
		if(ar - l + 1 >= ansr - ansl + 1) ansr = ar,ansl = l;
	}
	cout<<ansl<<" "<<ansr;
	return 0;
}

一个动态问题

P5278 算术天才⑨与等差数列

给定长度为 \(n\) 的序列 \(a_i\) ，有 \(m\) 次操作，分为两种：

1 x y ：将 \(a_x\) 修改为 \(y\) 。

2 l r k ：询问区间 \([l,r]\) 的数能否恰好构成一个公差为 \(k\) 的等差数列。

\(1 \leq n,m \leq 3 \times 10^5,0 \leq a_i,y,k \leq 10^9\) 。

强制在线。

再来考虑充要条件：

1. 没有相同的数

2. 极差为 \((r - l)k\)

我们发现，这个时候你不能再通过模 \(k\) 的限制做了，因为 \(k\) 在变化。

考虑其他的条件，发现任意两项的差都是 \(k\) 的倍数。

于是有了这条限制：

3. 定义差分序列 \(b_i = a_i - a_{i + 1}\) ，\(|\gcd_{i = l}^{r - 1}b_i| = k\) 。

我们发现，如果满足前两个条件，又满足第三个条件，那么这一定是一个等差数列，如果不满足第三个条件，就一定不是。

而且上文又提到等差数列一定满足条件 \(3\) ，所以条件 \(123\) 是充要的。

这样，对于相同的数，我们套路地维护 \(pre_i\) 表示 \(i\) 前面最近的等于 \(a_i\) 的位置，没有相同的数就是 \(\max_{i = l}^r pre_i < l\) 。

所以，外面用 \(set\) 维护所有数的出现位置，里面用线段树维护 \(max,min,pre,gcd\) 即可。

时间复杂度 \(\Theta(n \log n)\) 。

什么？你说 pushup 的时候暴力 gcd 复杂度 \(\log^2 n\) ？事实上不能将 \(\log\) 次 gcd 单纯地看成 \(\Theta(\log ^2n)\) 。考虑上一层要 gcd 的值一定基于当前层 gcd 的值，我们都知道辗转相除一次至少减半，所以可以看作 \(b_i\) 从底层向上和很多个数 gcd 到顶层，辗转相除次数不会超过 \(\Theta(\log n)\) 。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5,inf = 2e9;
struct Segment_Tree{
	int maxi[N << 2],mini[N << 2],g[N << 2],pre[N << 2];
	inline void pushup1(int pos) {maxi[pos] = max(maxi[pos << 1],maxi[pos << 1 | 1]); mini[pos] = min(mini[pos << 1],mini[pos << 1 | 1]);}
	inline void pushup2(int pos) {g[pos] = __gcd(g[pos << 1],g[pos << 1 | 1]);}
	inline void pushup3(int pos) {pre[pos] = max(pre[pos << 1],pre[pos << 1 | 1]);}
	inline void modify_num(int l,int r,int x,int k,int pos)
	{
		if(l == r) {maxi[pos] = mini[pos] = k; return;}
		int mid = (l + r) >> 1;
		if(x <= mid) modify_num(l,mid,x,k,pos << 1);
		else modify_num(mid + 1,r,x,k,pos << 1 | 1);
		pushup1(pos);
	}
	inline void modify_del(int l,int r,int x,int k,int pos)
	{
		if(l == r) {g[pos] = k; return;}
		int mid = (l + r) >> 1;
		if(x <= mid) modify_del(l,mid,x,k,pos << 1);
		else modify_del(mid + 1,r,x,k,pos << 1 | 1);
		pushup2(pos);
	}
	inline void modify_pre(int l,int r,int x,int k,int pos)
	{
		if(l == r) {pre[pos] = k; return;}
		int mid = (l + r) >> 1;
		if(x <= mid) modify_pre(l,mid,x,k,pos << 1);
		else modify_pre(mid + 1,r,x,k,pos << 1 | 1);
		pushup3(pos);
	}
	inline pair <int,int> query_num(int l,int r,int L,int R,int pos)
	{
		if(L <= l && r <= R) return make_pair(maxi[pos],mini[pos]);
		int mid = (l + r) >> 1; pair <int,int> now,ret = make_pair(-inf,inf);
		if(L <= mid) now = query_num(l,mid,L,R,pos << 1),ret.first = max(ret.first,now.first),ret.second = min(ret.second,now.second);
		if(R > mid) now = query_num(mid + 1,r,L,R,pos << 1 | 1),ret.first = max(ret.first,now.first),ret.second = min(ret.second,now.second);
		return ret;
	}
	inline int query_del(int l,int r,int L,int R,int pos)
	{
		if(L <= l && r <= R) return g[pos];
		int mid = (l + r) >> 1,ret = 0;
		if(L <= mid) ret = __gcd(ret,query_del(l,mid,L,R,pos << 1));
		if(R > mid) ret = __gcd(ret,query_del(mid + 1,r,L,R,pos << 1 | 1));
		return ret;
	}
	inline int query_pre(int l,int r,int L,int R,int pos)
	{
		if(L <= l && r <= R) return pre[pos];
		int mid = (l + r) >> 1,ret = 0;
		if(L <= mid) ret = max(ret,query_pre(l,mid,L,R,pos << 1));
		if(R > mid) ret = max(ret,query_pre(mid + 1,r,L,R,pos << 1 | 1));
		return ret;
	}
}t;
map <int,int> mp;
set <int> s[N * 2];
int n,m,a[N],cnt = 0;
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i <= n;i++) cin>>a[i];
	for(int i = 1;i <= n;i++)
	{
		if(mp.find(a[i]) == mp.end()) mp[a[i]] = ++cnt;
		if(s[mp[a[i]]].size()) t.modify_pre(1,n,i,*s[mp[a[i]]].rbegin(),1);
		s[mp[a[i]]].insert(i);
	}
	for(int i = 1;i <= n - 1;i++) t.modify_del(1,n,i,a[i] - a[i + 1],1);
	for(int i = 1;i <= n;i++) t.modify_num(1,n,i,a[i],1);
	for(int i = 1,op,x,y,k,yesnum = 0;i <= m;i++)
	{
		cin>>op>>x>>y;
		x ^= yesnum; y ^= yesnum; 
		if(op == 1)
		{
			int ori = mp[a[x]],pr = 0,sf = 0;
			s[ori].erase(x);
			set <int> :: iterator it = s[ori].lower_bound(x);
			if(it != s[ori].begin()) 
			{
				it--;
				pr = *it;
				it++;
			}
			if(it != s[ori].end()) sf = *it;
			if(sf) t.modify_pre(1,n,sf,pr,1);
			s[ori].erase(x);
			a[x] = y;
			if(mp.find(a[x]) == mp.end()) mp[a[x]] = ++cnt;
			ori = mp[a[x]]; pr = 0; sf = 0;
			s[ori].insert(x);
			it = s[ori].find(x);
			if(it != s[ori].begin())
			{
				it--;
				pr = *it;
				it++;
			}
			it++;
			if(it != s[ori].end()) sf = *it;
			t.modify_pre(1,n,x,pr,1);
			if(sf) t.modify_pre(1,n,sf,x,1);
			
			t.modify_del(1,n,x,a[x] - a[x + 1],1);
			if(x > 1) t.modify_del(1,n,x - 1,a[x - 1] - a[x],1);
			
			t.modify_num(1,n,x,a[x],1); 
		}
		else
		{
			cin>>k;
			k ^= yesnum;
			pair <int,int> num = t.query_num(1,n,x,y,1);
			if(k == 0)
			{
				if(num.first == num.second) puts("Yes"),++yesnum;
				else puts("No");
				continue;
			}
			if(x == y) {puts("Yes"),++yesnum; continue;}
			if(num.first - num.second == 1ll * (y - x) * k && abs(t.query_del(1,n,x,y - 1,1)) == k && t.query_pre(1,n,x,y,1) < x) puts("Yes"),++yesnum;
			else puts("No");
		}
	}
	return 0;
 } 

本栏目推荐文章
• Jmeter 如何连接mysql数据库？
• SQL Server 检测是不是数字型数据的两种方法
• 如何通过Navicat把MySQL远程数据库导入到本地数据库
• 和利时MACS6通过dat文件实现任意时间范围与测点的历史数据提取与科研分析
• 深入理解spring框架：剖析多线程模式下数据库连接
• 数据可视化是如何帮助大型企业提高效率的？
• redis 数据库
• openpyxl模块--------------------------------重复数据
• Django客户端应用1向服务端应用2发送POST请求并接收解析数据
• 数据可视化是如何帮助我们高效了解数据的？

等差 数列 数据结构 结构 数据等差 数列 数据结构 结构 等差 数列 等差 数列 数学shmily 等差 蓝桥 数列8682 等差 数列nflspc p9936 等差 数列1027 等差 蓝桥 数列 素数 等差 数列 算法 等差 数列 生成器 等差 数列 梯形 面积