线段树上二分

如题：q个询问 可以单点修改 可以查询某个区间内第一个大于等于d的下标

我们维护最大值 如果这个区间的最大值比d都小
那么这个区间一定是不正确的
继续往后二分
如果这个区间最大值大于d
向左二分

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 10;
#define int long longstruct Node
{int val;
} segs[N * 4];int n, q;
int a[N];void update(int id)
{segs[id].val = max(segs[id * 2].val, segs[id * 2 + 1].val);
}void build(int id, int l, int r)
{if (l == r)segs[id].val = a[l];else{int mid = l + r >> 1;build(id * 2, l, mid);build(id * 2 + 1, mid + 1, r);update(id);}
}// 单点修改
void change(int id, int l, int r, int pos, int val)
{if (l == r)segs[id].val = val;else{int mid = l + r >> 1;if (pos <= mid)change(id * 2, l, mid, pos, val);elsechange(id * 2 + 1, mid + 1, r, pos, val);update(id);}
}// 树上二分
int search(int id, int l, int r, int ql, int qr, int d)
{if (l == ql && r == qr){if (segs[id].val < d) return -1;else{if (l == r) return l;int mid = l + r >> 1;if (segs[id * 2].val >= d) return search(id * 2, l, mid, ql, mid, d);else return search(id * 2 + 1, mid + 1, r, mid + 1, qr, d);}}else{int mid = l + r >> 1;if (qr <= mid) return search(id * 2, l, mid, ql, qr, d);else if (ql > mid) return search(id * 2 + 1, mid + 1, r, ql, qr, d);else{int pos = search(id * 2, l, mid, ql, mid, d);if(pos == -1) pos = search(id * 2 + 1, mid + 1, r, mid + 1, qr, d);return pos;}}
}signed main()
{scanf("%lld %lld", &n, &q);for (int i = 1; i <= n; i++)cin >> a[i];build(1, 1, n);int ty;while (q--){scanf("%lld", &ty);if (ty == 1){int x, d;scanf("%lld%lld", &x, &d);change(1, 1, n, x, d);}else{int l, r, d;scanf("%lld %lld %lld", &l, &r, &d);auto ans = search(1, 1, n, l, r,d);printf("%lld\n", ans);}}
}