[DS记录]P3246 [HNOI2016]序列
command_block
·
·
个人记录
题意 ： 给出一个序列，每次询问一个区间的所有子区间最小值之和。
------------
设 $f[l][r]$ 为 $[l,r]$ 的最小值。
按照 $r$ 从小到大的顺序维护，考虑 $f[l][r]$ 和 $f[l][r+1]$ 有什么不同。
在右侧加入一个元素，可以用单调栈来维护最小值，配合线段树做区间修改，即可维护出 $f$ 数组。
对于一个询问，答案是 $f$ 的一个矩阵的和，如图 ：
套用线段树历史版本和即可。若可持久化可以做到在线。
更多内容可见 ： [关于线段树上的一些进阶操作](https://www.luogu.com.cn/blog/command-block/guan-yu-xian-duan-shu-shang-di-yi-suo-jin-jie-cao-zuo)
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define MaxN 100500
using namespace std;
struct Node{
ll tg,mt,u,s,ms;int len;
inline void ladd(ll _tg,ll _mt,ll _u){
ms+=_u*s+_mt*len;
mt+=tg*_u+_mt;
u+=_u;
s+=_tg*len;
tg+=_tg;
}
}a[MaxN<<2];
inline void up(int u){
a[u].s=a[u<<1].s+a[u<<1|1].s;
a[u].ms=a[u<<1].ms+a[u<<1|1].ms;
}
inline void ladd(int u){
if (a[u].u||a[u].tg||a[u].mt){
a[u<<1].ladd(a[u].tg,a[u].mt,a[u].u);
a[u<<1|1].ladd(a[u].tg,a[u].mt,a[u].u);
a[u].u=a[u].tg=a[u].mt=0;
}
}
int n;
void build(int l=1,int r=n,int u=1)
{
a[u].len=r-l+1;
if (l==r)return ;
int mid=(l+r)>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
}
int wfl,wfr,wfc;
void add(int l=1,int r=n,int u=1)
{
if (wfl<=l&&r<=wfr){
a[u].ladd(wfc,0,0);
return ;
}int mid=(l+r)>>1;ladd(u);
if (wfl<=mid)add(l,mid,u<<1);
if (mid<wfr)add(mid+1,r,u<<1|1);
up(u);
}
ll qry(int l=1,int r=n,int u=1)
{
if (wfl<=l&&r<=wfr)return a[u].ms;
int mid=(l+r)>>1;ll ret=0;ladd(u);
if (wfl<=mid)ret=qry(l,mid,u<<1);
if (mid<wfr)ret+=qry(mid+1,r,u<<1|1);
return ret;
}
struct Data{int l,p;};
vector<Data> b[MaxN];
ll ans[MaxN];
int q,x[MaxN],stk[MaxN],top;
int main()
{
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++)scanf("%d",&x[i]);
for (int i=1,l,r;i<=q;i++){
scanf("%d%d",&l,&r);
b[r].push_back((Data){l,i});
}build();
for (int i=1;i<=n;i++){
while(top&&x[stk[top]]>x[i]){
wfl=stk[top-1]+1;
wfr=stk[top];
wfc=x[i]-x[stk[top]];
add();top--;
}stk[++top]=wfl=wfr=i;
wfc=x[i];add();
a[1].ladd(0,0,1);
for (int j=0;j<b[i].size();j++){
wfl=b[i][j].l;wfr=i;
ans[b[i][j].p]=qry();
}
}
for (int i=1;i<=q;i++)
printf("%lld\n",ans[i]);
return 0;
}
```