首页 > 代码库 > BZOJ 4552: [Tjoi2016&Heoi2016]排序
BZOJ 4552: [Tjoi2016&Heoi2016]排序
4552: [Tjoi2016&Heoi2016]排序
Time Limit: 60 Sec Memory Limit: 256 MBSubmit: 579 Solved: 322
[Submit][Status][Discuss]
Description
在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题
，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排
序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q
位置上的数字。
Input
输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整
数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序
排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 10^5
，1 <= m <= 10^5
Output
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。
Sample Input
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
Sample Output
5
HINT
Source
首先二分答案，然后需要知道进行m次排序后p位置上的数字是否大于mid。
对于一个mid，我们可以把序列里的数字分为两类，即大于mid的数和小于等于mid的数，分别用1和0表示。
对这些0和1进行排序时，对于一个区间[l,r]进行升序排序，等价于把所有的0放在前面，所有的1放在后面；降序排序反之。
用线段树支持区间求和及区间修改即可。
1 #include <bits/stdc++.h> 2 3 #define fread_siz 1024 4 5 inline int get_c(void) 6 { 7 static char buf[fread_siz]; 8 static char *head = buf + fread_siz; 9 static char *tail = buf + fread_siz; 10 11 if (head == tail) 12 fread(head = buf, 1, fread_siz, stdin); 13 14 return *head++; 15 } 16 17 inline int get_i(void) 18 { 19 register int ret = 0; 20 register int neg = false; 21 register int bit = get_c(); 22 23 for (; bit < 48; bit = get_c()) 24 if (bit == ‘-‘)neg ^= true; 25 26 for (; bit > 47; bit = get_c()) 27 ret = ret * 10 + bit - 48; 28 29 return neg ? -ret : ret; 30 } 31 32 const int maxn = 1e5 + 5; 33 34 int n, m; 35 int total; 36 int num[maxn]; 37 int map[maxn]; 38 39 struct Query 40 { 41 int k, l, r; 42 }qry[maxn]; 43 44 int pos; 45 46 struct Node 47 { 48 int sum; 49 int tag; 50 int lt, rt; 51 }tree[maxn << 2]; 52 53 #define lson(t) (t << 1) 54 #define rson(r) (t << 1 | 1) 55 56 void build(int t, int l, int r, int k) 57 { 58 tree[t].lt = l; 59 tree[t].rt = r; 60 tree[t].tag = -1; 61 62 if (l == r) 63 tree[t].sum = num[l] > k; 64 else 65 { 66 int mid = (l + r) >> 1; 67 build(lson(t), l, mid, k); 68 build(rson(t), mid + 1, r, k); 69 tree[t].sum = tree[lson(t)].sum + tree[rson(t)].sum; 70 } 71 } 72 73 void change(int t, int l, int r, int k) 74 { 75 if (l > r)return; 76 77 if (l == tree[t].lt && r == tree[t].rt) 78 tree[t].sum = (r - l + 1) * k, tree[t].tag = k; 79 else 80 { 81 int mid = (tree[t].lt + tree[t].rt) >> 1; 82 83 if (tree[t].tag != -1) 84 { 85 change(lson(t), tree[t].lt, mid, tree[t].tag); 86 change(rson(t), mid + 1, tree[t].rt, tree[t].tag); 87 tree[t].tag = -1; 88 } 89 90 if (r <= mid) 91 change(lson(t), l, r, k); 92 else if (l > mid) 93 change(rson(t), l, r, k); 94 else 95 change(lson(t), l, mid, k), change(rson(t), mid + 1, r, k); 96 97 tree[t].sum = tree[lson(t)].sum + tree[rson(t)].sum; 98 } 99 }100 101 int query(int t, int l, int r)102 {103 if (l == tree[t].lt && r == tree[t].rt)104 return tree[t].sum;105 106 int mid = (tree[t].lt + tree[t].rt) >> 1;107 108 if (tree[t].tag != -1)109 {110 change(lson(t), tree[t].lt, mid, tree[t].tag);111 change(rson(t), mid + 1, tree[t].rt, tree[t].tag);112 tree[t].tag = -1;113 }114 115 if (r <= mid)116 return query(lson(t), l, r);117 else if (l > mid)118 return query(rson(t), l, r);119 else120 return query(lson(t), l, mid) + query(rson(t), mid + 1, r);121 }122 123 inline bool check(int mid)124 {125 build(1, 1, n, mid);126 127 for (int i = 1; i <= m; ++i)128 {129 int q = query(1, qry[i].l, qry[i].r);130 131 if (qry[i].k)132 {133 change(1, qry[i].l, qry[i].l + q - 1, 1);134 change(1, qry[i].l + q, qry[i].r, 0);135 }136 else137 {138 change(1, qry[i].l, qry[i].r - q, 0);139 change(1, qry[i].r - q + 1, qry[i].r, 1);140 }141 }142 143 return query(1, pos, pos);144 }145 146 signed main(void)147 {148 n = get_i();149 m = get_i();150 151 for (int i = 1; i <= n; ++i)152 num[i] = get_i();153 154 for (int i = 1; i <= m; ++i)155 {156 qry[i].k = get_i();157 qry[i].l = get_i();158 qry[i].r = get_i();159 }160 161 pos = get_i();162 163 memcpy(map, num, sizeof(map));164 std::sort(map + 1, map + 1 + n);165 total = std::unique(map + 1, map + 1 + n) - map;166 167 int lt = 1, rt = total, mid, ans;168 169 while (lt <= rt)170 {171 if (check(mid = (lt + rt) >> 1))172 lt = mid + 1;173 else174 rt = mid - 1, ans = mid;175 }176 177 printf("%d\n", map[ans]);178 }
@Author: YouSiki
BZOJ 4552: [Tjoi2016&Heoi2016]排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。