题目概述

有 $n$ 个箱子，每个箱子的长宽高为 $(a_i,b_i,c_i)$（可以任意旋转），把 $[l,r]$ 的箱子装入一个大箱子需要满足区间内任意的箱子三维都小于等于大箱子，求所有区间最小体积大箱子的期望体积。

解题报告

首先要想到贪心：将每个盒子的长宽高排序，那么 $[l,r]$ 的最小体积大箱子就是 $max_amax_bmax_c$ 。

这样的话就不难想到用单调栈维护三维的最大值，然后用线段树维护以 $j$ 结尾的所有 $[i,j]$ 的答案，每次加入节点的时候就是区间乘除，询问就是区间求和。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300000,MOD=1e9+7;

int n,a[maxn+5][3],top[3],stk[3][maxn+5],sum[(maxn<<2)+5],tag[(maxn<<2)+5],ans;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
#define Pushup(p) (sum[p]=ADD(sum[(p)<<1],sum[(p)<<1|1]))
void Build(int L,int R,int p=1){
    tag[p]=1;if (L==R) {sum[p]=MUL(a[L][0],MUL(a[L][1],a[L][2]));return;}
    int mid=L+(R-L>>1);Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p);
}
inline void Addtag(int p,int k) {tag[p]=MUL(tag[p],k);sum[p]=MUL(sum[p],k);}
inline void Pushdown(int p) {if (tag[p]>1) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=1;}
void Update(int L,int R,int k,int l=1,int r=n,int p=1){
    if (L==l&&r==R) return Addtag(p,k);int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Update(L,R,k,l,mid,p<<1); else if (L>mid) Update(L,R,k,mid+1,r,p<<1|1);
    else Update(L,mid,k,l,mid,p<<1),Update(mid+1,R,k,mid+1,r,p<<1|1);Pushup(p);
}
int Ask(int L,int R,int l=1,int r=n,int p=1){
    if (L==l&&r==R) return sum[p];int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    else return ADD(Ask(L,mid,l,mid,p<<1),Ask(mid+1,R,mid+1,r,p<<1|1));
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);for (int i=1;i<=n;i++) readi(a[i][0]),readi(a[i][1]),readi(a[i][2]);
    for (int i=1;i<=n;i++) sort(a[i],a[i]+3);Build(1,n);
    for (int i=1;i<=n;ans=ADD(ans,Ask(1,i)),i++)
        for (int j=0;j<3;stk[j][++top[j]]=i,j++)
            while (top[j]&&a[stk[j][top[j]]][j]<a[i][j]){
                int now=MUL(a[i][j],Pow(a[stk[j][top[j]]][j],MOD-2));
                Update(stk[j][top[j]-1]+1,stk[j][top[j]],now);top[j]--;
            }
    printf("%lld\n",MUL(ans,Pow(((LL)n*(n+1)>>1)%MOD,MOD-2)));return 0;
}