[TJOI2016]排序——[线段树]

【题意分析】

首先，暴力sort有30pts…

全排列是一个特别好的性质，我们想想有没有特别的做法。

由于数字保证不重复，对于x，把大于等于x的数全部变为1，把小于x的数全部变成0。

那么我们可以发现：对于要排序的区间[l,r]，如果是升序，那么区间前面肯定是若干个零，后面全是1，如果是降序，那么区间前面全都是1， 后面全都是0。

然后这样操作之后我们看看要求的q位置上数字是否为1，就可以初步确定排完后这个位置上的数比x大还是比x小。（1是比x大，0是比x小）

想到什么？二分这个x，二分到最后无法再放缩时，说明我们已经找到了答案。

现在唯一的问题就是排序，由于序列全是0和1，我们可以考虑用线段树维护：利用线段树可以求出每段区间有几个0与几个1（区间求和就可以算出几个1），排序时，只要一段一段地赋值即可。

具体操作：对于区间$[l,r]$有res个1，那么如果是降序，$[l,l+res-1]$为1,$[l+res,r]$为0. 如果是升序，$[l,r-res]$为0，$[r-res+1,r]$为1

Code :

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> #define MAXN 200000 using namespace std; struct Node { int opt, l, r; }ques[MAXN]; int tree[MAXN << 2], lazy[MAXN << 2], a[MAXN], b[MAXN], n, q, res, pos, ans; inline int read () { register int s = 0, w = 1; register char ch = getchar (); while (! isdigit (ch)) {if (ch == '-') w = -1; ch = getchar ();} while (isdigit (ch)) {s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar ();} return s * w; } inline void pushup (int now) { tree[now] = tree[now << 1] + tree[now << 1 | 1]; } inline void pushdown (int now, int L, int R) { int mid = L + R >> 1; tree[now << 1] = lazy[now] * (mid - L + 1); tree[now << 1 | 1] = lazy[now] * (R - mid); lazy[now << 1] = lazy[now]; lazy[now << 1 | 1] = lazy[now]; lazy[now] = -1; } void build (int now, int l, int r) { lazy[now] = -1; if (l == r) {tree[now] = b[l]; return;} int mid = l + r >> 1; build (now << 1, l, mid); build (now << 1 | 1, mid + 1, r); pushup (now); } void update (int now, int l, int r, int L, int R, int k) { if (R < l || r < L) return; if (L <= l && r <= R) {tree[now] = (r - l + 1) * k, lazy[now] = k; return;} if (lazy[now] != -1) pushdown (now, l, r); int mid = l + r >> 1; update (now << 1, l, mid, L, R, k); update (now << 1 | 1, mid + 1, r, L, R, k); pushup (now); } void query (int now, int l, int r, int L, int R) { if (R < l || r < L) return; if (L <= l && r <= R) {res += tree[now]; return;} if (lazy[now] != -1) pushdown (now, l, r); int mid = l + r >> 1; query (now << 1, l, mid, L, R); query (now << 1 | 1, mid + 1, r, L, R); } inline bool check (int x) { for (register int i = 1; i <= n; i++) b[i] = (a[i] >= x); memset (tree, 0, sizeof tree), build (1, 1, n); query (1, 1, n, 1, 1); for (register int i = 1; i <= q; i++) { res = 0, query (1, 1, n, ques[i].l, ques[i].r); if (ques[i].opt == 0) { update (1, 1, n, ques[i].l, ques[i].r - res, 0); update (1, 1, n, ques[i].r - res + 1, ques[i].r, 1); } else { update (1, 1, n, ques[i].l, ques[i].l + res - 1, 1); update (1, 1, n, ques[i].l + res, ques[i].r, 0); } } res = 0, query (1, 1, n, pos, pos); return res; } int main () { n = read (), q = read (); for (register int i = 1; i <= n; i++) a[i] = read (); for (register int i = 1; i <= q; i++) ques[i].opt = read (), ques[i].l = read (), ques[i].r = read (); pos = read (); int L = 1, R = n; while (L <= R) { int mid = L + R >> 1; if (check (mid)) ans = mid, L = mid + 1; else R = mid - 1; } return printf ("%d\n", ans), 0; }