题解：P17131 [ICPC 2025 Shanghai R] No more regrets

· · 题解

题目传送门

成功场切！感觉要拿下 OI 生涯第一个场紫了。

思路：

题意很清晰，三种操作分别是区间加，区间推平和查询区间每个位置上的前缀最大值与前缀最小值的积之和。

8s，1G 可以考虑分块，计块长为 B。

::::info[先思考如何计算贡献？]{open}

首先肯定是要记录当前的前缀最大和前缀最小的，然后我们考虑在继承前面的前缀最大最小时会如何影响当前块的前缀最大最小。

对于当前块的前缀最大值数组 A_i 和 前缀最小值数组 B_i，显然 A_i 单调递增 B_i 单调递减。

我们设 M_1 为前面所有块中的最大值，M_2 为前面所有块中的最小值，对于当前块内的位置 i，分类讨论：

  1. 对于 A_i < M_1 且 B_i>M_2 的区间 [l,r]：M_1,M_2 不受当前区间的元素影响，根据题目得到这个区间的贡献为 (r-l+1)M_1M_2，这显然是 O(1) 计算的。
  2. 对于 A_i < M_1 且 B_i \le M_2 的区间 [l,r]：此时 M_2 会不断被更新为 B_{i} 而 M_1 保持不变，因此这段区间的贡献是 \sum_{k=l}^r M_1B_k = M_1(\sum_{k=l}^r B_k)，维护块内 B_i 的前缀和就可以做到 O(1) 计算。
  3. 对于 A_i \ge M_1 且 B_i > M_2 的区间 [l,r]：类似地，此时 M_1 不断被更新为 A_{i} 而 M_2 保持不变，贡献为 \sum_{k=l}^r M_2A_k= M_2(\sum_{k=l}^r A_k)，同理维护一个 A_i 的前缀和就可以做到 O(1) 计算。
  4. 对于 A_i \ge M_1 且 B_i \le M_2 的区间 [l,r]：这时 M_1,M_2 不断被更新为 A_i,B_i，贡献为 \sum_{k=l}^r A_kB_k，对 A_iB_i 做前缀和即可 O(1) 计算。

由于 A_i,B_i 都是单调的，储存一下 A_i,B_i 的值，直接二分第一个 A_i \ge M_1 和 B_i \le M_2 的位置就可以得到 2 端点将区间分成 3 段，显然这 3 段都必然是上文 4 种区间之一，都可以 O(1) 计算。

至此我们将查询做到了 O(\frac{n \log n}{B})。 ::::

于是我们需要在块内维护的东西有：

有懒标记时需要处理标记特殊计算贡献：

查询时推平标记 cag 不为空时是显然的，整个区间要么是上文的第一类区间要么是第四类区间。

有加法标记需要推一下式子，同样二分出端点把查询的大区间分成三个区间并判断区间类型，这时计算公式中的 A_i,B_i 都需要视作增加了 add。

第一类区间的贡献公式显然无变化，因为公式里根本没有 A_i,B_i。\ 第二类区间的贡献公式会变成：\

第三类区间的贡献公式会变成：\ $$M_2(\sum_{k=l}^r (A_k+add)) = (r-l+1) \cdot M_2 \cdot add + M_2(\sum_{k=l}^r A_k) =(r-l+1) \cdot M_2 \cdot add +M_2(QA_r-QA_{l-1})$$。\ 第四类区间的贡献公式会变成： $$\sum_{k=l}^r (A_k+add)(B_k+add) = \sum_{k=l}^r (A_kB_k+(A_k+B_k)add + add^2) = \sum_{k=l}^r A_kB_k + add( \sum_{k=l}^r A_k) + add(\sum_{k=l}^r B_k) + (r-l+1)add^2 = ANS_r-ANS_{l-1} + add(QA_r-QA_{l-1}+QB_{r}-QB_{l-1}) + (r-l+1)add^2

有了这些后修改是简单的，整块块打标记，散块暴力重构即可，是 O(\frac{n}{B} +B) 一次的。

取模直接 unsigned long long 自然溢出即可。

平衡复杂度，取 B=\sqrt{n \log n} 有理论最优复杂度 O(n \sqrt{n \log n})。

代码细节非常多，码量较大，做的时候需要一定耐心。

::::success[奉上 300 行的丑陋代码]

