排序

代码

/*
* Try to have as good a life as you can under the circumstances.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>

static int const N = 100005;
static int const NM = 5000000;
int rt[N], top, buf[NM];
struct Interval {
int l, r, ord;
bool operator<(Interval const &a) const { return l < a.l; }
};
std::set<Interval> st;
struct SegmentTree {
int ch[2], val, sum;
} nd[NM];

void update(int rt) {
nd[rt].sum = nd[nd[rt].ch[0]].sum + nd[rt].val + nd[nd[rt].ch[1]].sum;
}

void insert(int &rt, int nl, int nr, int p) {
if (!rt)
nd[rt = buf[--top]] = nd[0];
if (nl == nr) {
nd[rt].val = nd[rt].sum = 1;
return;
}
int mid = nl + nr >> 1;
if (p <= mid)
insert(nd[rt].ch[0], nl, mid, p);
else
insert(nd[rt].ch[1], mid + 1, nr, p);
update(rt);
}

void merge(int &p, int &q) {
if (!p || !q) {
p = p + q, q = 0;
return;
}
merge(nd[p].ch[0], nd[q].ch[0]), merge(nd[p].ch[1], nd[q].ch[1]);
buf[top++] = q, q = 0, update(p);
}

int split(int &rt, int k) {
if (!rt || nd[rt].sum == k)
return 0;
if (!k) {
int rec = rt;
return rt = 0, rec;
}
if (nd[nd[rt].ch[0]].sum >= k) {
int sp = buf[--top];
nd[sp].ch[0] = split(nd[rt].ch[0], k), nd[sp].ch[1] = nd[rt].ch[1],
nd[rt].ch[1] = 0;
return update(rt), update(sp), sp;
}
int sp = buf[--top];
nd[sp].ch[0] = 0,
nd[sp].ch[1] = split(nd[rt].ch[1], k - nd[nd[rt].ch[0]].sum);
return update(rt), update(sp), sp;
}

int query(int rt, int nl, int nr, int k) {
if (nl == nr)
return nl;
int mid = nl + nr >> 1;
if (nd[nd[rt].ch[0]].sum >= k)
return query(nd[rt].ch[0], nl, mid, k);
else
return query(nd[rt].ch[1], mid + 1, nr, k - nd[nd[rt].ch[0]].sum);
}

int main() {
for (int i = 1; i < NM; ++i)
buf[top++] = i;
int n, m, q;
scanf("%d%d", &n, &m);
for (int i = 1, t; i <= n; ++i)
scanf("%d", &t), insert(rt[i], 1, n, t), st.insert((Interval){i, i, 0});
for (; m--;) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
std::set<Interval>::iterator L = st.upper_bound((Interval){l}),
R = st.upper_bound((Interval){r});
Interval recl = *(--L), recr = *(--R);
if (L->l < l)
if (L->ord == 0)
rt[l] = split(rt[L->l], l - L->l);
else
rt[l] = split(rt[L->l], L->r - l + 1), std::swap(rt[l], rt[L->l]);
if (L != R) {
st.erase(L++);
for (; L != R; st.erase(L++))
merge(rt[l], rt[L->l]);
if (r < R->r)
if (R->ord == 0)
rt[r + 1] = split(rt[R->l], r - R->l + 1);
else
rt[r + 1] = split(rt[R->l], R->r - r), std::swap(rt[r + 1], rt[R->l]);
merge(rt[l], rt[R->l]);
} else if (r < R->r)
if (R->ord == 0)
rt[r + 1] = split(rt[l], r - l + 1);
else
rt[r + 1] = split(rt[l], R->r - r), std::swap(rt[r + 1], rt[l]);
st.erase(R), st.insert((Interval){l, r, op});
if (recl.l < l)
st.insert((Interval){recl.l, l - 1, recl.ord});
if (r < recr.r)
st.insert((Interval){r + 1, recr.r, recr.ord});
}
scanf("%d", &q);
for (std::set<Interval>::iterator it = st.begin(); it != st.end(); ++it)
if (q <= nd[rt[it->l]].sum) {
if (it->ord == 0)
printf("%d\n", query(rt[it->l], 1, n, q));
else
printf("%d\n", query(rt[it->l], 1, n, nd[rt[it->l]].sum - q + 1));
break;
} else
q -= nd[rt[it->l]].sum;
return 0;
}


418 I'm a teapot