Description

给定一个长度为 \(n\) 的排列，有 \(m\) 次操作，每次选取一段局部进行升序或降序排序，问你一波操作后某个位置上的数字是几

Hint

\(1~\leq~n,~m~\leq~10^5\)

Solution

有两种做法，一种在线一种离线，这里把在线部分讲得更清楚点吧……

考虑离线算法，我们二分该位置上的答案，将大于该数的元素置为 \(1\)，小于该数的元素置为 \(0\)，然后模拟所有的排序并检验。由于使用线段树对 \(0/1\) 序列多次局部排序可以做到 \(O(m~\log n~+~n)\) 的复杂度，所以总复杂度为 \(O(m~\log^2 n)\)。

具体排序的做法为使用线段树维护当前区间有多少个 \(1\)，不妨设为 \(x\) 个。如果对该区间升序排序，则将后面 \(x\) 个数置为 \(1\)，剩下的置为 \(0\)，否则将前面 \(x\) 个数置为 \(1\)，其余置为 \(0\)。于是一次操作的复杂度为 \(O(\log n)\)，于是进行 \(m\) 次操作的复杂度为 \(O(m~\log n)\)。

考虑在线做。发现对于任意的时刻我们都有一些区间是排好序的。那么现在我们的问题是每次排序操作后合并被排序操作覆盖的区间。考虑到对于两个序列的按序合并可以使用权值线段树轻松做到，我们对每个排好序的区间分别维护一棵权值线段树。然后用一个 set 维护这些区间。对于被该排序操作完全覆盖的区间，我们可以直接进行线段树合并，而对于区间两侧的被覆盖了一部分的两个区间，可以先分裂成被完全覆盖的区间和完全不被覆盖的区间再进行合并。例如被排序的区间是 \([l,~r]\)，左侧被覆盖了一部分的区间为 \([l_0,~y_0]\)，其中 \(l_0~<~l~<~r_0\)，那么将区间 \([l_0,~r_0]\) 拆分成 \([l_0,~l - 1]~\bigcap~[l,~r_0]\) 两个区间，然后对 \([l,~r_0]\) 与其他被完全覆盖的区间进行合并即可。

考虑复杂度分析：

如果不考虑线段树分裂操作，我们对区间的操作实质上是将很多的小区间合并成至少一个大区间。考虑到对 \(n\) 个长度为 \(1\) 的小区间全部合并成一个大区间的复杂度为 \(O(n~\log n)\)，于是 merge 部分的的总复杂度为 \(O(n~\log n)\)。考虑分裂，一次排序操作后会分裂出 \(O(1)\) 个新区间，于是 \(m\) 次操作后会分裂出 \(O(m)\) 个新区间，合并这 \(O(m)\) 个区间的复杂度仍为 \(O(m~\log n)\)，考虑到每次分裂是严格 \(O(\log n)\) 的，且会进行 \(O(m)\) 次排序，所以分裂操作对复杂度的总贡献仍是 \(O(m~\log n)\)。于是总复杂度为 \(O((n+m)~\log n)\)。比上面的离线算法更优秀。同时这个算法可以解决查询任意多个位置上的数字，而不是仅仅一个。

Code

在分裂区间的时候有很多小细节需要注意……另外下面的代码存在一定的内存泄漏问题，不过总共被泄露的内存是 \(O((n+m)~\log n)\) 级别的，对空间复杂度不产生影响，是可以接受的。

其实是我不知道为什么回收空间会莫名其妙 RE

