```cpp
#include<bits/stdc++.h>
#define N 300005
using namespace std;
int n, m;
int o[100005], ans[100005], a[100005], cnt;
struct node{
int l, r, k, id, type;
}Q[N], q1[N], q2[N];
int lowbit(int x) {return x & (-x);}
int query(int x) {if(x == 0) return 0; int res = 0; for(int i = x; i; i -= lowbit(i)) res += o[i]; return res;}
void add(int x, int y) {for(int i = x; i <= n; i += lowbit(i)) o[i] += y;}
int ask(int l, int r) {return l == 1 ? query(r) : query(r) - query(l - 1);}
void Sol(int l, int r, int ql, int qr) {
if(ql > qr) return;
if(l == r) {
for(int i = ql; i <= qr; i++) if(Q[i].type == 2) ans[Q[i].id] = l;
return;
}
int mid = (l + r) / 2, cnt1 = 0, cnt2 = 0; //把(l+r)/2 改成 (l+r)>>1 就过了
for(int i = ql; i <= qr; i++) {
if(Q[i].type == 1) {
if(Q[i].l <= mid) q1[++cnt1] = Q[i], add(Q[i].id, Q[i].r);
else q2[++cnt2] = Q[i];
}
else {
int x = ask(Q[i].l, Q[i].r);
if(Q[i].k <= x) q1[++cnt1] = Q[i];
else {
Q[i].k -= x;
q2[++cnt2] = Q[i];
}
}
}
for(int i = 1; i <= cnt1; i++) if(q1[i].type == 1) add(q1[i].id, -q1[i].r);
for(int i = ql, j = 1; j <= cnt1; i++, j++) Q[i] = q1[j];
for(int i = ql + cnt1, j = 1; j <= cnt2; i++, j++) Q[i] = q2[j];
Sol(l, mid, ql, ql + cnt1 - 1); Sol(mid + 1, r, ql + cnt1, qr);
}
signed main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) Q[++cnt] = (node){a[i], 1, -1, i, 1};
for(int i = 1; i <= m; i++) ans[i] = 1e9 + 5;
for(int i = 1, l, r, k, x, y; i <= m; i++) {
char c;
cin >> c;
if(c == 'Q') {
scanf("%d %d %d", &l, &r, &k);
Q[++cnt] = (node){l, r, k, i, 2};
}
else {
scanf("%d %d", &x, &y);
Q[++cnt] = (node){a[x], -1, -1, x, 1};
a[x] = y;
Q[++cnt] = (node){a[x], 1, -1, x, 1};
}
}
Sol(-1e9, 1e9, 1, cnt);
for(int i = 1; i <= m; i++) if(ans[i] != 1e9 + 5) printf("%d\n", ans[i]);
return 0;
}
/*
1 1
0
Q 1 1 1
*/
```
by 小超手123 @ 2023-11-30 10:48:49
@[小超手123](/user/490978) 你可以将整个区间向右平移呀
by _Catluo_ @ 2023-11-30 10:54:20
只见过必须用```(l+r)/2```的，没见过只能用```(l+r)>>1```的。。。
by operator_ @ 2023-11-30 10:56:12
@[_Catluo_](/user/593791) 懒得。有这个功夫，我还不如离散化。。。
by 小超手123 @ 2023-11-30 10:59:35
@[operator_](/user/499682) 这下你就见到了
by 小超手123 @ 2023-11-30 11:00:13
对于这个问题，可能是因为 C/C++ 语言除法运算的 Feature。在二分取 mid 时，应该是使用向下取整来取得 mid，不过 C/C++ 的除法运算对于负数是向上取整。
您提到了右移运算，确实，对于任意数字，他右移 2 的结果正好是这个数字除以 2 后向下取整的结果，这涉及到计算机的负数存储问题。
在二分边界可能存在负数的情况，最好还是使用右移运算符，因为正常的除法不能处理负数的向下取整。因此，在实际应用中，二分取 mid 时，最好是使用右移运算符。
by chat_jinxuan @ 2023-11-30 11:05:21
l + (r - l) / 2
by 小粉兔 @ 2023-11-30 11:08:11
管理楼下！
by chat_jinxuan @ 2023-11-30 11:09:25
@[chat_jinxuan](/user/726525) @[小粉兔](/user/10703) 感谢
by 小超手123 @ 2023-11-30 11:11:09
@[chat_jinxuan](/user/726525) 楼【】【】下
by Disjoint_cat @ 2023-11-30 11:41:30