P10173题解

发表于 更新于 本文字数： 4k 阅读时长 ≈ 4 分钟

P10173 maxiMINImax

题目传送门

思路：

题目要求对符合要求的区间进行计数，而判断一个区间是否符合要求，只和这个区间的最大/最小值有关，所以考虑每个 \(a_i\) 能在哪些区间成为最大/最小值，然后枚举中间的区间最小值，用树状数组对两侧区间的信息整合。

  1. 单调队列处理出每个 \(a_i\) 两侧，第一个比它大和比它小的点的下标，记为 \(lb_i,ls_i,rb_i,rs_i\)，其中 \(l,r\) 表示左右，\(b,s\) 表示比 \(a_i\) 大/小。

    注：若找不到比 \(a_i\) 大/小的，即 \(a_i\) 左/右的数全都比 \(a_i\) 小/大，则记为数列边界，左侧为 \(0\) ，右侧为 \(n+1\) 。

  2. 计算以 \(a_i\) 为最小值的区间数量 \(x_i=(i-ls_i)(rs_i-i)\) ，以 \(a_i\) 为最大值则记为 \(y_i=(i-lb_i)(rb_i-i)\)。

  3. 所求 \(ans\) 即可表示为：

    \[ ans=\sum_{1<i<n}\sum_{1\le j<i,a_j<a_i}\sum_{i<k\le n,a_k<a_i} (a_i-a_j)(a_i-a_k)x_iy_jy_k \]

    方便起见，用 \(\sum_{i},\sum_{j},\sum_{k}\) 代指 \(\sum_{1<i<n},\sum_{1\le j<i,a_j<a_i},\sum_{i<k\le n,a_k<a_i}\)，亦即枚举符合条件的三区间极值。

    • 注：由于 \(a_i>a_j,a_k\)，则“以 \(a_i\) 为最小值的区间”，与“以 \(a_j,a_k\) 为最大值的区间”不可能重合，不影响计数。

    \[ \begin{aligned} ans &=\sum_{i}\sum_{j}\sum_{k} (a_i-a_j)(a_i-a_k)x_iy_jy_k\\ &=\sum_{i}x_i\sum_{j}\sum_{k} \left[a_i^2-a_i\left(a_j+a_k\right)+a_ja_k\right]y_jy_k\\ &=\sum_{i}x_i \left[ a_i^2\sum_{j}\sum_{k}y_jy_k- a_i\sum_{j}\sum_{k} \left(a_j+a_k\right)y_jy_k+ \sum_{j}\sum_{k}a_ja_ky_jy_k \right]\\ &=\sum_{i}x_i \left[ a_i^2\sum_{j}\sum_{k}y_jy_k- a_i \left( \sum_{j}\sum_{k} a_jy_jy_k+ \sum_{j}\sum_{k} a_ky_jy_k \right)+ \sum_{j}\sum_{k}a_jy_ja_ky_k \right] \end{aligned} \]

    • 注意到：对于数列 \(\{a_n\},\{b_n\}\) \[\sum_{i}\sum_{j}a_ib_j=\sum_{i}\left(a_i\sum_{j}b_j\right)=\left(\sum_{i}a_i\right)\left(\sum_{j}b_j\right)\]

    \[ \begin{aligned} ans &=\sum_{i}x_i \left[ a_i^2\left(\sum_{j}y_j\right)\left(\sum_{k}y_k\right)- a_i\left[ \left(\sum_{j}a_jy_j\right)\left(\sum_{k}y_k\right)+ \left(\sum_{j}y_j\right)\left(\sum_{k}a_ky_k\right) \right]+ \left(\sum_{j}a_jy_j\right)\left(\sum_{k}a_ky_k\right) \right] \end{aligned} \]

    化简过程中应尽可能将 \(j,k\) 有关的项分离，使之可以被树状数组维护，即避免出现 \(\sum_{j}\sum_{k}f(j)g(k)\) 的出现。

  4. 到此为止，我们已经通过树状数组维护 \(\sum_{j}y_j,\sum_{k}y_k,\sum_{j}a_jy_j,\sum_{k}a_ky_k\) 来计算 \(ans\) 了，但是上式还可以继续化简使得代码更加简洁，记

    \[ \begin{aligned} L_y&(i)&=&\sum_{j}y_j\\ R_y&(i)&=&\sum_{k}y_k\\ L_{ay}&(i)&=&\sum_{j}a_jy_j\\ R_{ay}&(i)&=&\sum_{k}a_ky_k \end{aligned} \]

    则 \(ans\) 可简写为：

    \[ \begin{aligned} ans &=\sum_{i}x_i \left[ a_i^2L_y(i)R_y(i)- a_i\left[L_{ay}(i)R_y(i)+L_y(i)R_{ay}(i)\right]+ L_{ay}(i)R_{ay}(i) \right] \end{aligned} \]

    观察各项系数

    \(L_y(i)\)\(L_{ay}(i)\)
    \(R_y(i)\)\(a_i^2\)\(-a_i\)
    \(R_{ay}(i)\)\(-a_i\)\(1\)

    可因式分解

    \[ \begin{aligned} ans &=\sum_{i}x_i \left[ a_iL_y(i)-L_{ay}(i) \right] \left[ a_iR_y(i)-R_{ay}(i) \right] \end{aligned} \]

    在从左到右枚举 \(i\) 的同时，把树状数组当作桶数组使用，以 \(a_i\) 为关键字，把 \(y_i,a_iy_i\) 放进相应的桶里，同时支持查询 \(i\) 左/右侧比 \(a_i\) 小的 \(L,R\)，就可以 \(O(n\log n)\) 地计算 \(ans\) 了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,p=9712176;
int n,a[N],lb[N],ls[N],rb[N],rs[N],x[N],y[N],ans;
struct tree{
    int data[N+10]={};
    inline int lowbit(int x){return x&-x;}
    void add(int i,int x){while(i<=N-5)data[i]+=x,i+=lowbit(i);}
    int sum(int i){int ans=0;while(i)ans+=data[i],i-=lowbit(i);return ans;}
}l1,r1,l2,r2;
void init(bool flag,function<bool(int a,int b)> cmp,int *ans){
    stack<int> stk;
    stk.push(flag?n+1:0);
    for(int i=flag?n:1;flag?i>=1:i<=n;flag?i--:i++){
        while(!cmp(a[stk.top()],a[i])&&stk.size()>1)stk.pop();
        ans[i]=stk.top();
        stk.push(i);
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    init(0,[](int a,int b){return a<b;},ls);
    init(0,[](int a,int b){return a>b;},lb);
    init(1,[](int a,int b){return a<b;},rs);
    init(1,[](int a,int b){return a>b;},rb);
    for(int i=1;i<=n;i++) x[i]=(i-ls[i])%p*(rs[i]-i)%p,y[i]=(i-lb[i])%p*(rb[i]-i)%p;
    for(int i=1;i<=n;i++){r1.add(a[i],y[i]%p);r2.add(a[i],a[i]*y[i]%p);}
    for(int i=1;i<=n;i++){
        a[i]%=p;
        (ans+=x[i]%p*(a[i]*l1.sum(a[i]-1)%p-l2.sum(a[i]-1)%p+p)%p*(a[i]*r1.sum(a[i]-1)%p-r2.sum(a[i]-1)%p+p)%p)%=p;
        l1.add(a[i],y[i]%p);l2.add(a[i],a[i]*y[i]%p);
        r1.add(a[i],-y[i]%p);r2.add(a[i],-a[i]*y[i]%p);
    }
    cout<<ans;
    return 0;
}