Luogu 4747 - [CERC2017]Intrinsic Interval

非常有意思的一道线段树题,应该想出来的并不难?

考虑离线,那么我们现在的问题便是在 $\log n$ 的时间内判断确定一个端点的情况下,其可能的区间的集合。

对于判定一个区间是否是题目所要求的“连续区间”,不难想到如此方法:

但是对于该题,在右端点固定的情况下,其区间 $\max$ 和 $\min$ 会随时变化的,难以维护以及查询。

在考虑“连续“区间的其他性质,不难发现其数字连续对(即在值域上连续)的个数一定是 $r - l$ 个,且对于一个区间 $[l, r]$ ,若其数字连续对的个数为 $r - l$ ,其一定是连续区间。

证明:其数字连续对个数为 $r - l$ ,则只有两个数只有一个数字连续对。则对于所有数字一定是连续的,反之不成立。

那么如何判定?令 $t_j = j$,每加入一个右端点 $a_i$ ,若 $a_i - 1,a_i + 1$ 已经在之前出现过,则在 $1 \sim p_{a_i - 1}$ 区间加一,$a_i + 1$ 同理,表明任意一个左端点取 $1 \sim p_{a_i - 1}$ 的点,都将多碰到一个数字连续对,判定条件即为:$t_j = i$ 。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>

#define MAXN 100005
#define ls x << 1
#define rs x << 1 | 1

using namespace std;

typedef pair<int, int> pa;

int n, m;
int a[MAXN], p[MAXN];
vector<pa> q[MAXN];
priority_queue<pa> s;
pa ans[MAXN];

struct node {
int p, v;
node(int p = 0, int v = 0):p(p), v(v) {}

bool operator < (const node b) const {
return v < b.v || (v == b.v && p < b.p);
}
}v;

struct segment {
int l, r, t;
node v;
}t[MAXN << 2];

int read() {
char c = getchar();
int x = 0, s = 1;
while (!isdigit(c)) {
s = c == '-' ? -1 : 1;
c = getchar();
}
while (isdigit(c)) {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x * s;
}

void pushdown(int x) {
if (t[x].t) {
t[ls].t += t[x].t;
t[ls].v.v += t[x].t;
t[rs].t += t[x].t;
t[rs].v.v += t[x].t;
t[x].t = 0;
}
}

void pushup(int x) {
t[x].v = max(t[ls].v, t[rs].v);
}

void build(int l = 1, int r = n, int x = 1) {
t[x].l = l;
t[x].r = r;
if (l == r) {
t[x].v = node(l, l);
return ;
}
int mid = (l + r) >> 1;
build(l, mid, ls);
build(mid + 1, r, rs);
pushup(x);
}

void modify(int l, int r, int v, int x = 1) {
if (l <= t[x].l && t[x].r <= r) {
t[x].t += v;
t[x].v.v += v;
return ;
}
pushdown(x);
int mid = (t[x].l + t[x].r) >> 1;
if (l <= mid)
modify(l, r, v, ls);
if (r > mid)
modify(l, r, v, rs);
pushup(x);
}

node query(int l, int r, int x = 1) {
if (l <= t[x].l && t[x].r <= r)
return t[x].v;
int mid = (t[x].l + t[x].r) >> 1;
node res;
pushdown(x);
if (l <= mid)
res = max(res, query(l, r, ls));
if (r > mid)
res = max(res, query(l, r, rs));
pushup(x);
return res;
}

void solve() {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < (int)q[i].size(); ++j)
s.push(q[i][j]);
if (a[i] - 1 >= 1 && p[a[i] - 1] <= i)
modify(1, p[a[i] - 1], 1);
if (a[i] + 1 <= n && p[a[i] + 1] <= i)
modify(1, p[a[i] + 1], 1);
while (!s.empty()) {
pa u = s.top();
node v = query(1, u.first);
if (v.v == i)
ans[u.second] = make_pair(v.p, i);
else
break;
s.pop();
}
}
}

int main() {
n = read();
for (int i = 1; i <= n; ++i)
p[a[i] = read()] = i;
m = read();
for (int i = 1; i <= m; ++i) {
int l = read(), r = read();
q[r].push_back(make_pair(l, i));
}
build();
solve();
for (int i = 1; i <= m; ++i)
printf("%d %d\n", ans[i].first, ans[i].second);
}