Joseph and Tests

[Link](Problem - J - Codeforces)

题意:

给定n个房子的高度，给定m个操作，操作1为把第x个房子的高度改为d，操作2为把从第x个房子当前房子与下一个房子的高度差不大于d就可以走到下一个房子，输出最远走到哪个房子。

题解：

​ 用线段树存一个区间内相邻两个房子差值的的最大值，我们要找的是小于等与d的最后一个位置，所以从x开始二分，l为x，r为n - 1(n个房子n-1个差值)，每次如果x到mid的最大值都小于d则这个区间均成立，就可以让l=mid继续向后查看，否则让r等于mid-1，就可以找到最后一个小于等于的位置了。

​ 对于操作一直接修改维护即可，要特判一下当前位置不是第一个位置的时候才会影响他前一个位置与他的高度差的关系，当前位置不是最后一个位置的时候才会影响他后一个位置和他高度差的关系。

​ 而且当只有一个房子的时候，直接输出就行。

while (l < r) {int mid = l + r  + 1 >> 1;if (check()) l = mid;else r = mid - 1;
}

这个二分模板，如果在当前区间一直不成立的情况下，就会不断的往左边折，最后起始位置不会被判断掉，所以要特判一下起始位置，而且当他放到最后一个位置的时候，就不能再往后走了。

while (l <= r) {int mid = l + r >> 1;if (check()) l = mid + 1; else		 r = mid - 1;
}

这个二分模板是不存在上述特殊情况的。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 2e5 + 100, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N], b[N];
struct Node {int l, r;LL mx;
}tr[N << 2];
void push(int u) {tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx);
}
void build(int u, int l, int r) {tr[u] = {l, r};if (l == r) {tr[u].mx = abs(a[l] - a[l + 1]);return ;}int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);push(u);
}
void update(int u, int pos) {if (tr[u].l == tr[u].r) {tr[u].mx = abs(a[tr[u].l] - a[tr[u].l + 1]);return ;}int mid = tr[u].l + tr[u].r >> 1;if (pos <= mid) update(u << 1, pos);else            update(u << 1 | 1, pos);push(u);
}
int query(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].mx;int mid = tr[u].l + tr[u].r >> 1;int mx = - 1;if (l <= mid)  mx = query(u << 1, l, r);if (r > mid)   mx = max(mx, query(u << 1 | 1, l, r));return mx;
}
int main() {ios::sync_with_stdio(false), cin.tie(0);cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];cin >> m;int op, x, d;if (n == 1) {while (m -- ) {cin >> op >> x >> d;if (op == 2) cout << 1 << endl;}}else {build(1, 1, n - 1);while (m -- ) {cin >> op >> x >> d;if (op == 1) {a[x] = d;if (x > 1) update(1, x - 1); // 对前一个点的影响if (x + 1 <= n) update(1, x); // 对后一个点的影响}else if (op == 2){int l = x, r = n - 1;int res = x;while (l < r) {int mid = l + r + 1 >> 1; // 1 2 归到右边 所以最左边考虑不到 还有直接在最右边的情况if (query(1, x, mid) <= d) l = mid, res = mid + 1;else r = mid - 1; } if (l == x && abs(a[x] - a[x + 1]) <= d && x != n) res ++;//    while (l <= r) {//        int mid = l + r >> 1;//         if (query(1, x, mid) <= d) l = mid + 1, res = mid + 1;//         else r = mid - 1;//    }cout << res << endl;}}}return 0;
}