@[FXT1110011010OI](/user/518899)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
by 12345678hzx @ 2023-08-17 16:35:53
哇，这不是大佬FXT吗？
0rz
by wkz2010 @ 2023-08-17 16:41:55
又优化了一下：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, INF = 1e9 + 5;
int n, q;
int a[N];
int stk[N], lmn[N], rmn[N];
LL lsum[N], rsum[N];
int lg2[N], f[N][25];
int id[N];
struct node
{
int l, r;
int qid;
bool operator < (const node &W) const
{
if (id[l] != id[W.l]) return l < W.l;
return (id[l] & 1) ? r < W.r : r > W.r;
}
}qu[N];
LL res[N];
inline void init_ddstk()
{
a[0] = a[n + 1] = -INF;
int tt = 0;
stk[ ++ tt] = 0;
for (int i = 1; i <= n; ++ i)
{
while (tt && a[stk[tt]] >= a[i]) tt -- ;
lmn[i] = stk[tt], stk[ ++ tt] = i;
}
tt = 0;
stk[ ++ tt] = n + 1;
for (int i = n; i; -- i)
{
while (tt && a[stk[tt]] >= a[i]) tt -- ;
rmn[i] = stk[tt], stk[ ++ tt] = i;
}
for (int i = 1; i <= n; ++ i) lsum[i] = lsum[lmn[i]] + (LL)(i - lmn[i]) * a[i];
for (int i = n; i; -- i) rsum[i] = rsum[rmn[i]] + (LL)(rmn[i] - i) * a[i];
a[0] = a[n + 1] = 0;
}
inline int minn(int p, int q) {return a[p] < a[q] ? p : q;}
inline void init_st()
{
for (int i = 2; i <= n; i ++ ) lg2[i] = lg2[i - 1] + ((1 << (lg2[i - 1] + 1)) <= i ? 1 : 0);
for (int i = 1; i <= n; ++ i) f[i][0] = i;
int t = lg2[n];
for (int j = 1; j <= t; ++ j)
for (int i = 1; i <= n - (1 << j) + 1; ++ i)
f[i][j] = minn(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
inline int query_mn(int l, int r)
{
int t = lg2[r - l + 1];
return minn(f[l][t], f[r - (1 << t) + 1][t]);
}
inline void init_kuai()
{
sort(qu + 1, qu + 1 + q);
int t = sqrt(n);
for (int i = 1; i <= n; ++ i) id[i] = (i - 1) / t + 1;
}
inline LL getl(int l, int r)
{
int id = query_mn(l, r);
return rsum[l] - rsum[id] + (LL)(r - id + 1) * a[id];
}
inline LL getr(int l, int r)
{
int id = query_mn(l, r);
return lsum[r] - lsum[id] + (LL)(id - l + 1) * a[id];
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
for (int i = 1; i <= q; ++ i)
{
scanf("%d%d", &qu[i].l, &qu[i].r);
qu[i].qid = i;
}
init_ddstk(), init_st(), init_kuai();
int l = 1, r = 0;
LL sum = 0;
for (int i = 1; i <= q; ++ i)
{
while (l > qu[i].l) sum += getl( -- l, r);
while (r < qu[i].r) sum += getr(l, ++ r);
while (l < qu[i].l) sum -= getl(l ++ , r);
while (r > qu[i].r) sum -= getr(l, r -- );
res[qu[i].qid] = sum;
}
for (int i = 1; i <= q; ++ i) printf("%lld\n", res[i]);
return 0;
}
```
by FXT1110011010OI @ 2023-08-17 16:49:07
过了，莫队排序写假，结帖
by FXT1110011010OI @ 2023-08-18 15:16:20