传送门

Description

有 \(q\) 个询问，每个询问给定两个数\(l\) 和\(r\)，求 \(a[l:r]\) 的不同子序列的最小值之和

Solution 

校内模拟赛用了这道题，但是莫队只能拿\(80\)分，正解是猫树

当然还是莫队啦

考虑一个数加入时的贡献，就是以它为端点的区间的贡献

发现可以将现有的区间分成一段一段的，每段的最小值不同

这个可以用单调栈\(+\)倍增解决

于是就有了\(O(n\sqrt n\log n)\)的做法

但是显然过不了原题

所以想办法把\(\log\)去掉

以右端点为例，令\(f[i]\)表示\(a_i\)对区间\([1,i-1]\)的贡献

发现答案可以看成是\(f[i]-f[k],(k\leq i)\)然后再加上\(k\)以后的贡献

但是，这里的\(k\)得满足它是端点之一，且它往左的贡献很好算

那是什么？就是区间最小值啦，它往左的贡献就是\(a[k]*(k-nowl+1)\)

所以可以先预处理所有的\(f[i]\)，用\(RMQ\)算法\(O(1)\)求出区间最小值就行了

复杂度\(O(n\sqrt n)\)

附上不能看的代码

Code 

#include<bits/stdc++.h>
#define ll long long
#define db double
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
#define dbg3(x) cerr<<#x<<"\n"
#define int ll
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
const int MN=1e5+5,Mod=1e9+7;
int A,B,C,P;
ll lastAns=0;
inline int rnd(){return A=(A*B+(C^(int)(lastAns&0x7fffffffll))%P)%P;}
int n,q,l,r,a[MN];
bool f1,f2;
namespace solve1
{
    int L[MN],R[MN],st[MN],top;
    void Main()
    {
        int i;
        st[top=0]=0;
        for(i=1;i<=n;++i)
        {
            while(top&&a[st[top]]>=a[i]) --top;
            L[i]=st[top]+1;
            st[++top]=i;
        }
        st[top=0]=n+1;
        for(i=n;i;--i)
        {
            while(top&&a[st[top]]>a[i]) --top;
            R[i]=st[top]-1;
            st[++top]=i;
        }
        while(q--)
        {
            l=read(),r=read();
            ll ans=0ll;
            for(i=l;i<=r;++i)
                ans+=1ll*a[i]*1ll*(min(r,R[i])-i+1)*1ll*(i-max(l,L[i])+1);
            printf("%lld\n",ans);
        }
    }
}
ll suf1[MN],suf2[MN];
void init()
{
    int i;suf1[n+1]=suf2[n+1]=0ll;
    for(i=n;i;--i)
        suf1[i]=suf1[i+1]+1ll*a[i]*(n-i+1),
        suf2[i]=suf2[i+1]+a[i];
}
ll cal(int x,int y){return suf1[x]-suf1[y+1]-1ll*(suf2[x]-suf2[y+1])*1ll*(n-y);}
struct Ques{int l,r,id;}_[MN];int tt;
namespace solve2
{
    int Bl,bel[MN],nowl,nowr;
    ll ans[MN],Sum,nowans;
    ll s1[20][MN],s2[20][MN],p1[20][MN],p2[20][MN],f[MN],g[MN];
    bool cmp(Ques x,Ques y)
    {
        return bel[x.l]!=bel[y.l]?bel[x.l]<bel[y.l]
            :(bel[x.l]&1?x.r<y.r:x.r>y.r);
    }
    int st[MN],top;
    ll cal(int x,bool ty)
    {
        int tmp=0;
        if(!ty)
        {
            for(int i=17;~i;--i)
                if(s1[i][x]==nowr) return tmp+s2[i][x];
                else if(s1[i][x]<nowr)tmp+=s2[i][x],x=s1[i][x]+1;
            return tmp+1ll*a[x]*(nowr-x+1);
        }
        else
        {
            for(int i=17;~i;--i)
                if(p1[i][x]==nowl) return tmp+p2[i][x];
                else if(p1[i][x]>nowl)tmp+=p2[i][x],x=p1[i][x]-1;
            return tmp+1ll*a[x]*(x-nowl+1);
        }
    }
    int Log[MN],mi[20][MN];
    int cmp_(int x,int y){return a[x]<a[y]?x:y;}
    int gmin(int x,int y){int og=Log[y-x+1];return cmp_(mi[og][x],mi[og][y-(1<<og)+1]);}
    void Init()
    {
        int i,j;
        for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
        for(i=1;i<=n;++i) mi[0][i]=i;
        for(j=1;j<18;++j)for(i=1;i<=n;++i)if(i-1+(1<<j)<=n)mi[j][i]=cmp_(mi[j-1][i],mi[j-1][i+(1<<j-1)]);
        st[top=0]=0;
        for(i=1;i<=n;++i)
        {
            while(top&&a[st[top]]>=a[i]) --top;
            p1[0][i]=st[top]+1;
            p2[0][i]=1ll*(i-p1[0][i]+1)*a[i];
            st[++top]=i;
        }
        st[top=0]=n+1;
        for(i=n;i;--i)
        {
            while(top&&a[st[top]]>a[i]) --top;
            s1[0][i]=st[top]-1;
            s2[0][i]=1ll*(s1[0][i]-i+1)*a[i];
            st[++top]=i;
        }
        for(i=1;i<18;++i)
            for(j=1;j<=n;++j)
            {
                if(s1[i-1][j]>=n) s1[i][j]=n+1;
                else s1[i][j]=s1[i-1][s1[i-1][j]+1],
                     s2[i][j]=s2[i-1][j]+s2[i-1][s1[i-1][j]+1];
                if(p1[i-1][j]<=1) p1[i][j]=0;
                else p1[i][j]=p1[i-1][p1[i-1][j]-1],
                     p2[i][j]=p2[i-1][j]+p2[i-1][p1[i-1][j]-1];
            }
        nowl=1;nowr=n;
        for(i=1;i<=n;++i) f[i]=cal(i,1),g[i]=cal(i,0);
    }
    ll Cal(int x,int ty)
    {
        ll tmp=0ll;
        if(ty)
        {
            int pos=gmin(nowl,x);
            tmp=f[x]-f[gmin(nowl,x)];
            tmp+=1ll*a[pos]*(pos-nowl+1);
        }
        else
        {
            int pos=gmin(x,nowr);
            tmp=g[x]-g[gmin(x,nowr)];
            tmp+=1ll*a[pos]*(nowr-pos+1);
        }
        return tmp;
    }
    void Add(int x,bool ty){nowans+=Cal(x,ty);}
    void Del(int x,bool ty){nowans-=Cal(x,ty);}
    void Main()
    {
        Init();Bl=sqrt((db)(n));
        for(int i=1;i<=n;++i)bel[i]=(i+Bl-1)/Bl;
        std::sort(_+1,_+tt+1,cmp);
        nowl=1,nowr=0;Sum=0;nowans=0;
        for(int i=1;i<=tt;++i)
        {
            while(nowr<_[i].r) Add(++nowr,1);
            while(nowl>_[i].l) Add(--nowl,0);
            while(nowr>_[i].r) Del(nowr--,1);
            while(nowl<_[i].l) Del(nowl++,0);
            if(f2) (Sum+=nowans)%=Mod;
            else ans[_[i].id]=nowans;
        }
        if(f2) printf("%lld\n",Sum);
        else for(int i=1;i<=tt;++i) printf("%lld\n",ans[i]);
    }
}
signed main()
{   
    n=read();q=read();
    if(f2) A=read(),B=read(),C=read(),P=read();
    int i;bool c1=1,c2=1;a[0]=-Mod;
    for(i=1;i<=n;++i) a[i]=read(),c1&=(a[i]==a[1]),c2&=(a[i]>a[i-1]);
    if(c2) init();
    if(n*q<=Mod&&!f1&&!f2) {solve1::Main();return 0;}
    while(q--)
    {
        if(f2)
        {
            l=rnd()%n+1;r=rnd()%n+1;
            if(l>r)swap(l,r);
        }
        else if(f1)
        {
            l=read();r=read();
            l=((l+lastAns)%n+n)%n+1;
            r=((r+lastAns)%n+n)%n+1;
            if(l>r)swap(l,r);
        }
        else l=read(),r=read();
        if(c1) printf("%lld\n",lastAns=1ll*(1ll*(r-l+1)*1ll*(r-l+2)/2)*1ll*a[1]);
        else if(c2) printf("%lld\n",lastAns=cal(l,r));
        else _[++tt].l=l,_[tt].r=r,_[tt].id=tt;
    }
    if(!c1&&!c2){solve2::Main();return 0;}
    return 0;
}

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！