富阳做网站方式,空间租用 网站开发,做seo网站推广价格,平时发现同学做的ppt找的材料图片不错_不知道从哪些网站可以获得题意#xff1a;给定序列 aia_iai#xff0c;qqq 次询问 [l,r][l,r][l,r] 所有子区间最小值之和。 n,q≤105n,q\leq 10^5n,q≤105
这种题一眼看上去是离线线段树#xff0c;但这题每移动一位要维护区间取 min\minmin#xff0c;历史值之和#xff0c;非常不可做。
所…题意给定序列 aia_iaiqqq 次询问 [l,r][l,r][l,r] 所有子区间最小值之和。
n,q≤105n,q\leq 10^5n,q≤105
这种题一眼看上去是离线线段树但这题每移动一位要维护区间取 min\minmin历史值之和非常不可做。
所以考虑莫队。
考虑移动一位产生的贡献。以向右扩展一位为例我们要求的是这个东西
∑ilrrmq(i,r1)\sum_{il}^r\operatorname{rmq}(i,r1)il∑rrmq(i,r1)
这显然是个单调栈的形式。维护单调栈内的所有贡献但十分精神污染并且单调栈既不能删除也不能撤销 智商分割线 考虑我们要求的到底是什么。设 preipre_iprei 为 iii 前面最后一个比它小的数的位置那么这个数产生的贡献是 ai(i−prei)a_i(i-pre_i)ai(i−prei)。
而这么下去只有单调栈中的第一个也就是区间最小值产生的贡献是不完整的。维护一个以 preipre_iprei 为 fafafa 数组的树的树上前缀和然后 ST 表查到最小值把多余的部分减掉即可。
复杂度 O(nlognmlogmnm)\Omicron(n\log nm\log mn\sqrt m)O(nlognmlogmnm)
#include iostream
#include cstdio
#include cstring
#include cctype
#include cmath
#include algorithm
#define MAXN 100005
using namespace std;
typedef long long ll;
inline int read()
{int ans0,f1;char cgetchar();while (!isdigit(c)) (c-)(f-1),cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return f*ans;
}
int a[MAXN],pre[MAXN],suf[MAXN],stk[MAXN],tp;
int st[MAXN][20],LOG[MAXN];
ll psum[MAXN],ssum[MAXN];
inline int Min(const int x,const int y){return a[x]a[y]? x:y;}
inline int rmq(int l,int r)
{int tLOG[r-l1];return Min(st[l][t],st[r-(1t)1][t]);
}
inline ll calcL(int l,int r)
{int posrmq(l-1,r);return ssum[l-1]-ssum[suf[pos]]-(ll)(suf[pos]-r-1)*a[pos];
}
inline ll calcR(int l,int r)
{int posrmq(l,r1);return psum[r1]-psum[pre[pos]]-(ll)(l-pre[pos]-1)*a[pos];
}
int B;
struct query{int l,r,pos;}q[MAXN];
inline bool operator (const query a,const query b){return a.l/Bb.l/B? a.rb.r:a.lb.l;}
ll res[MAXN];
int main()
{int n,m;nread(),mread();LOG[0]-1;for (int i1;in;i) LOG[i]LOG[i1]1;for (int i1;in;i) a[st[i][0]i]read();for (int j1;j20;j)for (int i1;i(1(j-1))n;i)st[i][j]Min(st[i][j-1],st[i(1(j-1))][j-1]);for (int i1;in;i){while (tpa[i]a[stk[tp]]) --tp;pre[i]stk[tp],psum[i]psum[stk[tp]](ll)(i-stk[tp])*a[i],stk[tp]i;}tp0;stk[0]n1;for (int in;i1;i--){while (tpa[i]a[stk[tp]]) --tp;suf[i]stk[tp],ssum[i]ssum[stk[tp]](ll)(stk[tp]-i)*a[i],stk[tp]i;}Bsqrt(n);for (int i1;im;i) q[i].lread(),q[i].rread(),q[i].posi;sort(q1,qm1);int l1,r0;ll sum0;for (int i1;im;i){while (rq[i].r) sumcalcR(l,r);while (lq[i].l) sumcalcL(l--,r);while (rq[i].r) sum-calcR(l,--r);while (lq[i].l) sum-calcL(l,r);res[q[i].pos]sum;}for (int i1;im;i) printf(%lld\n,res[i]);return 0;
}
