洛谷。
题目简述
给定两个数列 \(a,b\)，有 \(q\) 次询问，每次询问 \([L,R]\) 的所有子区间 \([l,r]\) 的 \(\max_{i=l}^r a_i \times \max_{i=l}^r b_i\) 之和。其中，\(n,q \le 2.5e5\)。
分析
这很像历史版本和，但是我们写过的只有一个数组 \(a\) 的。那么先从部分分开始。
对于 \(n,q \le 3000\) 这一档直接 \(O(n^2)\) 暴力。期望得分 \(20 pts\)。
代码
namespace sub1{
#define N 3010
ull val[N][N];
void solve(){
for(int i = 1;i<=n;++i){
ull A = a[i], B = b[i];
val[i][i] = 1ull * A * B;
for(int j = i+1;j<=n;++j){
A = max(A,a[j]), B = max(B,b[j]);
val[i][j] = 1ull * A * B;
}
}
for(int r = 1;r<=n;++r)
for(int l = r-1;l;--l)
val[l][r] += val[l+1][r];
int l,r;
while(q--){
read(l),read(r);
ull ans = 0;
for(int i = l;i<=r;++i)ans += val[l][i];
printf("%llu\n",ans);
}
}
#undef N
}
然后看到 \(q \le 5\)，说明允许我们每次询问在 \(O(n \log n)\) 时间复杂度内解决问题。统计区间，还带 \(\max\) 的，使用分治。每次 dfs 到一个区间 \([l,r]\)，统计经过 \(mid\) 的区间的价值。分类讨论：\(\max a,\max b\) 都在右边/左边的，\(\max a\) 在左/右边 \(\max b\) 在右/左。期望得分 \(52pts\)。
代码
namespace sub2{
inline bool check(){ return q <= 5; }
ull al[N],ar[N],bl[N],br[N];
ull ans;
void solve(int l,int r){
if(l > r)return ;
if(l == r)return ans += a[l] * b[l],void();
int mid = (l + r) >> 1;
solve(l,mid),solve(mid+1,r);
al[mid+1] = bl[mid+1] = 0;
ar[mid] = br[mid] = 0;
for(int i = mid;i>=l;--i)
al[i] = max(al[i+1],a[i]),
bl[i] = max(bl[i+1],b[i]);
for(int i = mid+1;i<=r;++i)
ar[i] = max(ar[i-1],a[i]),
br[i] = max(br[i-1],b[i]);
for(int i = mid+1,j = mid+1;i<=r;++i){
while(j > l && al[j-1] < ar[i] && bl[j-1] < br[i])--j;
ans += ar[i] * br[i] * (mid+1-j);
}
for(int i = mid,j = mid;i>=l;--i){
while(j < r && al[i] > ar[j+1] && bl[i] > br[j+1])++j;
ans += al[i] * bl[i] * (j-mid);
}
ull sum = 0;
for(int i = mid,j = mid,k = mid+1;i>=l;--i){
while(j < r && ar[j+1] < al[i])sum += br[++j];
while(k <= j && br[k] < bl[i])sum -= br[k++];
ans += sum * al[i];
}
sum = 0;
for(int i = mid+1,j = mid+1,k = mid;i<=r;++i){
while(j > l && al[j-1] < ar[i])sum += bl[--j];
while(k >= j && bl[k] < br[i])sum -= bl[k--];
ans += sum * ar[i];
}
}
void solve(){
int l,r;
while(q--){
read(l),read(r);
ans = 0;
solve(l,r);
printf("%llu\n",ans);
}
}
}
考虑特殊性质：生成的是随机排列。我们定义 \(i\) 向左和向右走，直到遇到第一个比 \(a_i\) 大的位置，得到的区间长度为 \(d_i\)。随机排列的区间长度之和的期望不大，大致在调和级数 \(n \log n\) 级别。详细证明可以看大佬 XuYueming 的博客。那么对于每个 \(a_i\)，我们扫描区间 \([la,ra]\) 中的所有位置 \(j\) 对应到 \(b_j\) 及其 \([lb,rb]\)。对于左端点在 \([\max(la_i, lb_j), \min(i, j)]\)，右端点在 \([\max(i, j), \min(ra_i, rb_j)]\) 的所有区间价值都为 \(a_i \times b_j\)。我们把左端点和右端点分别作为平面直角坐标系的 \(x\) 轴和 \(y\) 轴，这些区间就是一个矩形，价值和就是矩形的点权和。矩形个数大概是 \(n \log n\) 级别的。我们的 \([l,r]\) 询问就是询问在平面上矩形 \(((l,l),(r,r))\) 内的点权和。扫描线加线段树维护？但是这是一个范围内的多次统计而不是全局的统计。可以使用历史版本和，离线后类似扫描线的方法去扫。这样我写到了 \(84pts\)。
代码
namespace sub3{ vectorqry[N]; vector<tuple<int,int,ull>> e[N]; ull ans[N]; int la[N],ra[N],lb[N],rb[N]; int st[N],top; void calc(ull *a,int *L,int *R){ top = 0; a[n+1] = inf; for(int i = 1;i<=n+1;++i){ while(top && a[st[top]] < a[i])R[st[top--]] = i-1; L[i] = st[top] + 1, st[++top] = i; } } void init(){ calc(a,la,ra),calc(b,lb,rb); for(int i = 1;i<=n;++i){ for(int j = la[i];j<=ra[i];++j){ if(rb[j] < i || lb[j] > i)continue; pii L (max(la[i],lb[j]), min(i,j)); pii R (max(i,j), min(ra[i],rb[j])); ull val = 1ull * a[i] * b[j]; e[get<0>(R)].emplace_back(get<0>(L),get<1>(L),val); e[get<1>(R)+1].emplace_back(get<0>(L),get<1>(L),-val); } } } struct Tag{ ull tag,tagh,tim; Tag(){ tag = tagh = tim = 0; } Tag(ull _a,ull _b,ull _c):tag(_a),tagh(_b),tim(_c){} inline Tag friend operator +(const Tag &a,const Tag &b){ Tag res = a; res.tagh += b.tagh + b.tim * res.tag; res.tag += b.tag, res.tim += b.tim; return res; } }; struct node{ int l,r; ull sum,sumh; inline void pushtag(const Tag &val){ sumh += val.tagh * (r - l + 1) + sum * val.tim; sum += val.tag * (r - l + 1); } }; struct Seg{ node tr[N << 2]; Tag tag[N << 2]; #define ls (p << 1) #define rs (p << 1|1) #define len(p) (tr[(p)].r-tr[(p)].l+1) #define mid ((tr[p].l+tr[p].r)>>1) inline void pushup(int p){ tr[p].sum = tr[ls].sum + tr[rs].sum; tr[p].sumh = tr[ls].sumh + tr[rs].sumh; } inline void pushtag(int p,const Tag &val){ tr[p].pushtag(val); tag[p] = tag[p] + val; } inline void pushdown(int p){ if(!tag[p].tag && !tag[p].tagh && !tag[p].tim)return ; pushtag(ls,tag[p]),pushtag(rs,tag[p]); tag[p] = Tag(); } void build(int p,int l,int r){ tr[p] = {l,r,0,0}, tag[p] = Tag(); if(l == r)return ; build(ls,l,mid),build(rs,mid+1,r); } void modify(int p,int l,int r,const Tag &val){ if(l <= tr[p].l && tr[p].r <= r)return pushtag(p,val),void(); pushdown(p); if(l <= mid)modify(ls,l,r,val); if(mid < r)modify(rs,l,r,val); pushup(p); } ull query(int p,int l,int r){ if(l <= tr[p].l && tr[p].r <= r)return tr[p].sumh; pushdown(p); ull res = 0; if(l <= mid)res += query(ls,l,r); if(mid < r)res += query(rs,l,r); return res; } #undef len #undef mid #undef ls #undef rs }seg; void solve(){ for(int i = 1,l,r;i<=q;++i){ read(l),read(r); qry[r].emplace_back(l,i); } init(); seg.build(1,1,n); for(int i = 1;i<=n;++i){ for(const P &p : e[i])seg.modify(1,get<0>(p),get<1>(p),Tag(get<2>(p),0,0)); seg.modify(1,1,n,Tag(0,0,1)); for(const pii &p : qry[i])ans[get<1>(p)] += seg.query(1,get<0>(p),i); } for(int i = 1;i<=q;++i)printf("%llu\n",ans[i]); }
}
话说回来，历史版本和如何同时维护两个数的乘积？我们可以考虑使用矩阵先来直观地解剖这个问题。构造结点信息，包含：结点对应区间的长度，\(a_i\) 之和，\(b_i\) 之和，\(a_i \times b_i\) 之和，以及历史 \(a_i \times b_i\) 和。然后构造修改的 Tag 矩阵，用线段树维护矩阵即可。但是这样的做法常数巨大，分数还没有之前的部分分高。
代码
namespace sub4{ bool S; int sta[N],topa; int stb[N],topb; vectorqry[N]; ull ans[N]; struct Mat{ int n,m; ull c[5][5]; Mat(){ memset(c,0,sizeof c); } Mat(int _n,int _m){ n = _n, m = _m, memset(c,0,sizeof c); } Mat(int _n){ n = m = _n; for(int i = 0;i<n;++i) for(int j = 0;j<n;++j) c[i][j] = (i == j); } inline void output(){ puts("-----------"); for(int i = 0;i<n;++i){ for(int j = 0;j<m;++j) printf("%llu ",c[i][j]); puts(""); } puts("-----------"); } inline Mat friend operator *(const Mat &a,const Mat &b){ Mat res(a.n,b.m); assert(a.m == b.n); for(int i = 0;i<res.n;++i) for(int j = 0;j<res.m;++j) for(int k = 0;k<a.m;++k) res[i][j] += a[i][k] * b[k][j]; return res; } inline bool friend operator ==(const Mat &a,const Mat &b){ if((a.n^b.n) || (a.m^b.m))return false; for(int i = 0;i<a.n;++i) for(int j = 0;j<a.m;++j) if(a[i][j] ^ b[i][j])return false; return true; } inline Mat friend operator +(const Mat &a,const Mat &b){ Mat res(a.n,a.m); assert(a.n == b.n && a.m == b.m); for(int i = 0;i<res.n;++i) for(int j = 0;j<res.m;++j) res[i][j] = a[i][j] + b[i][j]; return res; } inline Mat friend operator ^(Mat a,int k){ Mat res(a.n); while(k){ if(k & 1)res = res * a; a = a * a, k >>= 1; } return res; } ull* operator [](const int i){ return c[i]; } const ull* operator [](const int i)const{ return c[i]; } }info,mdf,empty; struct Seg{ Mat tr[N << 2], tag[N << 2]; #define ls (p << 1) #define rs (p << 1|1) #define mid ((l + r) >> 1) inline void pushup(int p){ tr[p] = tr[ls] + tr[rs]; } void build(int p,int l,int r){ tr[p] = info, tag[p] = mdf; if(l == r)return tr[p][0][0] = 1,void(); build(ls,l,mid),build(rs,mid+1,r); pushup(p); } inline void pushdown(int p){ pushtag(ls,tag[p]),pushtag(rs,tag[p]); tag[p] = mdf; } inline void pushtag(int p,const Mat &val){ tag[p] = tag[p] * val; tr[p] = tr[p] * val; } void modify(int p,int l,int r,int L,int R,const Mat &val){ if(L <= l && r <= R)return pushtag(p,val); pushdown(p); if(L <= mid)modify(ls,l,mid,L,R,val); if(mid < R)modify(rs,mid+1,r,L,R,val); pushup(p); } ull query(int p,int l,int r,int L,int R){ if(L <= l && r <= R)return tr[p][0][4]; ull res = 0; pushdown(p); if(L <= mid)res = query(ls,l,mid,L,R); if(mid < R)res += query(rs,mid+1,r,L,R); return res; } inline void adda(int l,int r,ull val){ Mat tmp = mdf; tmp[0][1] = tmp[2][3] = val; modify(1,1,n,l,r,tmp); } inline void addb(int l,int r,ull val){ Mat tmp = mdf; tmp[0][2] = tmp[1][3] = val; modify(1,1,n,l,r,tmp); } inline void upd(){ Mat tmp = mdf; tmp[3][4] = 1; modify(1,1,n,1,n,tmp); } }seg; bool T; void test(){ // same tag * <=> + Mat A = mdf; A[0][1] = A[2][3] = 4; Mat B = mdf; B[0][2] = B[1][3] = 5; Mat C = mdf; C[3][4] = 1; A.output(),C.output(); Mat res = (A ^ 3); res = res * (B ^ 2); res = res * C; res = res * (A ^ 6); res = res * (B ^ 4); res = res * C; res.output(); } void solve(){ info = Mat(1,5), mdf = Mat(5), empty = Mat(5,5); for(int i = 1,l,r;i<=q;++i){ read(l),read(r); qry[r].emplace_back(l,i); } seg.build(1,1,n); for(int i = 1;i<=n;++i){ while(topa && a[i] > a[sta[topa]])seg.adda(sta[topa-1]+1,sta[topa],-a[sta[topa]]),--topa; while(topb && b[i] > b[stb[topb]])seg.addb(stb[topb-1]+1,stb[topb],-b[stb[topb]]),--topb; seg.adda(sta[topa]+1,i,a[i]); seg.addb(stb[topb]+1,i,b[i]); sta[++topa] = i, stb[++topb] = i; seg.upd(); for(const pii &p : qry[i])ans[get<1>(p)] = seg.query(1,1,n,get<0>(p),i); } for(int i = 1;i<=q;++i)printf("%llu\n",ans[i]); }
}
矩阵辅助推式子的意义就在于我们可以把矩阵中本质不同的信息提取出来，直接写有用的点的信息转移即可。而找本质不同信息可以多乘几下，就像上面代码中的 test() 函数一样。这样常数较小，离线+单调栈+历史版本和即可。期望分数 \(100pts\)。
代码
/* 推的过程： info: 0 1 2 3 4 tag: 1 8 5 40 0 0 1 0 5 0 0 0 1 8 8 0 0 0 1 1 0 0 0 0 11 (0)(1)(2)(3)
0 1 0 (1)(4)
0 0 1 (0)(6)
0 0 0 1 (5)
0 0 0 0 1merge(info, info):
{0 + 0, 1 + 1, 2 + 2, 3 + 3, 4 + 4}
tag1 * tag2 => res
res[0] = tag1[0] + tag2[0]
res[1] = tag1[1] + tag2[1]
res[2] = tag2[2] + tag1[2] + tag1[0] * tag2[1] + tag1[1] * tag2[0]
res[3] = tag2[3] + tag1[0] * tag2[4] + tag1[1] * tag2[6] + tag1[2] * tag2[5] + tag1[3]
res[4] = tag2[4] + tag1[1] * tag2[5] + tag1[4]
res[5] = tag1[5] + tag2[5]
res[6] = tag1[6] + tag2[6] + tag1[0] * tag2[5]0 1 2 3 4
merge(info, tag)
res[0] = info[0]
res[1] = info[0] * tag[0] + info[1]
res[2] = info[2] + info[0] * tag[1]
res[3] = info[0] * tag[2] + info[1] * tag[1] + info[2] * tag[0] + info[3]
res[4] = info[0] * tag[3] + info[1] * tag[4] + info[2] * tag[6] + info[3] * tag[5] + info[4]
*/
namespace sub5{
bool S;
int sta[N],topa;
int stb[N],topb;
vectorqry[N];
ull ans[N];struct Tag{ ull c[7]; Tag(){ c[0] = c[1] = c[2] = c[3] = c[4] = c[5] = c[6] = 0; } Tag(ull c0,ull c1,ull c2,ull c3,ull c4,ull c5,ull c6){ c[0] = c0,c[1] = c1,c[2] = c2,c[3] = c3,c[4] = c4,c[5] = c5,c[6] = c6; } inline Tag friend operator +(const Tag &a,const Tag &b){ return Tag( a[0] + b[0], a[1] + b[1], a[2] + b[2] + a[0] * b[1] + a[1] * b[0], a[3] + b[3] + a[0] * b[4] + a[1] * b[6] + a[2] * b[5], a[4] + b[4] + a[1] * b[5], a[5] + b[5], a[6] + b[6] + a[0] * b[5] ); } ull & operator [](const int i){ return c[i]; } const ull & operator [](const int i)const{ return c[i]; } }empty_tag; struct Info{ ull c[5]; Info(){ c[0] = c[1] = c[2] = c[3] = c[4] = 0; } Info(ull c0,ull c1,ull c2,ull c3,ull c4){ c[0] = c0,c[1] = c1,c[2] = c2,c[3] = c3,c[4] = c4; } inline Info friend operator +(const Info &a,const Info &b){ return Info(a[0] + b[0], a[1] + b[1], a[2] + b[2], a[3] + b[3], a[4] + b[4]); } inline Info friend operator +(const Info &a,const Tag &b){ return Info( a[0], a[0] * b[0] + a[1], a[2] + a[0] * b[1], a[0] * b[2] + a[1] * b[1] + a[2] * b[0] + a[3], a[0] * b[3] + a[1] * b[4] + a[2] * b[6] + a[3] * b[5] + a[4] ); } ull & operator [](const int i){ return c[i]; } const ull & operator [](const int i)const{ return c[i]; } }empty_info; struct Seg{ Info tr[N << 2]; Tag tag[N << 2]; #define ls (p << 1) #define rs (p << 1|1) #define mid ((l + r) >> 1) inline void pushup(int p){ tr[p] = tr[ls] + tr[rs]; } void build(int p,int l,int r){ tr[p] = empty_info, tag[p] = empty_tag; if(l == r)return tr[p][0] = 1,void(); build(ls,l,mid),build(rs,mid+1,r); pushup(p); } inline void pushdown(int p){ pushtag(ls,tag[p]),pushtag(rs,tag[p]); tag[p] = Tag(); } inline void pushtag(int p,const Tag &val){ tag[p] = tag[p] + val; tr[p] = tr[p] + val; } void modify(int p,int l,int r,int L,int R,const Tag &val){ if(L <= l && r <= R)return pushtag(p,val); pushdown(p); if(L <= mid)modify(ls,l,mid,L,R,val); if(mid < R)modify(rs,mid+1,r,L,R,val); pushup(p); } ull query(int p,int l,int r,int L,int R){ if(L <= l && r <= R)return tr[p][4]; ull res = 0; pushdown(p); if(L <= mid)res = query(ls,l,mid,L,R); if(mid < R)res += query(rs,mid+1,r,L,R); return res; } inline void adda(int l,int r,ull val){ Tag tmp = empty_tag; tmp[0] = val; modify(1,1,n,l,r,tmp); } inline void addb(int l,int r,ull val){ Tag tmp = empty_tag; tmp[1] = val; modify(1,1,n,l,r,tmp); } inline void upd(){ Tag tmp = empty_tag; tmp[5] = 1; modify(1,1,n,1,n,tmp); } }seg; void solve(){ for(int i = 1,l,r;i<=q;++i){ read(l),read(r); qry[r].emplace_back(l,i); } seg.build(1,1,n); for(int i = 1;i<=n;++i){ while(topa && a[i] > a[sta[topa]])seg.adda(sta[topa-1]+1,sta[topa],-a[sta[topa]]),--topa; while(topb && b[i] > b[stb[topb]])seg.addb(stb[topb-1]+1,stb[topb],-b[stb[topb]]),--topb; seg.adda(sta[topa]+1,i,a[i]); seg.addb(stb[topb]+1,i,b[i]); sta[++topa] = i, stb[++topb] = i; seg.upd(); for(const pii &p : qry[i])ans[get<1>(p)] = seg.query(1,1,n,get<0>(p),i); } for(int i = 1;i<=q;++i)printf("%llu\n",ans[i]); }
}
反思
- 对于在 \(O(n \log n)\) 时间复杂度内的区间统计，可以使用分治。
- 随机排列的一个重要性质：左右区间长度之和的期望大小很小，为 \(n \log n\) 级别。
- 对于历史版本和、历史最大值类的推式子，可以先写成矩阵的形式，再简化式子。