Day \(|\Sigma|\)。
模拟赛里面的题，早上降智没调出来。题意大概就是求区间所有子区间的只出现在子区间内的数的最大值的和。
记录一个数 \(i\) 的最左出现位置 \(l_i\) 和最右出现位置 \(r_i\)，一个数只在 \([L,R]\) 中出现当且仅当 \([l_i,r_i]\subseteq [L,R]\)。
考虑扫描线，统一处理所有右端点在 \(p\) 处的询问。对每个 \(l\)，记录 \(S_l=\sum\limits_{l\le r\le p}w(l,r)\)，考虑每次 \(p\) 的移动相当于给 \(S_l\) 加上 \(w(l,p)\)。考虑 \(w(l,p)\) 相比于 \(w(l,p-1)\) 的变化（如果能快速更新 \(w(l,p)\)，\(S_l\) 相当于对历史求和），相当于求所有满足 \(r_i=p,l_i\ge l\) 的 \(i\) 的最大值于 \(w(l,p-1)\) 做比较。
这个过程相当于，先令 \(w(l,p)=w(l,p-1)\)，然后我们每次插入 \(r_i=p\) 的所有 \(i\)，插入一对 \((l_i,p)\) 时相当于对 \(w(1,p),w(2,p)\cdots,w(l_i,p)\) 前缀对 \(i\) 取 \(\max\)，直接吉司机线段树即可。
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
//#define FILE
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pi;
bool Med;
const int N = 3e5 + 300;
const int inf = N + 1;
int n, q;
int a[N], lp[N], rp[N], ans[N];
vector<pi> g[N], qr[N];
struct seg {
int mn, cmn, ct, cct, sum, hsum;
seg () { }
seg (int _a, int _b, int _c, int _d, int _e, int _f) :
mn(_a), cmn(_b), ct(_c), sum(_d), hsum(_e) { }
seg operator + (const seg &rh) const {
seg res;
if (mn == rh.mn) res.mn = mn, res.cmn = min(cmn, rh.cmn), res.ct = ct + rh.ct, res.cct = cmn > rh.cmn ? rh.cct : cct;
else if (mn < rh.mn) {
res.mn = mn, res.ct = ct;
if (cmn == rh.mn) res.cmn = cmn, res.cct = cct + rh.ct;
else if (cmn < rh.mn) res.cmn = cmn, res.cct = cct;
else res.cmn = rh.mn, res.cct = rh.ct;
} else {
res.mn = rh.mn, res.ct = rh.ct;
if (mn == rh.cmn) res.cmn = mn, res.cct = ct + rh.cct;
else if (mn < rh.cmn) res.cmn = mn, res.cct = ct;
else res.cmn = rh.cmn, res.cct = rh.cct;
}
res.sum = sum + rh.sum, res.hsum = hsum + rh.hsum;
return res;
}
} tr[N << 2];
int ti[N << 2], lz[N << 2], hlz[N << 2];
#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
void build(int l, int r, int x) {
tr[x] = seg(0, inf, r - l + 1, 0, 0, 0);
if (l == r) return;
build(l, mid, ls), build(mid + 1, r, rs);
}
void phis(int x, int c) { ti[x] += c, hlz[x] += c * lz[x], tr[x].hsum += c * tr[x].sum; }
void psum(int x, int c) { lz[x] += c, tr[x].mn += c, tr[x].sum += c * tr[x].ct; }
void phsum(int x, int c) { hlz[x] += c, tr[x].hsum += c * tr[x].ct; }
void pdn(int x) {
int mn = min(tr[ls].mn, tr[rs].mn);
int fl = (tr[ls].mn == mn), fr = (tr[rs].mn == mn);
if (ti[x]) phis(ls, ti[x]), phis(rs, ti[x]), ti[x] = 0;
if (hlz[x]) {
if (fl) phsum(ls, hlz[x]);
if (fr) phsum(rs, hlz[x]);
hlz[x] = 0;
}
if (lz[x]) {
if (fl) psum(ls, lz[x]);
if (fr) psum(rs, lz[x]);
lz[x] = 0;
}
}
void upd(int l, int r, int s, int t, int c, int x) {
if (l != r) pdn(x);
if (tr[x].mn > c) return;
if (s <= l && r <= t && tr[x].mn <= c && tr[x].cmn > c) return psum(x, c - tr[x].mn), void();
if (s <= mid) upd(l, mid, s, t, c, ls);
if (t > mid) upd(mid + 1, r, s, t, c, rs);
tr[x] = tr[ls] + tr[rs];
}
int qry(int l, int r, int s, int t, int x) {
if (l != r) pdn(x);
if (s <= l && r <= t) return tr[x].hsum;
int res = 0;
if (s <= mid) res += qry(l, mid, s, t, ls);
if (t > mid) res += qry(mid + 1, r, s, t, rs);
return res;
}
int tp[N];
void solve() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i], rp[i] = n + 1;
for (int i = 1; i <= n; i++) rp[a[i]] = i;
for (int i = n; i; i--) lp[a[i]] = i;
for (int i = 1; i <= n; i++) g[rp[i]].pb(mp(lp[i], i));
for (int i = 1, l, r; i <= q; i++)
cin >> l >> r, qr[r].pb(mp(l, i));
build(1, n, 1);
for (int i = 1; i <= n; i++) {
for (pi p : g[i]) upd(1, n, 1, p.fi, p.se, 1);
phis(1, 1);
for (pi p : qr[i]) ans[p.se] = qry(1, n, p.fi, i, 1);
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
bool Mbe;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Med - &Mbe) / 1024 / 1024 << " MB\n";
#ifdef FILE
freopen("ex_seq3.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif
int _ = 1;
// cin >> T;
while (_--) solve();
cerr << 1. * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}