自动搬运

查看原文

来自洛谷，原作者为

	kilees ヾ(^▽^)))*

搬运于2025-08-24 23:06:32，当前版本为作者最后更新于2025-08-18 22:31:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11334 [NOISG 2020 Finals] Progression

很好的一道题，使我调代码调到崩溃。

一看到等差数列不难想到要差分一下，差分完后题目则变为支持区间加区间覆盖操作，求一个区间内最长相同数字的长度的题。一看见区间加区间覆盖不难想到用线段树来维护，而最长相同数字长度可仿照求最大字段和一般，求出左右最长连续长度与其数字大小，还有整个区间最大长度。分类讨论转移即可。

注意区间 $l$ 到 $r$ 的答案实际是线段树上 $l+1$ 到 $r$ 区间的答案加 $1$。且在修改区间时要注意对 $r+1$ 的点的修改。

这题花了我一晚上。。。。纯屎山

code：

// Problem: P11334 [NOISG 2020 Finals] Progression
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11334
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#include<queue>
#define endl "\n"
#define ll long long
#define db long double
#define lp p<<1
#define rp p<<1|1
#define pb push_back
#define mp make_pair
#define pe(j) (1ll<<(j))
#define foe(n) for(int i=1;i<=n;i++)
using namespace std;
inline void write(ll x);
inline ll read();
const ll N=5e6+5,INF=0x3f3f3f3f3f3f3f3f,mod=998244353;
ll n,T,ans,m,k;
ll a[N];
struct dat{
	ll l,r,sum,lm,rm,ls,rs;
	ll boj,bof;
	ll s1;
}t[N];
dat pu(dat x,dat y){
	dat ans={0,0,0,0,0,0,0,0,0,0};
	ans.sum=max(x.sum,y.sum);
	if(x.rs==y.ls)ans.sum=max(ans.sum,x.rm+y.lm);
	if(x.sum==x.r-x.l+1&&x.ls==y.ls)
		ans.lm=x.sum+y.lm,ans.ls=x.ls;
	else ans.lm=x.lm,ans.ls=x.ls;
	if(y.sum==y.r-y.l+1&&y.rs==x.rs)
		ans.rm=y.sum+x.rm,ans.rs=y.rs;
	else ans.rm=y.rm,ans.rs=y.rs;
	ans.s1=x.s1+y.s1;
	return ans;
}
void pus(ll p){
	dat x=pu(t[lp],t[rp]);
	t[p]={t[p].l,t[p].r,x.sum,x.lm,x.rm,x.ls,x.rs,t[p].boj,t[p].bof,x.s1};
}
void cv(ll p,ll tag){
	t[p].s1=(t[p].r-t[p].l+1)*tag,
	t[p].lm=t[p].rm=t[p].sum=t[p].r-t[p].l+1,
	t[p].ls=t[p].rs=tag,
	t[p].bof=tag;t[p].boj=0;
}
void add(ll p,ll tag){
	t[p].s1+=(t[p].r-t[p].l+1)*tag,
	t[p].ls+=tag;t[p].rs+=tag,
	t[p].boj+=tag;
}
void pd(ll p){
	if(t[p].bof!=INF){
		cv(lp,t[p].bof),
		cv(rp,t[p].bof),
		t[p].bof=INF;
	}
	if(t[p].boj){
		add(lp,t[p].boj),
		add(rp,t[p].boj),
		t[p].boj=0;
	}
}
void csh(ll p,ll l,ll r){
	t[p]={l,r,0,0,0,0,0,0,0,0},
	t[p].bof=INF;
	if(l==r){
		t[p].sum=t[p].lm=t[p].rm=1,
		t[p].ls=t[p].rs=a[l]-a[l-1],
		t[p].s1=a[l]-a[l-1];
		return;
	}
	ll mid=(l+r)>>1;
	csh(lp,l,mid),
	csh(rp,mid+1,r),
	pus(p);
}
void xgf(ll p,ll l1,ll r1,ll sum){
	if(l1>r1)return;
	if(t[p].l>=l1&&t[p].r<=r1){
		cv(p,sum);
		return;
	}
	pd(p);
	ll mid=(t[p].l+t[p].r)>>1;
	if(l1<=mid)xgf(lp,l1,r1,sum);
	if(r1>mid)xgf(rp,l1,r1,sum);
	pus(p);
}
void xgj(ll p,ll l1,ll r1,ll sum){
	if(l1>r1)return;
	if(t[p].l>=l1&&t[p].r<=r1){
		add(p,sum);
		return;
	}
	pd(p);
	ll mid=(t[p].l+t[p].r)>>1;
	if(l1<=mid)xgj(lp,l1,r1,sum);
	if(r1>mid)xgj(rp,l1,r1,sum);
	pus(p);
}
dat cx(ll p,ll l1,ll r1){
	if(t[p].l>=l1&&t[p].r<=r1){
		return t[p];
	}
	pd(p);
	ll mid=(t[p].l+t[p].r)>>1;
	dat ans,x;ll bo=0;
	if(l1<=mid)
		ans=cx(lp,l1,r1),bo=1;
	if(r1>mid){
		x=cx(rp,l1,r1);
		if(bo) ans=pu(ans,x);
		else ans=x;
	}
	return ans;
}
ll cx1(ll p,ll l1,ll r1){
	if(l1>r1)return 0;
	if(t[p].l>=l1&&t[p].r<=r1)
		return t[p].s1;
	pd(p);
	ll mid=(t[p].l+t[p].r)>>1,ans=0;
	if(l1<=mid)ans+=cx1(lp,l1,r1);
	if(r1>mid)ans+=cx1(rp,l1,r1);
	return ans;
}
int main(){
	// cin.tie(0);cout.tie(0);
	// ios::sync_with_stdio(false);
	n=read(),T=read();
	for(int i=1;i<=n;i++) a[i]=read();
	csh(1,1,n);
	ll bo,l,r,s,c;
	while(T--){
		bo=read(),l=read(),r=read();
		if(bo==1){
			s=read(),c=read();
			ll an=0;
			if(r+1<=n)an=cx1(1,1,r+1);
			xgj(1,l,l,s),
			xgj(1,l+1,r,c);
			if(r+1<=n)xgf(1,r+1,r+1,an-cx1(1,1,r));
		}
		else if(bo==2){
			s=read(),c=read();
			ll an=0,sx=cx1(1,1,l-1);
			if(r+1<=n)an=cx1(1,1,r+1);
			xgf(1,l,l,s-sx),
			xgf(1,l+1,r,c);
			if(r+1<=n) xgf(1,r+1,r+1,an-cx1(1,1,r));
		}
		else{
			if(l==r){putchar('1');putchar('\n');continue;}
			dat an=cx(1,l+1,r);
			write(an.sum+1);putchar('\n');
		}
	}
	return 0;
}
//------------------------------------------------------------------------------------------
//read&write
inline ll read(){
    ll x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-'0');ch=getchar();}
    return x*w;
}
inline void write(ll x){
  static ll sta[35];
  ll top=0;
  do{sta[top++] = x % 10, x /= 10;}while (x);
  while(top) putchar(sta[--top]+48);
}