【洛谷P5654】基础函数练习题
线段树
题目大意：
给定一个排列 $p$ 和一个数列 $w$。
定义函数 $f(l,r)$ 为：
其中 $m$ 为 $p$ 的区间 $[l,r]$ 中的最大值的下标。
每次询问给出 $l,r$，求 $f(l,r)$ 的值。
题解：
考虑对原序列，找到其 $m$ 的位置，然后分割成左右两个子序列，对子序列继续执行这样的分割操作。最后我们会得到一棵树。
考虑对于一个询问 $[l,r]$，我们找到其 $m$ 的位置，则该询问在这个结点分为 $f(l,m-1)$ 和 $f(m+1,r)$。
这个类似于线段树上查询的过程，但是本题中这样建出来的树的层数是 $O(n)$ 的，复杂度不对。
本题的询问都是不带修改的，因此我们还有一个思想，对于一个表示 $[l,r]$ 的结点，其分隔点为 $m$，我们想办法计算 $f(i,m-1),i\in[l,m-1]$ 和 $f(m+1,i),i\in[m+1,r]$，然后对于一个询问，我们只需得到左、右两个信息就可以计算答案了。
这个可以逐层向上更新，用线段树维护答案即可。
对于区间 $[l,r]$（假设为一个结点的左儿子，即其父亲的分割点为 $r+1$。右儿子同理），其线段树上的 $l\sim m-1$ 位置的答案为右端点为 $m-1$ 时的答案，而 $m+1\sim r$ 位置，对应的右端点为 $r+1$。
这个时候，我们把 $l\sim m-1$ 的值，同时和 $f(m+1,r)$ 取 $\max$，然后加上 $w_m$ 的值就完成更新。
左右都同理可得。
用线段树实现区间对一个数取 $\max$，区间加，单点查询即可。
至于求 $[l,r]$ 的 $m$ 的位置，用 ST 表维护区间最值即可。
时间复杂度 $O((n+q)\log n)$。
Code：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define lg2(x)(31-__builtin_clz(x))
typedef long long LL;
const int N=5e5+6;
const LL inf=1e18;
int n,m,a[N],p[N],st[19][N],pos[N];
inline int ask(int l,int r){
const int lg=lg2(r-l+1);
return max(st[lg][l],st[lg][r-(1<<lg)+1]);
}
struct que{
int l,r,id;
};
vector<que>vec[N];
LL ans[N];
struct sgt{
LL mx[N<<2],add[N<<2];
inline void pushdown(int o){
const int ls=o<<1,rs=o<<1|1;
if(mx[o]!=-inf){
LL&x=mx[o];
mx[ls]=max(mx[ls],x-add[ls]);
mx[rs]=max(mx[rs],x-add[rs]);
x=-inf;
}
add[ls]+=add[o],add[rs]+=add[o],add[o]=0;
}
void init(int l,int r,int o){
mx[o]=-inf*(l<r);
if(l<r){
const int mid=l+r>>1;
init(l,mid,o<<1),init(mid+1,r,o<<1|1);
}
}
void Add(int l,int r,int o,const int&L,const int&R,const LL&dlt){
if(L<=l&&r<=R)add[o]+=dlt;else{
pushdown(o);
const int mid=l+r>>1;
if(L<=mid)Add(l,mid,o<<1,L,R,dlt);
if(mid<R)Add(mid+1,r,o<<1|1,L,R,dlt);
}
}
void Max(int l,int r,int o,const int&L,const int&R,const LL&tag){
if(L<=l&&r<=R)mx[o]=max(mx[o],tag-add[o]);else{
pushdown(o);
const int mid=l+r>>1;
if(L<=mid)Max(l,mid,o<<1,L,R,tag);
if(mid<R)Max(mid+1,r,o<<1|1,L,R,tag);
}
}
LL ask(int l,int r,int o,const int&pos){
if(l==r)return mx[o]+add[o];
pushdown(o);
const int mid=l+r>>1;
if(pos<=mid)return ask(l,mid,o<<1,pos);
return ask(mid+1,r,o<<1|1,pos);
}
}A,B;
void build(int l,int r){
if(l>r)return;
const int mid=pos[ask(l,r)];
build(l,mid-1),build(mid+1,r);
for(int i=0;i<vec[mid].size();++i){
int l=vec[mid][i].l,r=vec[mid][i].r,id=vec[mid][i].id;
ans[id]=max(A.ask(1,n,1,l),B.ask(1,n,1,r))+a[mid];
}
LL x=A.ask(1,n,1,mid+1);
A.Max(1,n,1,l,mid,x),A.Add(1,n,1,l,mid,a[mid]);
x=B.ask(1,n,1,mid-1);
B.Max(1,n,1,mid,r,x),B.Add(1,n,1,mid,r,a[mid]);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>p[i],st[0][i]=p[i],pos[p[i]]=i;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<19;++i)
for(int j=1;j+(1<<i-1)<=n;++j)
st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]);
for(int i=1;i<=m;++i){
int l,r;
cin>>l>>r;
vec[pos[ask(l,r)]].push_back((que){l,r,i});
}
A.init(1,n,1),B.init(1,n,1);
build(1,n);
for(int i=1;i<=m;++i)
cout<<ans[i]<<'\n';
return 0;
}