P11334 solution

4C45 · 2026-08-10 19:23:48 · 题解

对原数列差分，则一个区间 [l,r] 上是等差数列当且仅当 [l+1,r] 区间上值相同。

区间加等差数列即在开头加 s，后面的值都加 c。区间赋值等差数列即开头设为 s-\sum\limits_{i=1}^{L-1} d_i，后面全部赋值为 c。注意维护好 r+1 处的差分值。

时间复杂度 \mathcal O(n\log n)。维护区间和、区间左右端点值、区间前后缀最长连续段、区间内最长连续段，支持区间赋值、区间加。涉及的信息都是比较板的。

:::info[P11334]

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ir(i,a,b) for(int i=b;i>=a;i--)
#define db double
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define re return
#define len(str) (str.length())
#define inr(L,R,l,r) (l<=L and R<=r)
#define ofr(L,R,l,r) (L>r or l>R)
#define lowbit(x) (x&(-x))
#define tn2 tuple<node*,node*>
#define tn3 tuple<node*,node*,node*>
#define mt make_tuple
#define np nullptr
#define ioo cin.tie(0)->sync_with_stdio(0);cout.tie(0)->sync_with_stdio(0);
#define popc __builtin_popcount
using namespace std;
const int maxn=3e5+114;

int n,q;
ll d[maxn];
struct node
{
    ll w,lval,rval,lc,rc,lzy1,lzy2,len,ans;
    bool flag1,flag2,empty;
    node(bool ff=0)
    {
        flag1=flag2=0;
        lzy1=lzy2=0;empty=ff;
    }
} t[maxn<<2],non(1);

node pushup(node a,node b)
{
    if(a.empty) re b;
    if(b.empty) re a;
    node c;
    c.len=a.len+b.len;
    c.w=a.w+b.w;
    c.lval=a.lval;c.rval=b.rval;
    c.lc=a.lc;
    c.rc=b.rc;
    if(a.lc==a.len and a.rval==b.lval) c.lc=a.len+b.lc;
    if(b.rc==b.len and b.lval==a.rval) c.rc=a.rc+b.len;
    c.ans=max(max(max(a.ans,b.ans),max(a.lc,a.rc)),max(b.lc,b.rc));
    if(a.rval==b.lval) c.ans=max(c.ans,a.rc+b.lc);
    re c;
}
void build(int u,int L,int R)
{
    if(L==R)
    {
        t[u].lval=t[u].rval=t[u].w=d[L];
        t[u].len=1;
        t[u].lc=t[u].rc=1;
        t[u].ans=1;
    }else{
        int M=L+R>>1;
        build(2*u,L,M);
        build(2*u+1,M+1,R);
        t[u]=pushup(t[2*u],t[2*u+1]); 
    }
}
void tagset(int u,ll x)
{
    t[u].flag1=1;t[u].flag2=0;
    t[u].lzy1=x;t[u].lzy2=0;
    t[u].w=x*t[u].len;
    t[u].lc=t[u].rc=t[u].len;
    t[u].lval=x;t[u].rval=x;
    t[u].ans=t[u].len;
}
void tagadd(int u,ll x)
{
    t[u].flag2=1;
    t[u].lzy2+=x;
    t[u].w+=x*t[u].len;
    t[u].lval+=x;t[u].rval+=x;
}
void pushdown(int u)
{
    if(t[u].flag1)
    {
        tagset(2*u,t[u].lzy1);
        tagset(2*u+1,t[u].lzy1);
        t[u].lzy1=t[u].flag1=0;
    }
    if(t[u].flag2)
    {
        tagadd(2*u,t[u].lzy2);
        tagadd(2*u+1,t[u].lzy2);
        t[u].lzy2=t[u].flag2=0;
    }
}
node query(int u,int L,int R,int l,int r)
{
    if(inr(L,R,l,r)) re t[u];
    else if(ofr(L,R,l,r)) re non;
    else
    {
        int M=L+R>>1;
        pushdown(u);
        re pushup(query(2*u,L,M,l,r),query(2*u+1,M+1,R,l,r));
    }
}
void updset(int u,int L,int R,int l,int r,ll x)
{
    if(inr(L,R,l,r)) 
    {
        tagset(u,x);
    }else if(!ofr(L,R,l,r))
    {
        int M=L+R>>1;
        pushdown(u);
        updset(2*u,L,M,l,r,x);
        updset(2*u+1,M+1,R,l,r,x);
        t[u]=pushup(t[2*u],t[2*u+1]);
    }
}
void updadd(int u,int L,int R,int l,int r,ll x)
{
    if(inr(L,R,l,r)) tagadd(u,x);
    else if(!ofr(L,R,l,r))
    {
        int M=L+R>>1;
        pushdown(u);
        updadd(2*u,L,M,l,r,x);
        updadd(2*u+1,M+1,R,l,r,x);
        t[u]=pushup(t[2*u],t[2*u+1]);
    }
}

int main()
{
    ioo;
    cin>>n>>q;
    rep(i,1,n) cin>>d[i];
    ir(i,1,n) d[i]-=d[i-1];
    build(1,1,n);
    while(q--)
    {
        ll l,r,s,c,o;
        cin>>o>>l>>r;
        if(o<=2) cin>>s>>c;
        if(o==1)
        {
            ll rv;
            if(r!=n) rv=query(1,1,n,1,r+1).w;
            if(l!=r) updadd(1,1,n,l+1,r,c);
            updadd(1,1,n,l,l,s);
            if(r!=n) updset(1,1,n,r+1,r+1,rv-query(1,1,n,1,r).w);
        }else if(o==2)
        {
            ll lv,rv;
            if(l!=1) lv=query(1,1,n,1,l-1).w;
            else lv=0;
            if(r!=n) rv=query(1,1,n,1,r+1).w;
            else rv=0;
            updset(1,1,n,l,l,s-lv);
            if(l!=r) updset(1,1,n,l+1,r,c);
            lv=query(1,1,n,1,r).w;
            if(r!=n) updset(1,1,n,r+1,r+1,rv-lv);
        }
        else{
            if(l!=r) cout<<query(1,1,n,l+1,r).ans+1<<'\n';
            else cout<<1<<'\n';
        }
    }
}

:::