#include <bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define ull unsigned long long
#define pb emplace_back
#define pr pair<int,int>
#define mp make_pair
#define endl "\n"
inline int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;}
void write(int x){if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');}

const int INF=1e18; 

int B=500;

struct fk{
    int l,r;
    int a[805]; 
    int qzmax[805],qzmin[805];
    ull qzhmx[805],qzhmn[805];
    ull qzans[805];
    int add,cag;
}k[805];

int wz[200005];

int mqk=0,mqs=B;

int n,q;

inline void js(int q){
    k[q].qzans[0]=0;
    k[q].qzmax[0]=-INF;
    k[q].qzmin[0]=INF;
    k[q].qzhmx[0]=0;
    k[q].qzhmn[0]=0;
    for(int i=1;i<=B;i++){
        int mq=k[q].l+i-1;
        if(1<=mq&&n>=mq){
            k[q].qzmax[i]=max(k[q].qzmax[i-1],k[q].a[i]);
            k[q].qzmin[i]=min(k[q].qzmin[i-1],k[q].a[i]);
            k[q].qzans[i]=k[q].qzans[i-1]+((ull)k[q].qzmax[i]*k[q].qzmin[i]);
        }   
        else break;
    }
    for(int i=1;i<=B;i++){
        int mq=k[q].l+i-1;
        if(1<=mq&&n>=mq){
            k[q].qzhmx[i]=k[q].qzhmx[i-1]+(ull)k[q].qzmax[i];
            k[q].qzhmn[i]=k[q].qzhmn[i-1]+(ull)k[q].qzmin[i];
        }   
        else break;
    }
}

inline void pushdown(int q){
    if(k[q].cag!=INF){
        for(int i=1;i<=B;i++){
            int mq=k[q].l+i-1;
            if(1<=mq&&n>=mq) k[q].a[i]=k[q].cag;
            else break;
        }
        js(q);
        k[q].add=0;
        k[q].cag=INF;
    }
    if(k[q].add!=0){
        for(int i=1;i<=B;i++){
            int mq=k[q].l+i-1;
            if(1<=mq&&n>=mq) k[q].a[i]+=k[q].add;
            else break;
        }
        js(q);
        k[q].add=0;
        k[q].cag=INF;
    }
}

inline void update(int ml,int mr,int kk){
    for(int i=wz[ml];i<=wz[mr];i++){
        if(ml<=k[i].l&&mr>=k[i].r){
            if(k[i].cag!=INF) k[i].cag+=kk;
            else k[i].add+=kk;
        }
        else{
            pushdown(i);
            for(int j=1;j<=B;j++){
                int mq=k[i].l+j-1;
                if(ml<=mq&&mr>=mq) k[i].a[j]+=kk;
            }
            js(i);
        }
    }
}

inline void change(int ml,int mr,int kk){
    for(int i=wz[ml];i<=wz[mr];i++){
        if(ml<=k[i].l&&mr>=k[i].r){
            k[i].cag=kk;
            k[i].add=0;
        }
        else{
            pushdown(i);
            for(int j=1;j<=B;j++){
                int mq=k[i].l+j-1;
                if(ml<=mq&&mr>=mq) k[i].a[j]=kk;
            }
            js(i);
        }
    }
}

inline ull query(int ml,int mr){
    int mina=INF,maxa=-INF;
    ull ans=0;
    for(int i=wz[ml];i<=wz[mr];i++){
        int L=k[i].l,R=min(k[i].r,n);
        if(ml<=L&&mr>=R){
            int len=R-L+1;
            if(k[i].cag!=INF){
                int v=k[i].cag+k[i].add;
                if(mina==INF){
                    mina=v;
                    maxa=v;
                    ans+=(ull)v*v;
                    ans+=(ull)v*v*(len-1);
                }
                else{
                    mina=min(mina,v);
                    maxa=max(maxa,v);
                    ans+=(ull)mina*maxa*len;
                }
            }
            else if(k[i].add!=0){
                int d=k[i].add;
                if(mina==INF){
                    mina=k[i].qzmin[len]+d;
                    maxa=k[i].qzmax[len]+d;
                    ans+=k[i].qzans[len];
                    ans+=(ull)d*(k[i].qzhmx[len]+k[i].qzhmn[len]);
                    ans+=(ull)d*d*len;
                }
                else{
                    int wmin=len+1,wmax=len+1;
                    int l=1,r=len,mid;
                    while(l<=r){
                        mid=(l+r)>>1;
                        if(k[i].qzmin[mid]<=mina-d){
                            r=mid-1;
                            wmin=mid;
                        }
                        else l=mid+1;
                    }
                    wmin--;
                    l=1;r=len;
                    while(l<=r){
                        mid=(l+r)>>1;
                        if(k[i].qzmax[mid]>=maxa-d){
                            r=mid-1;
                            wmax=mid;
                        }
                        else l=mid+1;
                    }
                    wmax--;
                    ull sum=0;
                    if(wmax<=wmin){
                        sum+=(ull)maxa*mina*wmax;
                        if(wmin>wmax){
                            sum+=(ull)mina*((k[i].qzhmx[wmin]-k[i].qzhmx[wmax])+(ull)d*(wmin-wmax));
                        }
                        if(len>wmin){
                            sum+=k[i].qzans[len]-k[i].qzans[wmin];
                            sum+=(ull)d*((k[i].qzhmx[len]-k[i].qzhmx[wmin])+(k[i].qzhmn[len]-k[i].qzhmn[wmin]));
                            sum+=(ull)d*d*(len-wmin);
                        }
                    }
                    else{
                        sum+=(ull)maxa*mina*wmin;
                        if(wmax>wmin){
                            sum+=(ull)maxa*((k[i].qzhmn[wmax]-k[i].qzhmn[wmin])+(ull)d*(wmax-wmin));
                        }
                        if(len>wmax){
                            sum+=k[i].qzans[len]-k[i].qzans[wmax];
                            sum+=(ull)d*((k[i].qzhmx[len]-k[i].qzhmx[wmax])+(k[i].qzhmn[len]-k[i].qzhmn[wmax]));
                            sum+=(ull)d*d*(len-wmax);
                        }
                    }
                    ans+=sum;
                    mina=min(mina,k[i].qzmin[len]+d);
                    maxa=max(maxa,k[i].qzmax[len]+d);
                }
            }
            else{
                if(mina==INF){
                    ans+=k[i].qzans[len];
                    mina=k[i].qzmin[len];
                    maxa=k[i].qzmax[len];
                }
                else{
                    int wmin=len+1,wmax=len+1;
                    int l=1,r=len,mid;
                    while(l<=r){
                        mid=(l+r)>>1;
                        if(k[i].qzmin[mid]<=mina){
                            r=mid-1;
                            wmin=mid;
                        }
                        else l=mid+1;
                    }
                    wmin--;
                    l=1;r=len;
                    while(l<=r){
                        mid=(l+r)>>1;
                        if(k[i].qzmax[mid]>=maxa){
                            r=mid-1;
                            wmax=mid;
                        }
                        else l=mid+1;
                    }
                    wmax--;
                    if(wmax<=wmin){
                        ans+=(ull)maxa*mina*wmax;
                        if(wmin>wmax){
                            ans+=(ull)mina*(k[i].qzhmx[wmin]-k[i].qzhmx[wmax]);
                        }
                        if(len>wmin){
                            ans+=k[i].qzans[len]-k[i].qzans[wmin];
                        }
                    }
                    else{
                        ans+=(ull)maxa*mina*wmin;
                        if(wmax>wmin){
                            ans+=(ull)maxa*(k[i].qzhmn[wmax]-k[i].qzhmn[wmin]);
                        }
                        if(len>wmax){
                            ans+=k[i].qzans[len]-k[i].qzans[wmax];
                        }
                    }
                    mina=min(mina,k[i].qzmin[len]);
                    maxa=max(maxa,k[i].qzmax[len]);
                }
            }
        }
        else{
            int bl=max(ml,L)-L+1;
            int br=min(mr,R)-L+1;
            for(int j=bl;j<=br;j++){
                int v=k[i].a[j];
                if(k[i].cag!=INF) v=k[i].cag;
                v+=k[i].add;
                if(mina==INF){
                    mina=v;
                    maxa=v;
                }
                else{
                    mina=min(mina,v);
                    maxa=max(maxa,v);
                }
                ans+=(ull)mina*maxa;
            }
        }
    }
    return ans;
}
signed main(){
    n=read();
    q=read();
    for(int i=1;i<=n;i++){
        mqs++;
        if(mqs==B+1){
            mqk++;
            mqs=1;
            k[mqk].l=(mqk-1)*B+1;
            k[mqk].r=mqk*B;
            k[mqk].add=0;
            k[mqk].cag=INF;
        } 
        k[mqk].a[mqs]=read();
        wz[i]=mqk;
    }
    for(int i=1;i<=mqk;i++) js(i);
    while(q--){
        int op,l,r,v;
        op=read();
        if(op==1){
            l=read(),r=read(),v=read();
            update(l,r,v);
        }
        else if(op==2){
            l=read(),r=read(),v=read();
            change(l,r,v);
        }
        else{
            l=read(),r=read();
            cout<<query(l,r)<<endl;
        }
    }
    return 0;
}

::::

跑得非常快，小于 1.5s。