历史版本线段树；扫描线：区间的所有子区间 trick
Problem
给长为 \(n\) 的排列 \(a,b\)。\(Q\) 次询问 \(L,R\)，回答这个东西：
\[\sum_{L\leq l\leq r\leq R}maxa(l,r)maxb(l,r)
\]
其中 \(maxa(l,r)=\max_{l\leq i\leq r}a_i\)，\(maxb\) 同理。数据范围全部 \(2\times 10^5\)。
solution
首先离线。
扫描线，考虑维护一个 \(s\) 数组，将 \(r\) 右移的过程中，将所有 \(1\leq l\leq r\) 的 \(s_l\) 都加上 \(maxa(l,r)maxb(l,r)\)，然后统一处理右端点为 \(r\) 的询问：直接区间查询 \([L,R]\) 的 \(s\) 的和。我们的 \(s\) 是不清空的，所以这样就能覆盖到所有合法的小区间。
但是 \(maxa(l,r)maxb(l,r)\) 这个东西很扭曲，我们不妨将 \(maxa\) 单独拎出来作为一个数组，每当指针移动加进来一个数，总是这个数组的一段后缀给改成一个相同的数（单调栈可以求出这个分界点），所以我们可以认为我们需要解决这样一个问题：
- 维护 \(a,b,h\)（\(s\) 数组改名为 \(h\)）三个数组。
- 区间覆盖 \(a\)。
- 区间覆盖 \(b\)。
- 对所有 \(i\)，\(h_i:=h_i+a_ib_i\)。
- 区间求和 \(h\)。
我们切出去看看一维版本（P3246 [HNOI2016] 序列）和一个叫做双半群模型的东西。
半群，双半群模型
半群
给定集合 \(A\) 以及 \(A\) 上的二元运算 \(*:A\to A\to A\)。
该运算应满足结合律：\(\forall a,b,c\in A, a*(b*c)=(a*b)*c\)。
幺半群
幺半群是一个半群，而且幺半群有幺元 \(e\in A\) 使得 \(e*a=a*e=a\)。
交换半群
交换半群是一个半群且满足交换律：\(\forall a,b\in A,a*b=b*a\)。
范围
常见的范围有序列区间，树简单路径，二维平面矩形，高维正交范围，半平面范围，圆范围。
我们一般理解成对于进行修改和查询的信息的限制。
双半群模型
其中 \(Q\) 就是范围，\(M\) 就是标记，\(I\) 认为是下标，\(d\) 就是维护的信息。这就是双半群模型的定义。
通用线段树
我们简化一下上面那玩意并提出“通用线段树”。（名字我自己取的）
线段树，将一个序列 \([1,n]\) 拆分成 \(O(n)\) 个区间，每个区间一个节点，除叶子节点外区间 \([l,r]\) 都有两个儿子 \([l,mid]\) 和 \((mid,r]\)。对于这个序列的任意区间，都能被拆分成 \(O(\log n)\) 个线段树上的小区间，而且树的高度是 \(O(\log n)\)。线段树支持可持久化，抠掉一半的儿子就是树状数组。
线段树上维护了信息（Answer,\(A\)）和标记（Tag,\(T\)），他们之间要有运算：
- \(+:A\to A\to A\) 满足结合律 \(\forall a,b,c\in A,(a+b)+c=a+(b+c)\)，交换律 \(\forall a,b\in A,a+b=b+a\)。
- \(*:A\to T\to A\) 或者 \(T\to T\to T\)，满足结合律 \(\forall a\in A\cup T,\forall b,c\in T,(a*b)*c=a*(b*c)\)。
- \(*\) 对 \(+\) 要有分配律 \(\forall a,b\in A,c\in T,(a+b)*c=a*c+b*c\)。
只要你能写出这些东西的函数表示/矩阵表示/代码表示而且复杂度还行，那么一般来说就能线段树。
当然我们有一些东西只能写出满足结合律的 \(+\)，那么这个可以支持单点修改和区间查询。
历史版本线段树
- 维护 \(a,h\) 两个数组。
- 区间覆盖 \(a\)。
- 对所有 \(i\)，\(h_i:=h_i+a_i\)。
- 区间求和 \(h\)。
这个东西被称作“历史版本线段树”因为你可以对 \(a\) 做一些操作后做一次 \(h:=h+a\) 保存它的历史版本的和，然后求和。这实际上是一个三维的东西。
本题
考虑做法：我们写出 \(+\) 和 \(*\) 就行。明显要维护的量（即 \(A\)）有 \(\sum h\) 还有区间长度 \(len\)（一般都可以把区间长度作为维护信息，好写很多）。考虑标记：
- 有一个 \(\sum h:=\sum h+\sum xy\) 所以还要维护一下 \(\sum xy\)
- 有一个覆盖操作，两次覆盖，那么 Tag 里面得有 \(cx,cy\) 表示覆盖；覆盖完了我们发现这个逆天 \(\sum xy\) 竟然这样变化：
- \(cx\land cy\) 时 \(\sum xy:=cx\times cy\times len\)
- \(cx\) 时 \(\sum xy:=cx\sum y\) 完了要维护 \(\sum y\)
- \(cy\) 时 \(\sum xy:=cy\sum x\) 完了要维护 \(\sum x\)
- 没有覆盖时原地不动
经过上面的讨论我们发现 Answer 要维护 \(\sum x,\sum y,\sum xy,\sum h,len\) 这五个量。接下来可以用矩阵刻画一下 Tag 矩阵了。
但是矩阵乘法过不去。
矩阵写法，全部代码见 Codes
t.modify(vector<dot>{
dot{4,0,(LL)a[0][r]},
dot{1,1,1ull},
dot{1,2,(LL)a[0][r]},
dot{3,3,1ull},
dot{4,4,1ull}
},pos[0][r]+1,r,1,1,n);
t.modify(vector<dot>{
dot{0,0,1ull},
dot{4,1,(LL)a[1][r]},
dot{0,2,(LL)a[1][r]},
dot{3,3,1ull},
dot{4,4,1ull}
},pos[1][r]+1,r,1,1,n);
t.modify(vector<dot>{
dot{0,0,1ull},
dot{1,1,1ull},
dot{2,2,1ull},
dot{2,3,1ull},
dot{3,3,1ull},
dot{4,4,1ull}
},1,r,1,1,n);
//dot: {x,y,d}->a[x][y]=d
//Answer: {sx,sy,sxy,sh,len}
那么就维护有用的值。打表，或者猜测，知道 Tag 中要维护 \(cx,cy,fxy,fl,fx,fy\) 表示 \(\sum h:=\sum h+fxy\sum xy+fx\sum x+fy\sum y+fl\times len\)，它们出现是因为在做 \(*:T\to T\to T\) 的时候（相当于两个标记先后打在同一个 Answer 上时，用一个新的 Tag 刻画），修改 \(\sum xy\) 后，新的 \(\sum xy\) 会变成关于 \(\sum x,\sum y,\sum xy,len\) 的一个函数，在做下一个标记的 \(\sum h:=\sum h+\sum xy\) 时要代入进去，就要展开成这个东西。
那么就写吧，就是一遍一遍的代入，求值，拆出未知数和系数，最后看一下成果：
点击查看代码
typedef unsigned long long LL;
struct Tag{LL cx,cy,fxy,fx,fy,fl;};
struct Ans{LL sx,sy,sxy,sh,len;};
Ans operator+(Ans a,Ans b){
return {a.sx+b.sx,a.sy+b.sy,a.sxy+b.sxy,a.sh+b.sh,a.len+b.len};
}
Ans operator*(Ans a,Tag t){
a.sh+=a.sx*t.fx+a.sy*t.fy+a.sxy*t.fxy+a.len*t.fl;
if(t.cx&&t.cy) a.sxy=t.cx*t.cy*a.len;
else if(t.cx) a.sxy=t.cx*a.sy;
else if(t.cy) a.sxy=a.sx*t.cy;
if(t.cx) a.sx=t.cx*a.len;
if(t.cy) a.sy=t.cy*a.len;
return a;
}
Tag operator*(Tag a,Tag b){
if(a.cx) b.fl+=b.fx*a.cx,b.fx=0;
if(a.cy) b.fl+=b.fy*a.cy,b.fy=0;
if(a.cx&&a.cy) b.fl+=b.fxy*a.cx*a.cy,b.fxy=0;
else if(a.cx) b.fy+=b.fxy*a.cx,b.fxy=0;
else if(a.cy) b.fx+=b.fxy*a.cy,b.fxy=0;
b.fxy+=a.fxy,b.fx+=a.fx,b.fy+=a.fy,b.fl+=a.fl;
if(!b.cx) b.cx=a.cx; if(!b.cy) b.cy=a.cy;
return b;
}
刚才说的一维版本的线段树，留作练习。
查看答案
const LL none=1e18;
struct Ans{LL sa,sh,len;};
struct Tag{LL cover,fa,fl;};
Ans operator+(Ans a,Ans b){
return {a.sa+b.sa,a.sh+b.sh,a.len+b.len};
}
Tag operator*(Tag a,Tag b){
return {
b.cover==none?a.cover:b.cover,
a.fa+(a.cover==none)*b.fa,
a.fl+b.fl+(a.cover!=none)*b.fa*a.cover
};
}
Ans operator*(Ans a,Tag b){
return {
b.cover==none?a.sa:b.cover*a.len,
a.sh+b.fa*a.sa+b.fl*a.len,
a.len
};
}
Codes
矩阵
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef unsigned long long LL;
struct dot{int x,y; LL d;};
vector<dot> unique(const vector<dot>&a){//应该是一些 Ans 进来
vector<LL> buc(5);
for(dot p:a) buc[p.y]+=p.d;
vector<dot> c;
for(int i=0;i<5;i++) if(buc[i]) c.push_back(dot{0,i,buc[i]});
return c;
}
vector<dot> multiple(const vector<dot>&a,const vector<dot>&b){
vector<dot> c; if(a.empty()) return b; if(b.empty()) return a;
for(dot p:a) for(dot q:b) if(p.y==q.x) c.push_back(dot{p.x,q.y,p.d*q.d});
return c;
}
vector<dot> addition(vector<dot> a,const vector<dot>&b){
a.insert(a.end(),b.begin(),b.end());
return unique(a);
}
template<int N> struct segtree{
vector<dot> ans[N<<2],tag[N<<2];
void build(int p,int l,int r){
if(l==r) return ans[p].push_back(dot{0,4,1}),void();
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
ans[p]=addition(ans[p<<1],ans[p<<1|1]);
}
void spread(int p,const vector<dot>&k){
ans[p]=unique(multiple(ans[p],k));
tag[p]=multiple(tag[p],k);
}
void pushdown(int p){spread(p<<1,tag[p]),spread(p<<1|1,tag[p]),tag[p].clear();}
void modify(const vector<dot>&k,int L,int R,int p,int l,int r){
if(L<=l&&r<=R) return spread(p,k);
int mid=(l+r)>>1; pushdown(p);
if(L<=mid) modify(k,L,R,p<<1,l,mid);
if(mid<R) modify(k,L,R,p<<1|1,mid+1,r);
ans[p]=addition(ans[p<<1],ans[p<<1|1]);
}
LL query(int L,int R,int p,int l,int r){
if(r<L||R<l) return 0;
if(L<=l&&r<=R) return [](const vector<dot>&a)->LL{
for(dot p:a) if(p.y==3) return p.d;
return 0;
}(ans[p]);
int mid=(l+r)>>1; pushdown(p);
return query(L,R,p<<1,l,mid)+query(L,R,p<<1|1,mid+1,r);
}
};
segtree<1<<18> t;
int n;
void getpos(int*a,int*pos){
static int stk[1<<18],top;
stk[top=0]=0;
for(int i=1;i<=n;i++){
while(top&&a[stk[top]]<=a[i]) top--;
pos[i]=stk[top],stk[++top]=i;
}
}
int Q,a[2][1<<18],pos[2][1<<18];
vector<pair<int,int>> que[1<<18];
LL ans[1<<18];
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%*d%d",&n);
for(int i=1;i<=n;i++) scanf("%d",a[0]+i);
for(int i=1;i<=n;i++) scanf("%d",a[1]+i);
scanf("%d",&Q);
for(int i=1,l,r;i<=Q;i++) scanf("%d%d",&l,&r),que[r].emplace_back(l,i);
t.build(1,1,n);
for(int k:{0,1}) getpos(a[k],pos[k]);
for(int r=1;r<=n;r++){
t.modify(vector<dot>{
dot{4,0,(LL)a[0][r]},
dot{1,1,1ull},
dot{1,2,(LL)a[0][r]},
dot{3,3,1ull},
dot{4,4,1ull}
},pos[0][r]+1,r,1,1,n);
t.modify(vector<dot>{
dot{0,0,1ull},
dot{4,1,(LL)a[1][r]},
dot{0,2,(LL)a[1][r]},
dot{3,3,1ull},
dot{4,4,1ull}
},pos[1][r]+1,r,1,1,n);
t.modify(vector<dot>{
dot{0,0,1ull},
dot{1,1,1ull},
dot{2,2,1ull},
dot{2,3,1ull},
dot{3,3,1ull},
dot{4,4,1ull}
},1,r,1,1,n);
for(auto q:que[r]) ans[q.second]=t.query(q.first,r,1,1,n);
}
for(int p=1;p<=3;p++){
debug("ans[%d]:",p);
}
for(int i=1;i<=Q;i++) printf("%llu\n",ans[i]);
return 0;
}
一维
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
const LL none=1e18;
struct Ans{LL sa,sh,len;};
struct Tag{LL cover,fa,fl;};
Ans operator+(Ans a,Ans b){
return {a.sa+b.sa,a.sh+b.sh,a.len+b.len};
}
Tag operator*(Tag a,Tag b){
return {
b.cover==none?a.cover:b.cover,
a.fa+(a.cover==none)*b.fa,
a.fl+b.fl+(a.cover!=none)*b.fa*a.cover
};
}
Ans operator*(Ans a,Tag b){
return {
b.cover==none?a.sa:b.cover*a.len,
a.sh+b.fa*a.sa+b.fl*a.len,
a.len
};
}
template<int N> struct segtree{
Ans ans[N<<2]; Tag tag[N<<2];
segtree(){memset(ans,0,sizeof ans);}
void build(int p,int l,int r){
tag[p]={none,0ll,0ll};
if(l==r) return ans[p].len=1,void();
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
ans[p]=ans[p<<1]+ans[p<<1|1];
}
void spread(int p,Tag k){
ans[p]=ans[p]*k;
tag[p]=tag[p]*k;
}
void pushdown(int p){spread(p<<1,tag[p]),spread(p<<1|1,tag[p]),tag[p]={none,0ll,0ll};}
void modify(Tag k,int L,int R,int p,int l,int r){
if(L<=l&&r<=R) return spread(p,k);
int mid=(l+r)>>1; pushdown(p);
if(L<=mid) modify(k,L,R,p<<1,l,mid);
if(mid<R) modify(k,L,R,p<<1|1,mid+1,r);
ans[p]=ans[p<<1]+ans[p<<1|1];
}
LL query(int L,int R,int p,int l,int r){
if(r<L||R<l) return 0;
if(L<=l&&r<=R) return ans[p].sh;
int mid=(l+r)>>1; pushdown(p);
return query(L,R,p<<1,l,mid)+query(L,R,p<<1|1,mid+1,r);
}
};
int n,Q,a[1<<17],Lpos[1<<17];
LL ans[1<<17];
vector<pair<int,int>> que[1<<17];
segtree<1<<17> t;
void getLpos(){
static int stk[1<<17],top;
stk[top=0]=0;
for(int i=1;i<=n;i++){
while(top&&a[stk[top]]<=a[i]) top--;
Lpos[i]=stk[top],stk[++top]=i;
debug("Lpos[%d]=%d\n",i,Lpos[i]);
}
}
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=-a[i];
for(int i=1,l,r;i<=Q;i++) scanf("%d%d",&l,&r),que[r].emplace_back(l,i);
getLpos(),t.build(1,1,n);
for(int i=1;i<=n;i++){
t.modify({a[i],0ll,0ll},Lpos[i]+1,i,1,1,n);
t.modify({none,1ll,0ll},1,i,1,1,n);
for(auto q:que[i]) ans[q.second]=t.query(q.first,i,1,1,n);
}
for(int i=1;i<=Q;i++) printf("%lld\n",-ans[i]);
return 0;
}
本题
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef unsigned long long LL;
struct Tag{LL cx,cy,fxy,fx,fy,fl;};
struct Ans{LL sx,sy,sxy,sh,len;};
Ans operator+(Ans a,Ans b){
return {a.sx+b.sx,a.sy+b.sy,a.sxy+b.sxy,a.sh+b.sh,a.len+b.len};
}
Ans operator*(Ans a,Tag t){
a.sh+=a.sx*t.fx+a.sy*t.fy+a.sxy*t.fxy+a.len*t.fl;
if(t.cx&&t.cy) a.sxy=t.cx*t.cy*a.len;
else if(t.cx) a.sxy=t.cx*a.sy;
else if(t.cy) a.sxy=a.sx*t.cy;
if(t.cx) a.sx=t.cx*a.len;
if(t.cy) a.sy=t.cy*a.len;
return a;
}
Tag operator*(Tag a,Tag b){
if(a.cx) b.fl+=b.fx*a.cx,b.fx=0;
if(a.cy) b.fl+=b.fy*a.cy,b.fy=0;
if(a.cx&&a.cy) b.fl+=b.fxy*a.cx*a.cy,b.fxy=0;
else if(a.cx) b.fy+=b.fxy*a.cx,b.fxy=0;
else if(a.cy) b.fx+=b.fxy*a.cy,b.fxy=0;
b.fxy+=a.fxy,b.fx+=a.fx,b.fy+=a.fy,b.fl+=a.fl;
if(!b.cx) b.cx=a.cx; if(!b.cy) b.cy=a.cy;
return b;
}
template<int N> struct segtree{
Ans ans[N<<2]; Tag tag[N<<2];
void build(int p,int l,int r){
if(l==r) return ans[p].len=1,void();
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
ans[p]=ans[p<<1]+ans[p<<1|1];
}
void spread(int p,Tag k){
ans[p]=ans[p]*k;
tag[p]=tag[p]*k;
}
void pushdown(int p){spread(p<<1,tag[p]),spread(p<<1|1,tag[p]),tag[p]={0,0,0,0,0,0};}
void modify(Tag k,int L,int R,int p,int l,int r){
if(L<=l&&r<=R) return spread(p,k);
int mid=(l+r)>>1; pushdown(p);
if(L<=mid) modify(k,L,R,p<<1,l,mid);
if(mid<R) modify(k,L,R,p<<1|1,mid+1,r);
ans[p]=ans[p<<1]+ans[p<<1|1];
}
LL query(int L,int R,int p,int l,int r){
if(r<L||R<l) return 0;
if(L<=l&&r<=R) return ans[p].sh;
int mid=(l+r)>>1; pushdown(p);
return query(L,R,p<<1,l,mid)+query(L,R,p<<1|1,mid+1,r);
}
};
segtree<1<<18> t;
int n;
void getpos(int*a,int*pos){
static int stk[1<<18],top;
stk[top=0]=0;
for(int i=1;i<=n;i++){
while(top&&a[stk[top]]<=a[i]) top--;
pos[i]=stk[top],stk[++top]=i;
}
}
int Q,a[2][1<<18],pos[2][1<<18];
vector<pair<int,int>> que[1<<18];
LL ans[1<<18];
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%*d%d",&n);
for(int i=1;i<=n;i++) scanf("%d",a[0]+i);
for(int i=1;i<=n;i++) scanf("%d",a[1]+i);
scanf("%d",&Q);
for(int i=1,l,r;i<=Q;i++) scanf("%d%d",&l,&r),que[r].emplace_back(l,i);
t.build(1,1,n);
for(int k:{0,1}) getpos(a[k],pos[k]);
for(int r=1;r<=n;r++){
t.modify({a[0][r],0,0,0,0},pos[0][r]+1,r,1,1,n);
t.modify({0,a[1][r],0,0,0,0},pos[1][r]+1,r,1,1,n);
t.modify({0,0,1,0,0,0},1,n,1,1,n);
for(auto q:que[r]) ans[q.second]=t.query(q.first,r,1,1,n);
}
for(int i=1;i<=Q;i++) printf("%llu\n",ans[i]);
return 0;
}