Statement

给出一个长度为 nn 的排列 PP，以及 mm 个询问。每次询问某个区间 [l,r][l,r] 中，最长的值域连续段长度。

数据范围：n,m≤5×104n,m\le5\times10^4。

Solution

考虑莫队区间如何扩展。

维护每个元素向上延伸和向下延伸的最大距离。加入新元素 xx 时，会合并 x−1x-1 所在集合和 x+1x+1 所在集合；但是对答案有贡献的只可能是合并后集合的端点。所以可以只更新这两个元素，也方便了撤销。

时间复杂度 O(nm)O(n\sqrt m)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
const int N = 5e4 + 3, SN = 293;
int n, q, a[N], B, T, ans[N];
#define belong(x) ((x) / B)
#define lp(x) ((x)*B)
#define rp(x) (std::min((x)*B + B, n) - 1)
struct Query {
    int l, r, id;
    bool operator<(const Query& x) const { return r < x.r; }
};
std::vector<Query> que[SN];
struct Stack {
    int x, y, z, upx, downx, upy, downz, mx;
};
int main() {
    scanf("%d%d", &n, &q), B = sqrt(q + 0.5), T = belong(n - 1) + 1;
    for (int i = 0; i < n; i++) scanf("%d", a + i);
#define add(x)                                        \
    up[x] = up[x + 1] + 1, down[x] = down[x - 1] + 1, \
    up[x - down[x - 1]] = down[x + up[x + 1]] = up[x] + down[x] - 1, \
    mx = std::max(mx, up[x] + down[x] - 1)
    for (int id = 1, l, r; id <= q; id++) {
        scanf("%d%d", &l, &r), l--, r--;
        static int up[N], down[N];
        if (r - l + 1 <= B) {
            int mx = 0;
            for (int i = l; i <= r; i++) add(a[i]);
            for (int i = l; i <= r; i++) up[a[i]] = down[a[i]] = 0;
            ans[id] = mx;
        } else
            que[belong(l)].push_back({l, r, id});
    }
    for (int b = 0; b < T; b++) {
        sort(que[b].begin(), que[b].end());
        static int up[N], down[N];
        static Stack stk[N];
        int r = rp(b), top = 0, mx = 0;
        memset(up, 0, sizeof up), memset(down, 0, sizeof down);
        for (Query& u : que[b]) {
            while (r < u.r) r++, add(a[r]);
            for (int i = rp(b), x, y, z; i >= u.l; i--) {
                x = a[i], y = x - down[x - 1], z = x + up[x + 1];
                stk[++top] = {x, y, z, up[x], down[x], up[y], down[z], mx};
                add(a[i]);
            }
            ans[u.id] = mx;
            while (top) {
                static int x, y, z;
                x = stk[top].x, y = stk[top].y, z = stk[top].z;
                up[x] = stk[top].upx, down[x] = stk[top].downx;
                up[y] = stk[top].upy, down[z] = stk[top].downz;
                mx = stk[top].mx, top--;
            }
        }
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    return 0;
}