CF1988E 解题报告（杂题选做）

Hoks · 2024-08-15 10:51:49 · 题解

前言

好题，思维难度和代码难度都很合适。

摘自杂题选做。

思路分析

如果并不带删除的话，这是一个经典问题。

我们考虑对于每一个 i，只计算他是区间最小值时的答案。

那么我们可以用单调栈维护出左右端点的取值范围，设为 L\in[l_i,i],R\in[i,r_i]。

那么对于 i 来讲，贡献即为 a_i\cdot(i-l_i+1)\cdot(r_i-i+1)。

总的贡献即为 \sum\limits_{i=1}^n a_i\cdot(i-l_i+1)\cdot(r_i-i+1)。

接着考虑来删除数。

我们考虑当 i 被删除时，j 的贡献变化了多少。

当 j=i 时，以 j 为区间最小值的贡献显然全没了，所以对于 i 的答案的贡献为 -a_j\cdot(j-l_j+1)\cdot(r_j-j+1)。
当 j<i\le r_j 时，j 的贡献从 a_j\cdot(j-l_j+1)\cdot(r_j-j+1) 变为了 a_j\cdot(j-l_j+1)\cdot(r_j-j)，作差即可。
当 r_j=i-1 时，j 有贡献的区间可以进一步往右扩展，考虑 ST 表+二分处理。
当 l_j\le i<j 时，j 的贡献从 a_j\cdot(j-l_j+1)\cdot(r_j-j+1) 变为了 a_j\cdot(j-l_j)\cdot(r_j-j+1)，作差即可。
当 l_j=i+1 时，j 有贡献的区间可以进一步向左拓展，考虑 ST 表+二分处理。

不难发现，比较难处理的就是 2. 和 4.。

我们考虑把 i,j 颠倒：

对于任意 i，他对 j\in(i,r_i] 的贡献都是 a_i\cdot(i-l_i+1)。

而对于 j\in[l_i,i) 的贡献都是 a_i\cdot(r_i-i+1)。

也就是一个区间加，考虑直接差分最后计算即可。

代码

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define int long long
using namespace std;
const int N=1e6+10,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
int n,a[N],b[N],l[N],r[N],s[N];
namespace Fast_IO
{
    static char buf[1000000],*paa=buf,*pd=buf,out[10000000];int length=0;
    #define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
    inline int read()
    {
        int x(0),t(1);char fc(getchar());
        while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
        while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
        return x*t;
    }
    inline void flush(){fwrite(out,1,length,stdout);length=0;}
    inline void put(char c){if(length==9999999) flush();out[length++]=c;}
    inline void put(string s){for(char c:s) put(c);}
    inline void print(int x)
    {
        if(x<0) put('-'),x=-x;
        if(x>9) print(x/10);
        put(x%10+'0');
    }
    inline bool chk(char c) { return !(c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='0'&&c<='9'||c=='?'); }
    inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1&&c!=' '; }
    inline void rd(char s[],int&n)
    {
        s[++n]=getchar();
        while(chk(s[n])) s[n]=getchar();
        while(ck(s[n])) s[++n]=getchar();
        n--;
    }
}
using namespace Fast_IO;
struct ST
{
    int st[20][N],lg[N];
    void clear(){for(int j=0;j<=19;j++) for(int i=1;i+(1<<j)-1<=n;i++) st[j][i]=0;}
    void get_ST(int a[])
    {
        lg[0]=-1;for(int i=1;i<=n;i++) st[0][i]=a[i],lg[i]=lg[i>>1]+1;
        for(int j=1;j<=19;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
                st[j][i]=min(st[j-1][i],st[j-1][i+(1<<j-1)]);
    }
    int get(int l,int r){int k=lg[r-l+1];return min(st[k][l],st[k][r-(1<<k)+1]);}
}st;
inline int getl(int x,int y)
{
    int l=1,r=x,res=x;
    while(l<=r)
        if(st.get(mid,x)>=y) res=mid,r=mid-1;
        else l=mid+1;
    if(st.get(res,x)<y) res++;return res;
}
inline int getr(int x,int y)
{
    int l=x,r=n,res=x;
    while(l<=r)
        if(st.get(x,mid)>=y) res=mid,l=mid+1;
        else r=mid-1;
    if(st.get(x,res)<y) res--;return res;
}
inline void solve()
{
    n=read();for(int i=1;i<=n;i++) a[i]=read();st.get_ST(a);int ss=0;
    for(int i=1;i<=n;i++) l[i]=getl(i,a[i]),r[i]=getr(i,a[i]),ss+=a[i]*(r[i]-i+1)*(i-l[i]+1);
    for(int i=1;i<=n;i++) b[i]=ss-a[i]*(r[i]-i+1)*(i-l[i]+1),s[i]=0;
    for(int i=1;i<=n;i++)
    {
        int ll=getl(l[i]-2,a[i]),rr=getr(r[i]+2,a[i]);
        b[l[i]-1]+=a[i]*(r[i]-i+1)*(l[i]-ll-1);
        b[r[i]+1]+=a[i]*(i-l[i]+1)*(rr-r[i]-1);
    }
    for(int i=1;i<=n;i++)
    {
        s[l[i]]-=a[i]*(r[i]-i+1);s[i]+=a[i]*(r[i]-i+1);
        s[i+1]-=a[i]*(i-l[i]+1);s[r[i]+1]+=a[i]*(i-l[i]+1);
    }ss=0;st.clear();
    for(int i=1;i<=n;i++) ss+=s[i],print(b[i]+ss),put(' ');put('\n');
}
signed main()
{
    int T=read();while(T--) solve();
    genshin:;flush();return 0;
}