P13978 数列分块入门 3 题解

_•́へ•́╬_ · 2025-09-05 23:05:04 · 题解

思路

序列分块板子。同时维护每块的原序列和排序后的样子。

修改的话，散块暴力修改再排序，整块打懒惰标记。

查询的话，散块暴力查询，整块二分。

复杂度 \mathcal O(n\sqrt{n\log n})。

实现

可以逐块处理。

#include<stdio.h>
#include<algorithm>
#define N 200009
#define B 8
using namespace std;
inline char nc()
{
    static char*l,*r,buf[99999];
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    bool t=0;char c=nc();for(;c<'0'||'9'<c;t|=c=='-',c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());if(t)x=-x;
}
int n,a[N],o[N],l[N],r[N],x[N],b[1<<B],c[1<<B];long long lazy,ans[N];
main()
{
    read(n);for(int i=0;i<n;read(a[i++]));
    for(int i=0;i<n;read(o[i]),read(l[i]),read(r[i]),read(x[i]),--l[i],--r[i],
        ans[i++]=-(1ll<<60));
    for(int i=0;i<n;i+=1<<B)
    {
        int len=1<<B;if(i>>B==n>>B)len=n-i;
        for(int j=0;j<len;++j)b[j]=c[j]=a[j|i];
        sort(c,c+len);lazy=0;
        for(int j=0;j<n;++j)if(o[j])
        {
            if(r[j]<i)continue;
            if(i+len-1<l[j])continue;
            if(l[j]<=i&&i+len-1<=r[j])
            {
                long long y=x[j]-lazy;
                if(y<=c[0])continue;
                if(c[len-1]<y)ans[j]=max(ans[j],c[len-1]+lazy);
                else ans[j]=max(ans[j],*(lower_bound(c,c+len,y)-1)+lazy);
            }
            else for(int k=max(0,l[j]-i);k<=min(len-1,r[j]-i);++k)
                if(b[k]+lazy<x[j])ans[j]=max(ans[j],b[k]+lazy);
        }
        else
        {
            if(r[j]<i)continue;
            if(i+len-1<l[j])continue;
            if(l[j]<=i&&i+len-1<=r[j])lazy+=x[j];
            else
            {
                for(int k=0;k<len;c[k]=b[k],++k)
                {
                    b[k]+=lazy;
                    if(l[j]<=(i|k))if((i|k)<=r[j])b[k]+=x[j];
                }
                sort(c,c+len);lazy=0;
            }
        }
    }
    for(int i=0;i<n;++i)if(o[i])printf("%lld\n",ans[i]==-(1ll<<60)?-1:ans[i]);
}