n个箱子，每个都有三个属性(a,b,c),可以任意调换属性顺序。 一段区间的价值定义为任意调换后max(a)*max(b)*max(c)的最小值。 求所有区间价值和。
把所有箱子的三个属性按降序排列，一定最优。 考虑找到了全局最大值mx，把mx调到第一维，接下来第一维答案一定是mx，而其他箱子也一定会将自己的最大值调到第一维，第二维也同理。
对三维维护单调栈。 维护线段树，位置l保存到当前r的max(a)*max(b)*max(c)。
#include<cstdio> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; typedef long long ll; const int maxn=200000+10,mo=1000000007; int top[3],a[maxn][3],tree[maxn*4][8],sta[maxn][3],st[maxn*4][3]; bool bz[maxn*4][3]; int i,j,k,l,t,n,m,tot; int ans; int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } return x; } int qsm(int x,int y){ if (!y) return 1; int t=qsm(x,y/2); t=(ll)t*t%mo; if (y%2) t=(ll)t*x%mo; return t; } void build(int p,int l,int r){ tree[p][0]=r-l+1; if (l==r) return; int mid=(l+r)/2; build(p*2,l,mid);build(p*2+1,mid+1,r); } void mark(int p,int v,int w){ bz[p][w]=1; st[p][w]=v; int i,j; fo(i,0,7) if (i&(1<<w)){ j=i^(1<<w); tree[p][i]=(ll)v*tree[p][j]%mo; } } void down(int p){ int i; fo(i,0,2) if (bz[p][i]){ mark(p*2,st[p][i],i); mark(p*2+1,st[p][i],i); bz[p][i]=0; } } void change(int p,int l,int r,int a,int b,int v,int w){ if (l==a&&r==b){ mark(p,v,w); return; } down(p); int mid=(l+r)/2; if (b<=mid) change(p*2,l,mid,a,b,v,w); else if (a>mid) change(p*2+1,mid+1,r,a,b,v,w); else change(p*2,l,mid,a,mid,v,w),change(p*2+1,mid+1,r,mid+1,b,v,w); int i,j; fo(i,0,7) if ((i&(1<<w))){ tree[p][i]=tree[p*2][i]+tree[p*2+1][i]; if (tree[p][i]>=mo) tree[p][i]-=mo; } } int query(int p,int l,int r,int a,int b){ if (l==a&&r==b) return tree[p][7]; down(p); int mid=(l+r)/2; if (b<=mid) return query(p*2,l,mid,a,b); else if (a>mid) return query(p*2+1,mid+1,r,a,b); else{ int t=query(p*2,l,mid,a,mid)+query(p*2+1,mid+1,r,mid+1,b); if (t>=mo) t-=mo; return t; } } int main(){ n=read(); fo(i,1,n){ a[i][0]=read();a[i][1]=read();a[i][2]=read(); if (a[i][1]<a[i][2]) swap(a[i][1],a[i][2]); if (a[i][0]<a[i][1]) swap(a[i][0],a[i][1]); if (a[i][1]<a[i][2]) swap(a[i][1],a[i][2]); } build(1,1,n); fo(i,1,n){ fo(j,0,2){ while (top[j]&&a[sta[top[j]][j]][j]<=a[i][j]){ change(1,1,n,sta[top[j]-1][j]+1,sta[top[j]][j],a[i][j],j); top[j]--; } sta[++top[j]][j]=i; change(1,1,n,i,i,a[i][j],j); } ans+=query(1,1,n,1,i); if (ans>=mo) ans-=mo; } t=((ll)n*(n+1)/2)%mo; ans=(ll)ans*qsm(t,mo-2)%mo; printf("%d\n",ans); fclose(stdin);fclose(stdout); return 0; }