自动搬运

查看原文

来自洛谷，原作者为

	Argon_Cube So now I am trapped in my Eternal Subconscienc∃.

搬运于2025-08-24 22:55:24，当前版本为作者最后更新于2024-02-18 19:44:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先看到三个区间肯定是枚举中间那个，然后看到 $\min/\max$ 就考虑做单调栈然后枚举区间的 $\min/\max$。

其次我们发现三个区间不交的条件是没用的，也就是说只要有两个区间有交集那么这种方案一定贡献为 $0$。证明很简单，我们发现如果 $r_1\geq l_2$ 也就是前两个区间有交，交集包含 $x$ 那么 $\min_2\leq x\leq \max_1$ 从而 $\min_2-\max_1\leq 0$。

现在我们只需要保证 $\min_2>\max(\max_1,\max_3)$，我们从小到大加入数并让当前加入的数为 $\min_2$。即可满足这个条件。容易用单调栈跑出每一个数 $a_i$ 作为区间 $\min/\max$ 时合法的区间数 $c_i/d_i$。于是此时包含 $\min_2$ 的贡献为 $\sum c_{\min_2}d_{\max_1}d_{\max_3}(\min_2-\max_1)(\min_2-\max_3)$，拆一下发现只需要知道容易用树状数组维护的 $\sum d_{\max_1}$、$\sum d_{\max_3}$、$\sum d_{\max_1}\max_1$、$\sum d_{\max_3}\max_3$ 即可快速计算。

#include <algorithm>
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <stack>
#include <array>

using namespace std;

stack<int,vector<int>> mnstk;
array<int,1000002> vals,ivals,bidt1,bidt2,bidt3,bidt4,rgln,rgrn,rglx,rgrx;
const int moder=9712176;

inline void update(int idx,long long val,int cnt,decltype(bidt1)& bidt)
{
    while(idx<=cnt)
        bidt[idx]=(bidt[idx]+val)%moder,idx+=-idx&idx;
}
inline int query(int idx,decltype(bidt1)& bidt)
{
    int result=0;
    while(idx)
        result=(result+bidt[idx])%moder,idx-=idx&-idx;
    return result;
}

int main(int argc,char* argv[],char* envp[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cnt;
    cin>>cnt;
    for(int i=1;i<=cnt;i++)
        cin>>vals[i],ivals[vals[i]]=i;
    vals[0]=vals[cnt+1]=0;
    mnstk.push(0);
    for(int i=1;i<=cnt+1;i++)
    {
        while(vals[mnstk.top()]>vals[i])
            rgrn[mnstk.top()]=i,mnstk.pop();
        rgln[i]=mnstk.top();
        mnstk.push(i);
    }
    mnstk.pop();
    vals[0]=vals[cnt+1]=cnt+1;
    for(int i=1;i<=cnt+1;i++)
    {
        while(vals[mnstk.top()]<vals[i])
            rgrx[mnstk.top()]=i,mnstk.pop();
        rglx[i]=mnstk.top();
        mnstk.push(i);
    }
    int answer=0;
    for(int idx=1;idx<=cnt;idx++)
    {
        long long i=ivals[idx];
        long long cntn=(rgrn[i]-i+0ll)*(i-rgln[i])%moder,cntx=(rgrx[i]-i+0ll)*(i-rglx[i])%moder;
        long long a=query(i,bidt1),b=query(cnt-i+1,bidt2),c=query(i,bidt3),d=query(cnt-i+1,bidt4);
        answer=(answer+cntn*((c*d-idx*((a*d+b*c)%moder)%moder+moder+a*b%moder*idx%moder*idx)%moder))%moder;
        // cerr<<idx<<' '<<i<<' '<<cntn<<' '<<cntx<<' '<<answer<<'\n';
        update(i,cntx,cnt,bidt1),update(cnt-i+1,cntx,cnt,bidt2),update(i,cntx*idx,cnt,bidt3),update(cnt-i+1,cntx*idx,cnt,bidt4);
    }
    cout<<answer;
    return 0;
}