最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

线段树好题！ P2824 [HEOI2016/TJOI2016]排序 题解

来源：博客园


(资料图片)

题目传送门

前言

线段树好题！！！！咕咕了挺久的一道题目，很早之前就想写了，今天终于找了个时间A掉了。

题意

给定一个 \(1\) 到 \(n\) 的排列，有 \(m\) 次操作，分两种类型。1.0 l r表示将下标在 \([l, r]\) 区间中的数升序排序。2.1 l r表示将下标在 \([l, r]\) 区间中的数降序排序。给定一个数 \(q\) 询问最后 \(q\) 位置上的数。

\(Solution\)

看到数据范围，发现前 \(30\) 分是可以暴力的，这里不多赘述。注意到 \(n,m\leqslant 10^5\) ,优先考虑 \(O(nlogn)\) 或 \(O(n \sqrt n)\) 做法。对一个序列进行操作，自然想到，线段树，但是线段树不支持区间排序那怎么办呢。考虑对一段 \(01\) 串做排序，显然排完序后会变成 \(00011\) 或 \(11100\) 这种形式，可以用线段树的区间推平和求和操作来完成。但是原序列不是 \(01\) 串，我们就要把它转换成 \(01\) 串。可以选取一个基准数，让原序列大于等于这个数的都变成 \(1\) ，其他的都是 \(0\) 就能解决这个问题了。如果操作完之后 \(q\) 上的是 \(1\) ，说明答案至少是大于等于这个基准数的，所以二分就行了。总复杂度 \(O(n log^2n)\)。

code

#include using namespace std;typedef long long ll;const int N = 1e5 + 5, INF = 0x3f3f3f3f;const ll mod = 1e9 + 7;int n, m, pos;int a[N];struct question{int op, l, r;} Q[N];struct segment_tree{int l, r, val, tag;#define l(x) tr[x].l#define r(x) tr[x].r#define val(x) tr[x].val#define tag(x) tr[x].tag} tr[N << 2];void pushup(int x){val(x) = val(x << 1) + val(x << 1 | 1);}void pushdown(int x){if(tag(x) == -1) return;val(x << 1) = (r(x << 1) - l(x << 1) + 1) * tag(x);tag(x << 1) = tag(x);val(x << 1 | 1) = (r(x << 1 | 1) - l(x << 1 | 1) + 1) * tag(x);tag(x << 1 | 1) = tag(x);tag(x) = -1;}void build(int l, int r, int x, int v){l(x) = l, r(x) = r, tag(x) = -1, val(x) = 0;if(l == r){val(x) = (a[l] >= v);return;}int mid = l + r >> 1;build(l, mid, x << 1, v), build(mid + 1, r, x << 1 | 1, v);pushup(x);}void update(int l, int r, int x, int v){if(l <= l(x) && r(x) <= r){tag(x) = v;val(x) = (r(x) - l(x) + 1) * v;return;}pushdown(x);int mid = l(x) + r(x) >> 1;if(l <= mid) update(l, r, x << 1, v);if(r > mid) update(l, r, x << 1 | 1, v);pushup(x);}int query(int l, int r, int x){if(l <= l(x) && r(x) <= r) return val(x);pushdown(x);int mid = l(x) + r(x) >> 1, res = 0;if(l <= mid) res += query(l, r, x << 1);if(r > mid) res += query(l, r, x << 1 | 1);return res;}int check(int v){build(1, n, 1, v);for(int i = 1;i <= m;i ++){int l = Q[i].l, r = Q[i].r, op = Q[i].op;int sum = query(l, r, 1);if(sum == 0) continue;update(l, r, 1, 0);if(op == 0) update(r - sum + 1, r, 1, 1);else update(l, l + sum - 1, 1, 1);}return query(pos, pos, 1);}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;for(int i = 1;i <= n;i ++) cin >> a[i];for(int i = 1;i <= m;i ++) cin >> Q[i].op >> Q[i].l >> Q[i].r;cin >> pos;int l = 1, r = n, res;while(l <= r){int mid = l + r >> 1;if(check(mid)) l = mid + 1, res = mid;else r = mid - 1;}cout << res << "\n";    return 0;}

关键词：