整体二分学习笔记
2026-02-13 13:57:20
发布于：广东
17阅读
0回复
0点赞
板子题 P2617。
Difficulty：6.3 / Template
Tag：整体二分
思想就是对答案二分。
把所有答案在区间 的询问，修改的值在 的操作放一块处理，看看有多少答案在区间 ，多少在区间 。树状数组即可。
还有 std::stable_partition 太好用了你知道吗。
。
#include <bits/stdc++.h>
const int N = 100000;
struct node{
int tmp, l, r, k, ansid;
}q[N * 3 + 5];
int ans[N + 5];
int a[N + 5], b[N * 2 + 5];
int ctq, cta, ctb;
int n, m;
namespace DS{
int tr[N * 2 + 5];
void modify(int idx, int val){
for(int i = idx; i <= N * 2; i += (i & (-i))) tr[i] += val;
}
int query(int idx){
int ans = 0;
for(int i = idx; i; i -= (i & (-i))) ans += tr[i];
return ans;
}
}
void solve(int l, int r, int ql, int qr){
if(l > r || ql > qr) return;
if(l == r){
for(int i = ql; i <= qr; i++){
if(q[i].tmp == 2) ans[q[i].ansid] = b[l];
}
return;
}
int mid = (l + r) >> 1;
int idx = std::stable_partition(q + ql, q + qr + 1, [&](node &cur){
if(cur.tmp == 1){
if(cur.l <= mid){
DS::modify(cur.r, cur.k);
return 1;
}
return 0;
}
int val = DS::query(cur.r) - DS::query(cur.l - 1);
if(cur.k > val){
cur.k -= val;
return 0;
}
return 1;
}) - q - 1;
for(int i = ql; i <= idx; i++){
if(q[i].tmp == 1) DS::modify(q[i].r, -q[i].k);
}
solve(l, mid, ql, idx), solve(mid + 1, r, idx + 1, qr);
}
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0), std::cout.tie(0);
std::cin >> n >> m;
for(int i = 1; i <= n; i++){
std::cin >> a[i];
q[++ctq] = {1, a[i], i, 1, 1055148};
b[++ctb] = a[i];
}
for(int i = 1; i <= m; i++){
char tmp;
std::cin >> tmp;
if(tmp == 'C'){
int idx, val;
std::cin >> idx >> val;
q[++ctq] = {1, a[idx], idx, -1, 1590033};
q[++ctq] = {1, val, idx, 1, 1590033};
a[idx] = val;
b[++ctb] = val;
}else{
int l, r, k;
std::cin >> l >> r >> k;
q[++ctq] = {2, l, r, k, ++cta};
}
}
std::sort(b + 1, b + ctb + 1);
for(int i = 1; i <= ctq; i++){
if(q[i].tmp == 1) q[i].l = std::lower_bound(b + 1, b + ctb + 1, q[i].l) - b;
}
solve(1, ctb, 1, ctq);
for(int i = 1; i <= cta; i++){
std::cout << ans[i] << '\n';
}
return 0;
}
有帮助，赞一个