Solution : P10173(maxiMINImax)

Argon_Cube · 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;
}