成都网站建设公司地址,网站开发方向 英语翻译,博爱网站建设,做的网站第二年续费多钱题目来源#xff1a;[HEOI2016/TJOI2016] 排序 - 洛谷https://www.luogu.com.cn/problem/P2824 问题思路 本文介绍一种二分答案的做法#xff0c;时间复杂度为#xff1a;(nm)*log(n)*log(n).本题存在nlog(n)的做法#xff0c;然而其做法没有二分答案的做法通俗易懂. 默认读…题目来源[HEOI2016/TJOI2016] 排序 - 洛谷https://www.luogu.com.cn/problem/P2824 问题思路 本文介绍一种二分答案的做法时间复杂度为(nm)*log(n)*log(n).本题存在nlog(n)的做法然而其做法没有二分答案的做法通俗易懂. 默认读者已读过原题故直接介绍思路.
二分枚举答案为mid对于原序列中大于或等于mid的元素将其转化为1对于其他元素将其转化为0.现在原排列已转化为01序列m次操作对01序列进行排序.经过m次排序操作后如果第p个位置上的元素为1那么更新二分边界 r mid.否则如果第p个位置上的元素为0那么更新二分边界 l mid.如何维护m次操作呢该问题转化为线段树的修改查找问题。没有接触过线段树修查问题的读者建议先去学习相关知识此处不多赘述. 好了思路介绍完了你可能惊讶于为什么二分答案可行.如下便是二分答案可行性的一些解释. 假如经过m次操作后第p个位置上的元素为x0。我们考虑m次普通的序列排序但是此次排序咱们让每一个元素都夹带“私货”.对应于问题思路中的第一步令mid x0对于xmid的元素让它带上额外的元素1.对于xx0的元素让它带上额外的元素0.经过m次操作后元素x0位于第p个位置上且额外的“私货”——元素1也随之到达了第p个位置. 看到这里是否嗅到了二分答案的味道?既然 mid x0可行那么按照mid x0 - 1,x0 - 2....的要求给元素分配额外“私货”0和1那么 1 依旧会随着元素x0来到第p个位置上.然而假如midx0那么跟随元素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解释到此结束更多细节问题请参考代码
#includebits/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];vectorarrayint, 3op(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-k1,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;
}
