P3246 [HNOI2016] 序列

鱼跃于渊 · 2024-08-10 10:29:28 · 题解

这道题实际上是 P8868 [NOIP2022] 比赛的弱化版。

做法

首先我们离线所有的询问，对于右端点 r 进行扫描线，我们设 X_{l,r}=\min_{i=l}^{r}a_i,S_{l,r}=\sum_{i=l}^{r}X_{l,i}，则可以得到区间 [l,r] 的答案为 \sum_{i=l}^{r}S_{l,i}，实际上就是这段区间的历史版本和。
考虑单调栈维护，当 i 入栈时先排除掉比 a_i 大的数，若排除完后栈顶为 j，则 [j,i] 这段区间的最小值就是 a_i，可以在线段树上更新。
不过要注意，如果维护区间最值，时间复杂度是 O(n \log^2 n) 的。事实上我们还可以维护区间加减，使时间复杂度降至 O(n\log n)，具体可以看代码理解。

现在步入正题，来讲一下如何通过双半群模型来构造出我们需要的线段树，即一棵支持区间加减区间版本和的线段树。
如果您不知道双半群模型是什么，可以阅读这篇和这篇文章，然后再来看本文的构造方法。
我们首先考虑我们需要维护的信息 D，显然区间和与区间版本和是必需的，为方便起见，我们把区间长度也加入其中，这样信息 D 就可以表示成 (sa,sum,len) 的形式，其中 sa 是区间和，sum 是区间版本和。
接下来我们考虑我们需要执行的操作。我们把更新历史版本和也看作是一个操作，那么总共就有两个操作，另一个是区间加减。
再考虑这两个操作会对信息产生怎样的影响：

令函数 f 代表区间加减操作，则有 f((sa,sum,len))=(sa+len\times x,sum,len)，其中 x 是我们要加减的数。
令函数 g 代表区间更新操作，则有 g((sa,sum,len))=(sa,sum+y \times sa,len)，其中 y 是更新次数。

再考虑这两个操作结合起来会产生怎样的影响，也就是求函数 f 和 g 的复合，可以得到 g(f((sa,sum,len)))=(sa+len\times x,sum+y\times sa+len\times x \times y)。
事实上可以发现，无论我们以何等顺序、何等次数执行这两个操作，最终的结果都可以表示成上面的那个形式。
也就是说，如果我们令 F 为若干个 f 和 g 的复合，则 F((sa,sum,len))=(sa+len\times taga,sum+upd\times sa+len\times cnta)。
我们可以记一个三元组 (taga,upd,cnta) 来表示 F，事实上我们可以惊讶的发现，这个三元组其实就是我们要维护的标记 M 的形式。
这就是双半群模型的强悍之处，只要我们知道我们要维护的信息 D，以及我们的操作 F，就可以推出我们需要维护的标记 M。其实它还不止于此，接下来我们还可以推出标记与信息的三个转移。
如果您阅读了上面给出的两篇文章，您应该知道有三个核心式子：

D + D \rightarrow D
M * M \rightarrow M
D \times M \rightarrow D

这实际上是我们构造出来的信息 D 和 M 所必须满足的性质，我们可以据此推出它们之间的具体转移。
首先考虑 D + D \rightarrow D，这个还是很简单的，即 (sa,sum,len)+(sa',sum',len')=(sa+sa',sum+sum',len+len')，具体到代码就是

node operator +(const node &x,const node &y){
    node z={0,0,0};
    z.a=x.a+y.a;
    z.sum=x.sum+y.sum;
    z.len=x.len+y.len;
    return z;
}

其次考虑 D \times M \rightarrow D，这个也简单，上文已经得出来 (sa,sum,len)\times (taga,upd,cnta)=(sa+len\times taga,sum+upd\times sa+len\times cnta)，具体到代码就是

node operator *(const node &x,const tag &y){
    node z={0,0,0};
    z.sum=x.sum+x.a*y.upd+x.len*y.cnta;
    z.a=x.a+x.len*y.taga;
    z.len=x.len;
    return z;
}

