洛谷——P2824 排序

题目来源：[HEOI2016/TJOI2016] 排序 - 洛谷https://www.luogu.com.cn/problem/P2824

 问题思路

        本文介绍一种二分答案的做法，时间复杂度为：(n+m)*log(n)*log(n).本题存在nlog(n)的做法，然而其做法没有二分答案的做法通俗易懂.

        默认读者已读过原题，故直接介绍思路.

1. 二分枚举答案为mid，对于原序列中大于或等于mid的元素，将其转化为1，对于其他元素，将其转化为0.
2. 现在，原排列已转化为01序列，m次操作对01序列进行排序.
3. 经过m次排序操作后，如果第p个位置上的元素为1，那么更新二分边界 r = mid.否则如果第p个位置上的元素为0，那么更新二分边界 l = mid.
4. 如何维护m次操作呢？该问题转化为线段树的修改+查找问题。没有接触过线段树修查问题的读者，建议先去学习相关知识，此处不多赘述.

        好了，思路介绍完了，你可能惊讶于为什么二分答案可行.如下便是二分答案可行性的一些解释.

        假如经过m次操作后，第p个位置上的元素为x0。我们考虑m次普通的序列排序，但是此次排序咱们让每一个元素都夹带“私货”.对应于问题思路中的第一步，令mid = x0，对于x>=mid的元素，让它带上额外的元素1.对于x<x0的元素，让它带上额外的元素0.经过m次操作后，元素x0位于第p个位置上，且额外的“私货”——元素1，也随之到达了第p个位置.

        看到这里是否嗅到了二分答案的味道?既然 mid = x0可行，那么按照mid = x0 - 1,x0 - 2....的要求，给元素分配额外“私货”0和1，那么 1 依旧会随着元素x0来到第p个位置上.然而，假如mid>x0，那么跟随元素x0到达第p个位置上的额外“私货”便是元素0了.

        经过上述解释，你应该理解了二分答案在该题目中的可行性.

        当我们不再考虑普通的序列排序，而是考虑01序列的排序时，对元素0和1进行排序后的结果，必定能够映射到其普通序列的正确的排序结果上.举个例子，对序列 perm = [1,5,2,4,3] 进行排序，先二分答案 mid = 3，那么perm 转化 01序列 bperm = [0,1,0,1,1]，那么对 bperm进行升序排序的结果为： bperm = [0,0,1,1,1]，该排序结果能够映射到其普通序列的正确排序结果上，即

   ==>  perm = [1,2,3,4,5].

OK，解释到此结束，更多细节问题请参考代码：

#include<bits/stdc++.h>
using namespace std;const int N = 100005;
int a[N];int ls(int u) { return u << 1; }
int rs(int u) { return u << 1 | 1; }struct tree {int l, r, s, tag;
}tr[N * 4];void build(int u, int l, int r) {tr[u] = { l,r,0,-1 };if (l == r)return;int mid = l + r >> 1;build(ls(u), l, mid);build(rs(u), mid + 1, r);
}void addTag(int u, int v) {tr[u].s = v * (tr[u].r - tr[u].l + 1);tr[u].tag = v;
}void pu(int u) {tr[u].s = tr[ls(u)].s + tr[rs(u)].s;
}void pd(int u) {//	tag == -1代表该线段的标签已重置...if (tr[u].tag != -1) {addTag(ls(u), tr[u].tag);addTag(rs(u), tr[u].tag);tr[u].tag = -1;}
}void update(int L, int R, int u, int v) {if (tr[u].l > R || tr[u].r < L) return;if (L <= tr[u].l && tr[u].r <= R) {addTag(u, v);return;}pd(u);int mid = (tr[u].l + tr[u].r) >> 1;if (L <= mid) update(L, R, ls(u), v);if (R > mid) update(L, R, rs(u), v);pu(u);
}int query(int L, int R, int u) {if (tr[u].l > R || tr[u].r < L) return 0;if (L <= tr[u].l && tr[u].r <= R) return tr[u].s;pd(u);int mid = (tr[u].l + tr[u].r) >> 1;int ans = 0;if (L <= mid) ans = query(L, R, ls(u));if (R > mid) ans = ans + query(L, R, rs(u));return ans;
}int main() {ios::sync_with_stdio(0), cin.tie(0);int n, m;cin >> n >> m;for (int i = 1;i <= n;i++) cin >> a[i];vector<array<int, 3>>op(m);for (int i = 0;i < m;i++) {cin >> op[i][0] >> op[i][1] >> op[i][2];}build(1, 1, n);int q;cin >> q;int l = 0, r = n + 1;while (l + 1 != r) {update(1, n, 1, 0);int mid = l + r >> 1;for (int i = 1;i <= n;i++)if (a[i] >= mid) update(i, i, 1, 1);for (int i = 0;i < m;i++) {int o = op[i][0], ql = op[i][1], qr = op[i][2];int k = query(ql, qr, 1);int cnt = qr - ql + 1;//	[qr-k+1,qr]全为1，[ql,qr-k]全为0...if (k == 0 || k == cnt) continue;if (o == 0) {update(ql, qr - k, 1, 0);update(qr - k + 1, qr, 1, 1);}else {update(ql, ql + k - 1, 1, 1);update(ql + k, qr, 1, 0);}}query(q, q, 1) == 1 ? l = mid : r = mid;}cout << l << '\n';return 0;
}