P2824 排序
题目描述
给出一个
0 l r
表示将区间的数字升序排序 1 l r
表示将区间的数字降序排序
注意,这里是对下标在区间
最后询问第
输入格式
输入数据的第一行为两个整数
第二行为
接下来输入
最后输入一个整数
输出格式
输出数据仅有一行,一个整数,表示按照顺序将全部的部分排序结束后第
Sloution
线段树+二分+01 序列排序
C38 线段树+二分 P2824 [HEOI2016/TJOI2016] 排序 - 董晓 - 博客园
由于给出的是排列,具有单调性,每次将序列中大于等于 mid
的数置为 1,否则置为 0,每次将 01 序列排序之后在题目要查询的位置会有一个 0|1
若为 1,则答案是大于等于这个值的,若为 0,则答案是小于这个值的。
注:当区间全为 0 或全为 1 时需要直接进行下一个循环,不然会RE
#define lc u<<1
#define rc u<<1|1
int n, m;int q;
int a[100010], OP[100010], L[100010], R[100010];
struct Tree { //线段树
ll l, r, sum, tag;
}tr[400010];
void pushup(ll u) { //上传
tr[u].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(ll u) { //下传
if (tr[u].tag == 0 || tr[u].tag == 1) {
tr[lc].sum = tr[u].tag * (tr[lc].r - tr[lc].l + 1);
tr[rc].sum = tr[u].tag * (tr[rc].r - tr[rc].l + 1);
tr[lc].tag = tr[u].tag;
tr[rc].tag = tr[u].tag;
tr[u].tag = -1;
}
}
void build(ll u, ll l, ll r, ll x) { //建树
tr[u] = {l,r,a[l] >= x,-1};
if (l == r) return;
ll m = l + r >> 1;
build(lc, l, m, x);
build(rc, m + 1, r, x);
pushup(u);
}
void change(ll u, ll l, ll r, ll k) { //区修
if (l <= tr[u].l && tr[u].r <= r) {
tr[u].sum = (tr[u].r - tr[u].l + 1) * k;
tr[u].tag = k;
return;
}
ll m = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (l <= m) change(lc, l, r, k);
if (r > m) change(rc, l, r, k);
pushup(u);
}
ll query(ll u, ll l, ll r) { //区查
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
ll m = tr[u].l + tr[u].r >> 1;
pushdown(u);
ll sum = 0;
if (l <= m) sum += query(lc, l, r);
if (r > m) sum += query(rc, l, r);
return sum;
}
bool check(int x) {
build(1, 1, n, x);
for (int i = 1;i <= m;i++) {
int l = L[i], r = R[i];
int cnt = query(1, l, r);
if (cnt == 0 || cnt == r - l + 1) {
continue;
}
if (OP[i] == 0) {
change(1, l, r - cnt, 0);
change(1, r - cnt + 1, r, 1);
} else {
change(1, l, l + cnt - 1, 1);
change(1, l + cnt, r, 0);
}
}
return query(1, q, q);
}
void solve() {
cin >> n >> m;
for (int i = 1;i <= n;i++)cin >> a[i];
for (int i = 1;i <= m;i++) {
cin >> OP[i] >> L[i] >> R[i];
}
cin >> q;
int l = 0, r = n + 1;
while (l + 1 < r) {
int mid = l + r >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
cout << l << '\n';
}
也可
int l = 1, r = n;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << l - 1 << '\n';