其次考虑 M * M \rightarrow M，这个是最复杂的，不过我们有 D\times (M*M) = (D\times M)\times M。也就是说我们可以通过 (D\times M)\times M 所得到的系数，得到 M*M 的结果。
过程留给读者自行推导，最终可以得到 ((sa,sum,len) \times (taga,upd,cnta))\times (taga',upd',cnta')=(sa+len\times (taga+taga'),sum+(upd+upd')\times sa+len\times (cnta+taga\times upd'+cnta'))。
也就是说 (taga,upd,cnta)*(taga',upd',cnta')=(taga+taga',upd+upd',cnta+taga*upd'+cnta')，具体到代码就是

tag operator *(const tag &x,const tag &y){
    tag z={0,0,0};
    z.cnta=x.cnta+x.taga*y.upd+y.cnta;
    z.upd=x.upd+y.upd;
    z.taga=x.taga+y.taga;
    return z;
}

于是这棵线段树就这么被构造出来了。
我们最终可以得到构造双半群模型的以下流程：

构造可行的信息 D，检验是否满足 D+D\rightarrow D，并得出转移形式。
通过计算各个操作对信息 D 的影响，总结出标记 M，检验是否满足 D\times M \rightarrow D，并得出转移形式。
通过计算验证标记 M 是否满足 M*M\rightarrow M，并得出转移形式。

如果出现不满足的情况，从 1 重新开始。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned int
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
const int N=1e5+5;
struct tag{
 int taga,upd,cnta;
}M[N<<2];
struct node{
 int a,sum,len;
}D[N<<2];
tag operator *(const tag &x,const tag &y){
 tag z={0,0,0};
 z.cnta=x.cnta+x.taga*y.upd+y.cnta;
 z.upd=x.upd+y.upd;
 z.taga=x.taga+y.taga;
 return z;
}
node operator +(const node &x,const node &y){
 node z={0,0,0};
 z.a=x.a+y.a;
 z.sum=x.sum+y.sum;
 z.len=x.len+y.len;
 return z;
}
node operator *(const node &x,const tag &y){
 node z={0,0,0};
 z.sum=x.sum+x.a*y.upd+x.len*y.cnta;
 z.a=x.a+x.len*y.taga;
 z.len=x.len;
 return z;
}
struct ques{
 int p,i;
};
int n,m,a[N],ans[N];
int top,st[N];
vector <ques> e[N];
void push_up(int i){
 D[i]=D[ls(i)]+D[rs(i)];
}
void modify(int i,tag j){
 D[i]=D[i]*j;
 M[i]=M[i]*j;
}
void push_down(int i){
 modify(ls(i),M[i]);
 modify(rs(i),M[i]);
 M[i]={0,0,0};
}
void update(int nl,int nr,int l,int r,int i,int k){
 if(nl<=l&&r<=nr) return modify(i,{k,0,0});
 push_down(i);
 int mid=(l+r)>>1;
 if(nl<=mid) update(nl,nr,l,mid,ls(i),k);
 if(mid<nr) update(nl,nr,mid+1,r,rs(i),k);
 push_up(i);
}
int query(int nl,int nr,int l,int r,int i){
 if(nl<=l&&r<=nr) return D[i].sum;
 push_down(i);
 int mid=(l+r)>>1,res=0;
 if(nl<=mid) res+=query(nl,nr,l,mid,ls(i));
 if(mid<nr) res+=query(nl,nr,mid+1,r,rs(i));
 return res;
}
void build(int i,int l,int r){
 D[i]={0,0,r-l+1};
 M[i]={0,0,0};
 if(l==r) return;
 int mid=(l+r)>>1;
 build(ls(i),l,mid);
 build(rs(i),mid+1,r);
}
signed main(){
 ios::sync_with_stdio(0);
 cin.tie(0); cout.tie(0);
 cin>>n>>m;
 for(int i=1;i<=n;i++) cin>>a[i];
 for(int i=1,l,r;i<=m;i++){
     cin>>l>>r;
     e[r].push_back({l,i});
 }
 build(1,1,n);
 for(int i=1;i<=n;i++){
     while(top&&a[st[top]]>a[i]){
         update(st[top-1]+1,st[top],1,n,1,-a[st[top]]);
         top--;
     }
     update(st[top]+1,i,1,n,1,a[i]);
     st[++top]=i;
     modify(1,{0,1,0});
     for(auto x:e[i]) ans[x.i]=query(x.p,i,1,n,1);
 }
 for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
 return 0;
}