#include 
    
     #include 
     
      #include 
      
       #ifdef ONLINE_JUDGE#define freopen(a, b, c)#endiftypedef long long int ll;namespace IPT {    const int L = 1000000;    char buf[L], *front=buf, *end=buf;    char GetChar() {        if (front == end) {            end = buf + fread(front = buf, 1, L, stdin);            if (front == end) return -1;        }        return *(front++);    }}template 
       
        inline void qr(T &x) {    char ch = IPT::GetChar(), lst = ' ';    while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();    while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();    if (lst == '-') x = -x;}namespace OPT {    char buf[120];}template 
        
         inline void qw(T x, const char aft, const bool pt) {    if (x < 0) {x = -x, putchar('-');}    int top=0;    do {OPT::buf[++top] = static_cast
         
          (x % 10 + '0');} while (x /= 10); while (top) putchar(OPT::buf[top--]); if (pt) putchar(aft);}const int maxn = 100010;struct Tree { Tree *ls, *rs; int l, r, v; Tree() { ls = rs = NULL; l = r = v = 0; } inline void pushup() {if (this->l != this->r) this->v = (this->ls ? this->ls->v : 0) + (this->rs ? this->rs->v : 0); else this->v = 1;}};struct OP { int l, r; bool up; Tree *rot; inline bool operator<(const OP &_others) const { return this->r < _others.r; } OP(int _l = 0, int _r = 0, bool _up = 0, Tree *_rot = 0) { l = _l; r = _r; up = _up; rot = _rot; }};OP temp;std::set
          
           s;int n, m;int MU[maxn];void split(int, bool);void insert(Tree*, int, int, int);void split(Tree*, Tree*, Tree*, int);Tree* merge(Tree*, Tree*);int query(Tree*, int);int main() { freopen("data.in", "r", stdin); freopen("my.out", "w", stdout); qr(n); qr(m); for (int i = 1; i <= n; ++i) { auto _rot = new Tree; qr(MU[i]); insert(_rot, 1, n, MU[i]); s.insert(OP(i, i, true, _rot)); } for (int j = 1, a, b, c; j <= m; ++j) { a = b = c = 0; qr(a); qr(b); qr(c); split(b, true); split(c + 1, false); auto l = s.lower_bound({0, b, true, NULL}), r = s.lower_bound({0, c + 1, true, NULL}); auto _tmp = *l; for (auto i = s.erase(l); i != r; i = s.erase(i)) { _tmp.rot = merge(_tmp.rot, (*i).rot); } _tmp.l = b; _tmp.r = c; _tmp.up = !a; s.insert(_tmp); } int q = 0; qr(q); auto _ans = s.lower_bound({0, q, true, NULL}); auto ans = *_ans; int k = ans.up ? q - ans.l + 1 : ans.r - q + 1; qw(query(ans.rot, k), '\n', true); return 0;}int query(Tree *u, int k) { if (u->l == u->r) return u->l; if (!u->ls) return query(u->rs, k); if (u->ls->v >= k) return query(u->ls, k); return query(u->rs, k - u->ls->v);}Tree* merge(Tree *u, Tree *v) { if (!u) return v; else if (!v) return u; u->v += v->v; u->ls = merge(u->ls, v->ls); u->rs = merge(u->rs, v->rs); return u;}void insert(Tree *u, int l, int r, int v) { ++u->v; if ((u->l = l) == (u->r = r)) return; int mid = (l + r) >> 1; if (v <= mid) insert(u->ls = new Tree, l, mid, v); else insert(u->rs = new Tree, mid + 1, r, v);}void split(int x, bool isfront) { auto k = s.lower_bound({0, x, true, NULL}); if (k == s.end()) return; auto t = *k; if (t.l == x) return; s.erase(k); int _k = (isfront ? t.r - x + 1: x - t.l), len = t.r - t.l + 1; if (t.up == isfront) { Tree *_rot = new Tree; _k = len - _k; if (!_k) { s.insert(t); return; } split(t.rot, t.rot, _rot, _k); if (!t.up) { _k = len - _k; std::swap(_rot, t.rot); } s.insert({t.l, t.l + _k - 1, t.up, t.rot}); s.insert({t.l + _k, t.r, t.up, _rot}); } else { Tree *_rot = new Tree; if (!_k) { s.insert(t); return; } split(t.rot, t.rot, _rot, _k); if (!t.up) { std::swap(t.rot, _rot); _k = len -_k; } s.insert({t.l, t.l + _k - 1, t.up, t.rot}); s.insert({t.l + _k, t.r, t.up, _rot}); }}void split(Tree *u, Tree *l, Tree *r, int k) { l->l = r->l = u->l; r->r = l->r = u->r; if (!u->ls) split(u->rs, l->rs ? l->rs : l->rs = new Tree, r->rs ? r->rs : r->rs = new Tree, k); else if (k == u->ls->v) { l->ls = u->ls; r->rs = u->rs; l->rs = NULL; r->ls = NULL; } else if (k < u->ls->v) { split(u->ls, l->ls ? l->ls : l->ls = new Tree, r->ls ? r->ls : r->ls = new Tree, k); r->rs = u->rs; l->rs = NULL; } else { split(u->rs, l->rs ? l->rs : l->rs = new Tree, r->rs ? r->rs : r->rs = new Tree, k - u->ls->v); l->ls = u->ls; r->ls = NULL; } l->pushup(); r->pushup();}
          
         
        
       
      
     
    

Summary

1、将 \(n\) 个长度为 \(1\) 的小区间合并为一个大区间的复杂度为 \(O(n~\log n)\)，理由是这样的开销显然不大于将这些区间顺次插入一棵线段树。

2、合并两个有序序列可以使用合并权值线段树来做到均摊复杂度 \(O(\log n)\)。