【線分樹】HDOJ 5338 ZZX and Permutations

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define lson o << 1, L, mid
#define rson o << 1 | 1, mid+1, R
#define ls o << 1
#define rs o << 1 | 1
#define mp(x, y) make_pair(x, y)

const int maxn = 100005;

set<int> s, ss;
set<int>::iterator it;
int maxv[maxn << 2];
int List[maxn];
int pos[maxn];
int res[maxn];
int cir[maxn];
int a[maxn];
int n;

void pushup(int o)
{
	maxv[o] = max(maxv[ls], maxv[rs]);
}

void build(int o, int L, int R)
{
	if(L == R) {
		maxv[o] = a[L];
		return;
	}
	int mid = (L + R) >> 1;
	build(lson);
	build(rson);
	pushup(o);
}

void update(int o, int L, int R, int q)
{
	if(L == R) {
		maxv[o] = -1;
		return;
	}
	int mid = (L + R) >> 1;
	if(q <= mid) update(lson, q);
	else update(rson, q);
	pushup(o);
}

int query(int o, int L, int R, int ql, int qr)
{
	if(ql <= L && qr >= R) return maxv[o];
	int mid = (L + R) >> 1, ans = -1;
	if(ql <= mid) ans = max(ans, query(lson, ql, qr));
	if(qr > mid) ans = max(ans, query(rson, ql, qr));
	return ans;
}

void work()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		pos[a[i]] = i;
	}
	build(1, 1, n);
	s.clear();
	ss.clear();

	s.insert(0);
	for(int i = 1; i <= n; i++) ss.insert(i);
	int cnt = 0;
	
	memset(cir, 0, sizeof cir);
	memset(List, 0, sizeof List);
	List[n+1] = cir[n+1] = -1;
	while(cnt < n) {
		int u = *ss.begin();
		ss.erase(u);
		cnt++;

		int loc = pos[u];
		int t2 = cir[loc+1] ? -1 : a[loc+1];
		it = --s.upper_bound(loc);
		int t1 = query(1, 1, n, (*it) + 1, loc);

		if(t1 > t2) {
			int loc2 = pos[t1];
			List[loc] = loc2;
			update(1, 1, n, loc2);
			for(int i = loc2; i <= loc; i++) {
				if(List[i]) continue;
				List[i] = i+1;
				ss.erase(a[i]);
				cnt++;
				update(1, 1, n, i+1);
			}
			cir[loc2] = cir[loc] = 1;
			s.insert(loc);
		}
		else {
			List[loc] = loc + 1;
			update(1, 1, n, loc+1);
		}
	}
	for(int i = 1; i <= n; i++) res[a[i]] = a[List[i]];
	for(int i = 1; i <= n; i++) printf("%d%c", res[i], i == n ? '
' : ' ');
}

int main()
{
	int _;
	scanf("%d", &_);
	while(_--) work();
	
	return 0;
}