Nefine_incist_0130D
2025-12-06 18:07:45
发布于：北京
6阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const int INF = 1e9;
const int LOG = 20;
int n, m;
int a[MAXN], b[MAXN];
int s[MAXN]; // 前缀和：s[0]=0, s[i] = s[i-1] + (b[i]==1 ? 1 : -1)
int f[MAXN]; // f[i]：从i到n最少需要分几段
// 线段树：维护区间最小值（用于check函数）
struct SegTree {
int size;
vector<int> tree;
SegTree(int n) {
size = 1;
while (size < n) size <<= 1;
tree.assign(2 * size, INF);
}
void update(int pos, int val) {
pos += size;
tree[pos] = min(tree[pos], val);
for (pos >>= 1; pos >= 1; pos >>= 1) {
tree[pos] = min(tree[2*pos], tree[2*pos+1]);
}
}
int query(int l, int r) { // 查询[l, r]的最小值
l += size;
r += size;
int res = INF;
while (l <= r) {
if (l % 2 == 1) res = min(res, tree[l++]);
if (r % 2 == 0) res = min(res, tree[r--]);
l >>= 1;
r >>= 1;
}
return res;
}
};
// ST表：维护a数组区间最小值的位置（用于构造字典序最小序列）
int st[MAXN][LOG];
int lg[MAXN];
void init_st() {
lg[1] = 0;
for (int i = 2; i <= n; ++i) lg[i] = lg[i/2] + 1;
for (int i = 1; i <= n; ++i) st[i][0] = i;
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
int p1 = st[i][j-1];
int p2 = st[i + (1 << (j-1))][j-1];
st[i][j] = (a[p1] < a[p2]) ? p1 : p2;
}
}
}
// 查询[l, r]中a[r]最小的位置
int get_min_pos(int l, int r) {
if (l > r) return -1;
int k = lg[r - l + 1];
int p1 = st[l][k];
int p2 = st[r - (1 << k) + 1][k];
return (a[p1] < a[p2]) ? p1 : p2;
}
// 检查D是否可行：能否将1~n分为<=m段，每段|s[r]-s[l-1]| <= D
bool check(int D) {
fill(f, f + n + 1, INF);
f[n] = 0; // 从n到n无需分段
int offset = n; // s的范围[-n, n] → 偏移为[0, 2n]
SegTree seg(2 * n + 1);
seg.update(s[n] + offset, f[n]);
for (int i = n - 1; i >= 0; --i) {
int L = s[i] - D + offset;
int R = s[i] + D + offset;
L = max(L, 0);
R = min(R, 2 * n);
int min_f = seg.query(L, R);
if (min_f != INF) f[i] = min_f + 1;
seg.update(s[i] + offset, f[i]);
}
return f[0] <= m;
}
// 构造字典序最小的分割序列
vector<int> construct(int D) {
// 重新计算f数组
fill(f, f + n + 1, INF);
f[n] = 0;
int offset = n;
SegTree seg(2 * n + 1);
seg.update(s[n] + offset, f[n]);
for (int i = n - 1; i >= 0; --i) {
int L = s[i] - D + offset;
int R = s[i] + D + offset;
L = max(L, 0);
R = min(R, 2 * n);
int min_f = seg.query(L, R);
if (min_f != INF) f[i] = min_f + 1;
seg.update(s[i] + offset, f[i]);
}
init_st(); // 预处理ST表
vector<int> res;
int prev = 0; // 上一个分割点（初始为0）
for (int k = 1; k <= m; ++k) {
int target = m - k; // 剩余需要分的段数
int start = prev + 1, end = n;
int best_r = -1;
// 二分找满足条件的r的范围：[start, end]
// 找左边界：第一个满足|s[r]-s[prev]|<=D且f[r]<=target的r
int l = start, r = end;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) r = mid - 1;
else l = mid + 1;
}
start = l;
// 找右边界：最后一个满足|s[r]-s[prev]|<=D且f[r]<=target的r
l = prev + 1, r = end;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) l = mid + 1;
else r = mid - 1;
}
end = r;
if (start > end) { // 无合法范围，退而求其次找第一个满足的
for (int rr = prev + 1; rr <= n; ++rr) {
if (abs(s[rr] - s[prev]) <= D && f[rr] <= target) {
best_r = rr;
break;
}
}
} else { // 找区间内a[r]最小的位置
best_r = get_min_pos(start, end);
}
res.push_back(a[best_r]);
prev = best_r;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
// 计算前缀和s
s[0] = 0;
for (int i = 1; i <= n; ++i) {
s[i] = s[i-1] + (b[i] == 1 ? 1 : -1);
}
// 二分找最小的D
int left = 0, right = n, D_min = n;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid)) {
D_min = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
// 构造答案并输出
vector<int> ans = construct(D_min);
for (int i = 0; i < ans.size(); ++i) {
if (i > 0) cout << " ";
cout << ans[i];
}
cout << endl;
return 0;
}~~#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const int INF = 1e9;
const int LOG = 20;
int n, m;
int a[MAXN], b[MAXN];
int s[MAXN]; // 前缀和：s[0]=0, s[i] = s[i-1] + (b[i]==1 ? 1 : -1)
int f[MAXN]; // f[i]：从i到n最少需要分几段
// 线段树：维护区间最小值（用于check函数）
struct SegTree {
int size;
vector<int> tree;
SegTree(int n) {
size = 1;
while (size < n) size <<= 1;
tree.assign(2 * size, INF);
}
void update(int pos, int val) {
pos += size;
tree[pos] = min(tree[pos], val);
for (pos >>= 1; pos >= 1; pos >>= 1) {
tree[pos] = min(tree[2*pos], tree[2*pos+1]);
}
}
int query(int l, int r) { // 查询[l, r]的最小值
l += size;
r += size;
int res = INF;
while (l <= r) {
if (l % 2 == 1) res = min(res, tree[l++]);
if (r % 2 == 0) res = min(res, tree[r--]);
l >>= 1;
r >>= 1;
}
return res;
}
};
// ST表：维护a数组区间最小值的位置（用于构造字典序最小序列）
int st[MAXN][LOG];
int lg[MAXN];
void init_st() {
lg[1] = 0;
for (int i = 2; i <= n; ++i) lg[i] = lg[i/2] + 1;
for (int i = 1; i <= n; ++i) st[i][0] = i;
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
int p1 = st[i][j-1];
int p2 = st[i + (1 << (j-1))][j-1];
st[i][j] = (a[p1] < a[p2]) ? p1 : p2;
}
}
}
// 查询[l, r]中a[r]最小的位置
int get_min_pos(int l, int r) {
if (l > r) return -1;
int k = lg[r - l + 1];
int p1 = st[l][k];
int p2 = st[r - (1 << k) + 1][k];
return (a[p1] < a[p2]) ? p1 : p2;
}
// 检查D是否可行：能否将1~n分为<=m段，每段|s[r]-s[l-1]| <= D
bool check(int D) {
fill(f, f + n + 1, INF);
f[n] = 0; // 从n到n无需分段
int offset = n; // s的范围[-n, n] → 偏移为[0, 2n]
SegTree seg(2 * n + 1);
seg.update(s[n] + offset, f[n]);
for (int i = n - 1; i >= 0; --i) {
int L = s[i] - D + offset;
int R = s[i] + D + offset;
L = max(L, 0);
R = min(R, 2 * n);
int min_f = seg.query(L, R);
if (min_f != INF) f[i] = min_f + 1;
seg.update(s[i] + offset, f[i]);
}
return f[0] <= m;
}
// 构造字典序最小的分割序列
vector<int> construct(int D) {
// 重新计算f数组
fill(f, f + n + 1, INF);
f[n] = 0;
int offset = n;
SegTree seg(2 * n + 1);
seg.update(s[n] + offset, f[n]);
for (int i = n - 1; i >= 0; --i) {
int L = s[i] - D + offset;
int R = s[i] + D + offset;
L = max(L, 0);
R = min(R, 2 * n);
int min_f = seg.query(L, R);
if (min_f != INF) f[i] = min_f + 1;
seg.update(s[i] + offset, f[i]);
}
init_st(); // 预处理ST表
vector<int> res;
int prev = 0; // 上一个分割点（初始为0）
for (int k = 1; k <= m; ++k) {
int target = m - k; // 剩余需要分的段数
int start = prev + 1, end = n;
int best_r = -1;
// 二分找满足条件的r的范围：[start, end]
// 找左边界：第一个满足|s[r]-s[prev]|<=D且f[r]<=target的r
int l = start, r = end;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) r = mid - 1;
else l = mid + 1;
}
start = l;
// 找右边界：最后一个满足|s[r]-s[prev]|<=D且f[r]<=target的r
l = prev + 1, r = end;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) l = mid + 1;
else r = mid - 1;
}
end = r;
if (start > end) { // 无合法范围，退而求其次找第一个满足的
for (int rr = prev + 1; rr <= n; ++rr) {
if (abs(s[rr] - s[prev]) <= D && f[rr] <= target) {
best_r = rr;
break;
}
}
} else { // 找区间内a[r]最小的位置
best_r = get_min_pos(start, end);
}
res.push_back(a[best_r]);
prev = best_r;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
// 计算前缀和s
s[0] = 0;
for (int i = 1; i <= n; ++i) {
s[i] = s[i-1] + (b[i] == 1 ? 1 : -1);
}
// 二分找最小的D
int left = 0, right = n, D_min = n;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid)) {
D_min = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
// 构造答案并输出
vector<int> ans = construct(D_min);
for (int i = 0; i < ans.size(); ++i) {
if (i > 0) cout << " ";
cout << ans[i];
}
cout << endl;
return 0;
}[链接描述](#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const int INF = 1e9;
const int LOG = 20;
int n, m;
int a[MAXN], b[MAXN];
int s[MAXN]; // 前缀和：s[0]=0, s[i] = s[i-1] + (b[i]==1 ? 1 : -1)
int f[MAXN]; // f[i]：从i到n最少需要分几段
// 线段树：维护区间最小值（用于check函数）
struct SegTree {
int size;
vector<int> tree;
SegTree(int n) {
size = 1;
while (size < n) size <<= 1;
tree.assign(2 * size, INF);
}
void update(int pos, int val) {
pos += size;
tree[pos] = min(tree[pos], val);
for (pos >>= 1; pos >= 1; pos >>= 1) {
tree[pos] = min(tree[2*pos], tree[2*pos+1]);
}
}
int query(int l, int r) { // 查询[l, r]的最小值
l += size;
r += size;
int res = INF;
while (l <= r) {
if (l % 2 == 1) res = min(res, tree[l++]);
if (r % 2 == 0) res = min(res, tree[r--]);
l >>= 1;
r >>= 1;
}
return res;
}
};
// ST表：维护a数组区间最小值的位置（用于构造字典序最小序列）
int st[MAXN][LOG];
int lg[MAXN];
void init_st() {
lg[1] = 0;
for (int i = 2; i <= n; ++i) lg[i] = lg[i/2] + 1;
for (int i = 1; i <= n; ++i) st[i][0] = i;
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
int p1 = st[i][j-1];
int p2 = st[i + (1 << (j-1))][j-1];
st[i][j] = (a[p1] < a[p2]) ? p1 : p2;
}
}
}
// 查询[l, r]中a[r]最小的位置
int get_min_pos(int l, int r) {
if (l > r) return -1;
int k = lg[r - l + 1];
int p1 = st[l][k];
int p2 = st[r - (1 << k) + 1][k];
return (a[p1] < a[p2]) ? p1 : p2;
}
// 检查D是否可行：能否将1~n分为<=m段，每段|s[r]-s[l-1]| <= D
bool check(int D) {
fill(f, f + n + 1, INF);
f[n] = 0; // 从n到n无需分段
int offset = n; // s的范围[-n, n] → 偏移为[0, 2n]
SegTree seg(2 * n + 1);
seg.update(s[n] + offset, f[n]);
for (int i = n - 1; i >= 0; --i) {
int L = s[i] - D + offset;
int R = s[i] + D + offset;
L = max(L, 0);
R = min(R, 2 * n);
int min_f = seg.query(L, R);
if (min_f != INF) f[i] = min_f + 1;
seg.update(s[i] + offset, f[i]);
}
return f[0] <= m;
}
// 构造字典序最小的分割序列
vector<int> construct(int D) {
// 重新计算f数组
fill(f, f + n + 1, INF);
f[n] = 0;
int offset = n;
SegTree seg(2 * n + 1);
seg.update(s[n] + offset, f[n]);
for (int i = n - 1; i >= 0; --i) {
int L = s[i] - D + offset;
int R = s[i] + D + offset;
L = max(L, 0);
R = min(R, 2 * n);
int min_f = seg.query(L, R);
if (min_f != INF) f[i] = min_f + 1;
seg.update(s[i] + offset, f[i]);
}
init_st(); // 预处理ST表
vector<int> res;
int prev = 0; // 上一个分割点（初始为0）
for (int k = 1; k <= m; ++k) {
int target = m - k; // 剩余需要分的段数
int start = prev + 1, end = n;
int best_r = -1;
// 二分找满足条件的r的范围：[start, end]
// 找左边界：第一个满足|s[r]-s[prev]|<=D且f[r]<=target的r
int l = start, r = end;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) r = mid - 1;
else l = mid + 1;
}
start = l;
// 找右边界：最后一个满足|s[r]-s[prev]|<=D且f[r]<=target的r
l = prev + 1, r = end;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) l = mid + 1;
else r = mid - 1;
}
end = r;
if (start > end) { // 无合法范围，退而求其次找第一个满足的
for (int rr = prev + 1; rr <= n; ++rr) {
if (abs(s[rr] - s[prev]) <= D && f[rr] <= target) {
best_r = rr;
break;
}
}
} else { // 找区间内a[r]最小的位置
best_r = get_min_pos(start, end);
}
res.push_back(a[best_r]);
prev = best_r;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
// 计算前缀和s
s[0] = 0;
for (int i = 1; i <= n; ++i) {
s[i] = s[i-1] + (b[i] == 1 ? 1 : -1);
}
// 二分找最小的D
int left = 0, right = n, D_min = n;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid)) {
D_min = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
// 构造答案并输出
vector<int> ans = construct(D_min);
for (int i = 0; i < ans.size(); ++i) {
if (i > 0) cout << " ";
cout << ans[i];
}
cout << endl;
return 0;
}
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const int INF = 1e9;
const int LOG = 20;
int n, m;
int a[MAXN], b[MAXN];
int s[MAXN]; // 前缀和：s[0]=0, s[i] = s[i-1] + (b[i]==1 ? 1 : -1)
int f[MAXN]; // f[i]：从i到n最少需要分几段
// 线段树：维护区间最小值（用于check函数）
struct SegTree {
int size;
vector<int> tree;
SegTree(int n) {
size = 1;
while (size < n) size <<= 1;
tree.assign(2 * size, INF);
}
void update(int pos, int val) {
pos += size;
tree[pos] = min(tree[pos], val);
for (pos >>= 1; pos >= 1; pos >>= 1) {
tree[pos] = min(tree[2*pos], tree[2*pos+1]);
}
}
int query(int l, int r) { // 查询[l, r]的最小值
l += size;
r += size;
int res = INF;
while (l <= r) {
if (l % 2 == 1) res = min(res, tree[l++]);
if (r % 2 == 0) res = min(res, tree[r--]);
l >>= 1;
r >>= 1;
}
return res;
}
};
// ST表：维护a数组区间最小值的位置（用于构造字典序最小序列）
int st[MAXN][LOG];
int lg[MAXN];
void init_st() {
lg[1] = 0;
for (int i = 2; i <= n; ++i) lg[i] = lg[i/2] + 1;
for (int i = 1; i <= n; ++i) st[i][0] = i;
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
int p1 = st[i][j-1];
int p2 = st[i + (1 << (j-1))][j-1];
st[i][j] = (a[p1] < a[p2]) ? p1 : p2;
}
}
}
// 查询[l, r]中a[r]最小的位置
int get_min_pos(int l, int r) {
if (l > r) return -1;
int k = lg[r - l + 1];
int p1 = st[l][k];
int p2 = st[r - (1 << k) + 1][k];
return (a[p1] < a[p2]) ? p1 : p2;
}
// 检查D是否可行：能否将1~n分为<=m段，每段|s[r]-s[l-1]| <= D
bool check(int D) {
fill(f, f + n + 1, INF);
f[n] = 0; // 从n到n无需分段
int offset = n; // s的范围[-n, n] → 偏移为[0, 2n]
SegTree seg(2 * n + 1);
seg.update(s[n] + offset, f[n]);
for (int i = n - 1; i >= 0; --i) {
int L = s[i] - D + offset;
int R = s[i] + D + offset;
L = max(L, 0);
R = min(R, 2 * n);
int min_f = seg.query(L, R);
if (min_f != INF) f[i] = min_f + 1;
seg.update(s[i] + offset, f[i]);
}
return f[0] <= m;
}
// 构造字典序最小的分割序列
vector<int> construct(int D) {
// 重新计算f数组
fill(f, f + n + 1, INF);
f[n] = 0;
int offset = n;
SegTree seg(2 * n + 1);
seg.update(s[n] + offset, f[n]);
for (int i = n - 1; i >= 0; --i) {
int L = s[i] - D + offset;
int R = s[i] + D + offset;
L = max(L, 0);
R = min(R, 2 * n);
int min_f = seg.query(L, R);
if (min_f != INF) f[i] = min_f + 1;
seg.update(s[i] + offset, f[i]);
}
init_st(); // 预处理ST表
vector<int> res;
int prev = 0; // 上一个分割点（初始为0）
for (int k = 1; k <= m; ++k) {
int target = m - k; // 剩余需要分的段数
int start = prev + 1, end = n;
int best_r = -1;
// 二分找满足条件的r的范围：[start, end]
// 找左边界：第一个满足|s[r]-s[prev]|<=D且f[r]<=target的r
int l = start, r = end;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) r = mid - 1;
else l = mid + 1;
}
start = l;
// 找右边界：最后一个满足|s[r]-s[prev]|<=D且f[r]<=target的r
l = prev + 1, r = end;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) l = mid + 1;
else r = mid - 1;
}
end = r;
if (start > end) { // 无合法范围，退而求其次找第一个满足的
for (int rr = prev + 1; rr <= n; ++rr) {
if (abs(s[rr] - s[prev]) <= D && f[rr] <= target) {
best_r = rr;
break;
}
}
} else { // 找区间内a[r]最小的位置
best_r = get_min_pos(start, end);
}
res.push_back(a[best_r]);
prev = best_r;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
// 计算前缀和s
s[0] = 0;
for (int i = 1; i <= n; ++i) {
s[i] = s[i-1] + (b[i] == 1 ? 1 : -1);
}
// 二分找最小的D
int left = 0, right = n, D_min = n;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid)) {
D_min = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
// 构造答案并输出
vector<int> ans = construct(D_min);
for (int i = 0; i < ans.size(); ++i) {
if (i > 0) cout << " ";
cout << ans[i];
}
cout << endl;
return 0;
}*#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const int INF = 1e9;
const int LOG = 20;
int n, m;
int a[MAXN], b[MAXN];
int s[MAXN]; // 前缀和：s[0]=0, s[i] = s[i-1] + (b[i]==1 ? 1 : -1)
int f[MAXN]; // f[i]：从i到n最少需要分几段
// 线段树：维护区间最小值（用于check函数）
struct SegTree {
int size;
vector<int> tree;
SegTree(int n) {
size = 1;
while (size < n) size <<= 1;
tree.assign(2 * size, INF);
}
void update(int pos, int val) {
pos += size;
tree[pos] = min(tree[pos], val);
for (pos >>= 1; pos >= 1; pos >>= 1) {
tree[pos] = min(tree[2*pos], tree[2*pos+1]);
}
}
int query(int l, int r) { // 查询[l, r]的最小值
l += size;
r += size;
int res = INF;
while (l <= r) {
if (l % 2 == 1) res = min(res, tree[l++]);
if (r % 2 == 0) res = min(res, tree[r--]);
l >>= 1;
r >>= 1;
}
return res;
}
};
// ST表：维护a数组区间最小值的位置（用于构造字典序最小序列）
int st[MAXN][LOG];
int lg[MAXN];
void init_st() {
lg[1] = 0;
for (int i = 2; i <= n; ++i) lg[i] = lg[i/2] + 1;
for (int i = 1; i <= n; ++i) st[i][0] = i;
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
int p1 = st[i][j-1];
int p2 = st[i + (1 << (j-1))][j-1];
st[i][j] = (a[p1] < a[p2]) ? p1 : p2;
}
}
}
// 查询[l, r]中a[r]最小的位置
int get_min_pos(int l, int r) {
if (l > r) return -1;
int k = lg[r - l + 1];
int p1 = st[l][k];
int p2 = st[r - (1 << k) + 1][k];
return (a[p1] < a[p2]) ? p1 : p2;
}
// 检查D是否可行：能否将1~n分为<=m段，每段|s[r]-s[l-1]| <= D
bool check(int D) {
fill(f, f + n + 1, INF);
f[n] = 0; // 从n到n无需分段
int offset = n; // s的范围[-n, n] → 偏移为[0, 2n]
SegTree seg(2 * n + 1);
seg.update(s[n] + offset, f[n]);
for (int i = n - 1; i >= 0; --i) {
int L = s[i] - D + offset;
int R = s[i] + D + offset;
L = max(L, 0);
R = min(R, 2 * n);
int min_f = seg.query(L, R);
if (min_f != INF) f[i] = min_f + 1;
seg.update(s[i] + offset, f[i]);
}
return f[0] <= m;
}
// 构造字典序最小的分割序列
vector<int> construct(int D) {
// 重新计算f数组
fill(f, f + n + 1, INF);
f[n] = 0;
int offset = n;
SegTree seg(2 * n + 1);
seg.update(s[n] + offset, f[n]);
for (int i = n - 1; i >= 0; --i) {
int L = s[i] - D + offset;
int R = s[i] + D + offset;
L = max(L, 0);
R = min(R, 2 * n);
int min_f = seg.query(L, R);
if (min_f != INF) f[i] = min_f + 1;
seg.update(s[i] + offset, f[i]);
}
init_st(); // 预处理ST表
vector<int> res;
int prev = 0; // 上一个分割点（初始为0）
for (int k = 1; k <= m; ++k) {
int target = m - k; // 剩余需要分的段数
int start = prev + 1, end = n;
int best_r = -1;
// 二分找满足条件的r的范围：[start, end]
// 找左边界：第一个满足|s[r]-s[prev]|<=D且f[r]<=target的r
int l = start, r = end;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) r = mid - 1;
else l = mid + 1;
}
start = l;
// 找右边界：最后一个满足|s[r]-s[prev]|<=D且f[r]<=target的r
l = prev + 1, r = end;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(s[mid] - s[prev]) <= D && f[mid] <= target) l = mid + 1;
else r = mid - 1;
}
end = r;
if (start > end) { // 无合法范围，退而求其次找第一个满足的
for (int rr = prev + 1; rr <= n; ++rr) {
if (abs(s[rr] - s[prev]) <= D && f[rr] <= target) {
best_r = rr;
break;
}
}
} else { // 找区间内a[r]最小的位置
best_r = get_min_pos(start, end);
}
res.push_back(a[best_r]);
prev = best_r;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
// 计算前缀和s
s[0] = 0;
for (int i = 1; i <= n; ++i) {
s[i] = s[i-1] + (b[i] == 1 ? 1 : -1);
}
// 二分找最小的D
int left = 0, right = n, D_min = n;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid)) {
D_min = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
// 构造答案并输出
vector<int> ans = construct(D_min);
for (int i = 0; i < ans.size(); ++i) {
if (i > 0) cout << " ";
cout << ans[i];
}
cout << endl;
return 0;
}*
)~~
这里空空如也
有帮助，赞一个