题解：P11334 [NOISG 2020 Finals] Progression
P11334 [NOISG 2020 Finals] Progression
很好的一道题，使我调代码调到崩溃。
一看到等差数列不难想到要差分一下，差分完后题目则变为支持区间加区间覆盖操作，求一个区间内最长相同数字的长度的题。一看见区间加区间覆盖不难想到用线段树来维护，而最长相同数字长度可仿照求最大字段和一般，求出左右最长连续长度与其数字大小，还有整个区间最大长度。分类讨论转移即可。
注意区间
这题花了我一晚上。。。。纯屎山
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);
}