n
n
n个点，每个点
i
i
i只有连向
i
+
1
i+1
i+1和
a
i
a_i
ai两条出边，
m
m
m次操作，支持修改
a
i
a_i
ai，询问点
x
x
x能到达的编号最小的点。
n
,
m
≤
1
0
5
n,m\le10^5
n,m≤105
题解
显然
a
i
≥
i
a_i\ge i
ai≥i是没有用的。
考虑某个点
x
x
x会以何种方式走向最优的点，不失一般性地，一定是先往右走若干格，再通过
a
x
a_x
ax走向较小的点，然后如此循环重复。
这个过程中会使用多若干组
(
i
,
a
i
)
(i,a_i)
(i,ai)，它们能在一次询问中被同时使用到当且仅当存在另一组
(
a
j
,
j
]
(a_j,j]
(aj,j]与
(
a
i
,
i
]
(a_i,i]
(ai,i]的交不为空，形象的说即为这若干条左开右闭的线段都不能被不理，至少要有另一条与它有重叠。
那么它能走到的位置即为
x
x
x左边最靠右的一个未被线段覆盖的位置，可以用线段树维护。
具体地，记录每个区间的最小值及最右边的最小值所在的位置，区间合并显然。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
int a[N];
struct {
int r, mi, p;
}f[N * 4];
void make(int v, int l, int r) {
f[v].r = r, f[v].mi = 0;
if(l == r) return;
int mid = (l + r) / 2;
make(v * 2, l, mid), make(v * 2 + 1, mid + 1, r);
}
int find(int v, int l, int r, int x, int y) {
if(x > y) return -1;
if(l == x && r == y) {
if(f[v].mi == 0) return f[v].r;
return -1;
}
else {
int mid = (l + r) / 2;
f[v * 2].p += f[v].p, f[v * 2 + 1].p += f[v].p;
f[v * 2].mi += f[v].p, f[v * 2 + 1].mi += f[v].p;
f[v].p = 0;
int s;
if(y <= mid) s = find(v * 2, l, mid, x, y);
else if(x > mid) s = find(v * 2 + 1, mid + 1, r, x, y);
else {
int t = find(v * 2 + 1, mid + 1, r, mid + 1, y);
if(t != -1) s = t; else s = find(v * 2, l, mid, x, mid);
}
f[v].mi = min(f[v * 2].mi, f[v * 2 + 1].mi);
if(f[v * 2].mi < f[v * 2 + 1].mi) f[v].r = f[v * 2].r; else f[v].r = f[v * 2 + 1].r;
return s;
}
}
void ins(int v, int l, int r, int x, int y, int c) {
if(x > y) return;
if(l == x && r == y) f[v].mi += c, f[v].p += c;
else {
int mid = (l + r) / 2;
f[v * 2].p += f[v].p, f[v * 2 + 1].p += f[v].p;
f[v * 2].mi += f[v].p, f[v * 2 + 1].mi += f[v].p;
f[v].p = 0;
if(y <= mid) ins(v * 2, l, mid, x, y, c);
else if(x > mid) ins(v * 2 + 1, mid + 1, r, x, y, c);
else ins(v * 2, l, mid, x, mid, c), ins(v * 2 + 1, mid + 1, r, mid + 1, y, c);
f[v].mi = min(f[v * 2].mi, f[v * 2 + 1].mi);
if(f[v * 2].mi < f[v * 2 + 1].mi) f[v].r = f[v * 2].r; else f[v].r = f[v * 2 + 1].r;
}
}
int main() {
int n, Q, i, j;
scanf("%d%d", &n, &Q);
make(1, 1, n);
for(i = 1; i <= n; i++) {
scanf("%d", &a[i]);
ins(1, 1, n, a[i] + 1, i, 1);
}
while(Q--) {
int op, x, y;
scanf("%d", &op);
if(op == 1) {
scanf("%d%d", &x, &y);
ins(1, 1, n, a[x] + 1, x, -1);
a[x] = y;
ins(1, 1, n, a[x] + 1, x, 1);
}
else {
scanf("%d", &x);
int t = find(1, 1, n, 1, x);
printf("%d\n", t == -1 ? i : t);
}
}
return 0;
}