时间戳

首页 > 技术文章 > JZOJ4605. 排序（线段树合并与分裂）

JZOJ4605. 排序（线段树合并与分裂）

coldchair 2019-09-22 08:53 原文

题目大意：

每次把一个区间升序或降序排序，最后问一个点是什么。

题解：

如果只是问一个点，这确乎是个经典题，二分一下答案然后线段树维护01排序。

从pty那里get到了可以用线段树的合并与分裂实时地维护整个序列。

考虑一次排序就把这个区间的数搞到一个线段树上，在根处标记是正的还是反的。

如果想搞到一棵树上就需要用到分裂与合并，根据势能分析，复杂度还是\(O(n~log~n)\)。

Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int N = 1e5 + 5;

int n, m, a[N];
int op, l, r;

struct tree {
	int l, r, x;
} t[N * 120];
#define i0 t[i].l
#define i1 t[i].r
int tot, pl, pr, px;
int rt[N * 120], rev[N * 120];

void upd(int i) {
	t[i].x = t[i0].x + t[i1].x;
}

void add(int &i, int x, int y) {
	i = ++ tot;
	t[i].x = 1;
	if(x == y) return;
	int m = x + y >> 1;
	if(pl <= m) add(i0, x, m); else add(i1, m + 1, y);
}

void merge(int &i, int j) {
	if(!i || !j) { i = i + j; return;}
	merge(t[i].l, t[j].l);
	merge(t[i].r, t[j].r);
	upd(i);
}

void ft(int i, int x, int y) {
	if(x == y) { if(t[i].x == pl) px = x; return;}
	int m = x + y >> 1;
	if(t[i0].x >= pl) ft(i0, x, m); else
		pl -= t[i0].x, ft(i1, m + 1, y);
}

void sp(int i, int &j1, int &j2, int x, int y, int k) {
	if(!i) return;
	if(y <= k) { j1 = i, j2 = 0; return;}
	if(x > k)  { j1 = 0, j2 = i; return;} 
	int m = x + y >> 1;
	if(!j1) j1 = ++ tot;
	if(!j2) j2 = ++ tot;
	sp(i0, t[j1].l, t[j2].l, x, m, k);
	sp(i1, t[j1].r, t[j2].r, m + 1, y, k);
	upd(j1); upd(j2);
}

int bz[N];
void dg(int i, int x, int y) {
	if(!t[i].x) return;
	if(x == y) { bz[x] ++; return;}
	int m = x + y >> 1;
	dg(i0, x, m); dg(i1, m + 1, y);
}

void split(int &i, int &j, int k) {
	pl = rev[i] ? t[i].x - k : k;
	px = 0; ft(i, 0, n);
	if(rev[i]) sp(i, j, i, 0, n, px); else sp(i, i, j, 0, n, px);
}

set<int> s;
set<int> :: iterator st, en;
int d[N], d0;

int main() {
	scanf("%d %d", &n, &m);
	fo(i, 1, n) scanf("%d", &a[i]);
	fo(i, 0, n + 1) s.insert(i);
	fo(i, 0, n) pl = pr = a[i], add(rt[i], 0, n);
	fo(i, 1, m) {
		scanf("%d %d %d", &op, &l, &r);
		en = s.upper_bound(r);
		st = -- s.lower_bound(l);
		d0 = 0;
		for(; st != en; st ++) d[++ d0] = *st;
		d[++ d0] = *en;
		int rt1 = 0, rt2 = 0;
		split(rt[d[1]], rt1, l - d[1]);
		if(t[rt1].x) {
			rt[l] = rt1;
			rev[rt[l]] = rev[rt[d[1]]];
			d[1] = l;
		}
		if(d[d0] != r + 1) {
			split(rt[d[d0 - 1]], rt2, r + 1 - d[d0 - 1]);
			rt[r + 1] = rt2;
			rev[rt[r + 1]] = rev[rt[d[d0 - 1]]];
		}
		fo(j, 2, d0 - 1) {
			if(l != d[j]) merge(rt[l], rt[d[j]]), rt[d[j]] = 0;
			s.erase(d[j]);
		}
		rev[rt[l]] = op;
		s.insert(l); s.insert(r + 1);
	}
	scanf("%d", &l);
	l ++;
	for(st = s.begin(); st != s.end(); st ++) {
		int i = *st;
		if(t[rt[i]].x >= l) {
			pl = rev[rt[i]] ? t[rt[i]].x - l + 1 : l;
			px = 0;
			ft(rt[i], 0, n);
			pp("%d\n", px);
			return 0;
		} else l -= t[rt[i]].x;
	}
}

推荐阅读