题意
给定一个序列，静态区间查询区间的长度为 \(1 \to 10\) 的极长值域连续段个数。
Sol
考虑离线下来跑扫描线。枚举右端点，维护每个左端点的答案。
不难想到，\(i\) 对 \(lst[i]\) 是没有贡献的，考虑右端点为 \(i - 1\)，若此时的 \(l \le lst[i]\)。\(i\) 不作贡献。
所以我们把值域上 \([s[i] - 10, s[i] + 10]\) 这 \(20\) 个点单独挑出来，从右到左排序依次计算。
考虑当前 \(i\) 对于 \(l\) 的贡献。
-
\(i\) 为某个连续值域段的左端点
-
\(i\) 为某个连续值域段的右端点
-
\(i\) 连接两个连续值域段
我们需要一个区间修改，单点查询的数据结构。这边考虑使用树状数组。
设当前枚举到的 \(l\)，不难发现贡献区间即为，\(idx[l + 1] \to idx[l]\)。
对于三种情况分别分类讨论即可。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <vector>
#include <bitset>
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
const int N = 1e6 + 25;
array <int, N> s;
struct BIT {
/* int edge[N]; */
array <int, N> edge;
int lowbit(int x) {
return x & -x;
}
void modify(int x, int y) {
while (x) {
edge[x] += y;
x -= lowbit(x);
}
return;
}
int query(int x, int n) {
int ans = 0;
while (x <= n) {
ans += edge[x];
x += lowbit(x);
}
return ans;
}
BIT() : edge() {}
} T[11];
/* const auto func = [](pii a, pii b) { */
/* return a.se < b.se; */
/* }; */
/* array <pii, N> prl; */
array <vector <pii>, N> idx;
array <int, N> lst;
bitset <N> vis;
array <array <int, 10>, N> ans;
int main() {
int n = read(), m = read();
for (int i = 1; i <= n; i++)
s[i] = read();
for (int i = 1; i <= m; i++) {
int l = read(), r = read();
idx[r].push_back(make_pair(l, i));
/* prl[i].fi = l, prl[i].se = r; */
}
/* sort(prl.begin() + 1, prl.begin() + 1 + n, func); */
for (int i = 1; i <= n; i++) {
vector <int> tp;
for (int j = max(1, s[i] - 11); j <= s[i] + 11; j++) {
if (!lst[j] || lst[j] <= lst[s[i]]) continue;
tp.push_back(lst[j]);
}
tp.push_back(i);
tp.push_back(lst[s[i]]);
sort(tp.begin(), tp.end(), greater <int>());
/* if (i == 2) { */
/* for (auto x : tp) */
/* write(x), putchar(32); */
/* puts("$$"); */
/* } */
vis[s[i]] = 1;
/* vis[lst[s[i]]] = 1; */
int Lp = s[i], Rp = s[i];
/* puts("["); */
for (int j = 0; j < (int)tp.size() - 1; j++) {
vis[s[tp[j]]] = 1;
/* if (i == 2) */
/* write(s[tp[j]]), puts(""); */
/* write(j), puts(""); */
while (vis[Lp - 1]) Lp--;
while (vis[Rp + 1]) Rp++;
/* if (i == 2) */
/* write(s[i] - Lp), putchar(32); */
/* write(Rp - s[i]), puts(""); */
if (1 <= s[i] - Lp && s[i] - Lp <= 10)
T[s[i] - Lp].modify(tp[j], -1), T[s[i] - Lp].modify(tp[j + 1], 1);
if (1 <= Rp - s[i] && Rp - s[i] <= 10)
T[Rp - s[i]].modify(tp[j], -1), T[Rp - s[i]].modify(tp[j + 1], 1);
if (1 <= Rp - Lp + 1 && Rp - Lp + 1 <= 10)
T[Rp - Lp + 1].modify(tp[j], 1), T[Rp - Lp + 1].modify(tp[j + 1], -1);
}
/* puts("]"); */
/* idx[prl[i].se].push_back() */
for (int j = max(1, s[i] - 11); j <= s[i] + 11; j++)
vis[j] = 0;
for (auto j : idx[i])
for (int k = 1; k <= 10; k++)
ans[j.se][k] = T[k].query(j.fi, n);
lst[s[i]] = i;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= 10; j++)
write(ans[i][j] % 10);
puts("");
}
return 0;
}