BZOJ4552 排序

发表于

  题意:一个1-n的全排列，进行m次局部排序(选定一个区间，升序或降序排序)，最后求第q位置上数字。

  这道题有个咸鱼做法:二分数字，转化为01序列然后就很好办了。但是这样时间要多一个log而且不支持在线。
  而如果使用线段树合并的话，就可以不用最后求，而是随时求q位置数字了。
  对每个操作区间建立一棵权值线段树，并且记录当前顺序是升序还是降序，操作一个区间时，先找到包含该区间一部分的权值线段树，将两端多出去的地方割裂(要用到线段树分裂)，然后一个个合并起来。对于每个区间的开头我们用一个set存储，这样可以实现快速插入删除区间。
  注意分裂的时候没有下传l与r端点，所以k值等于左儿子size的时候就不要下传了，以免陷入死循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <ctime>
#include <set>
#include <vector>
 
using namespace std;
 
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define ms(a, b) memset(a, b, sizeof a)
#define pb push_back
#define SZ(x) (int((x).size()))
 
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
    if(flag) x = -x; return x;
}
const int maxn = 100010;
int n, m, a[maxn];
set<int> S;
set<int>::iterator it;
int tp[maxn], End[maxn];
namespace SGT
{
#define mid ((l + r) >> 1)
#define lc l, mid
#define rc mid + 1, r
    struct node
    {
        int ls, rs;
        int sz;
		node(): ls(0), rs(0), sz(0) { }
    }T[maxn * 18 * 3];
    int rt[maxn], cur;
    void pushup(int h) { T[h].sz = T[T[h].ls].sz + T[T[h].rs].sz; }
    void update(int& h, int l, int r, int x)
    {
        if(!h) h = ++cur;
        if(l == r) { ++T[h].sz; return; }
        if(x <= mid) update(T[h].ls, lc, x);
        else update(T[h].rs, rc, x);
        pushup(h);
    }
    
    void split(int h1, int& h2, int k)
	{
		h2 = ++cur;
		if(k > T[T[h1].ls].sz) split(T[h1].rs, T[h2].rs, k - T[T[h1].ls].sz);
		else
		{
			swap(T[h1].rs, T[h2].rs);
			if(k < T[T[h1].ls].sz) split(T[h1].ls, T[h2].ls, k);
		}
		T[h2].sz = T[h1].sz - k; T[h1].sz = k;
	}
	void merge(int& h1, int h2)
	{
		if(!h2) return;
		if(!h1) { h1 = h2; return; }
		merge(T[h1].ls, T[h2].ls);
		merge(T[h1].rs, T[h2].rs);
		pushup(h1);
	}
	int query(int h, int l, int r, int k)
	{
		if(l == r) return l;
		if(k > T[T[h].ls].sz) return query(T[h].rs, rc, k - T[T[h].ls].sz);
		else return query(T[h].ls, lc, k);
	}
}
using namespace SGT;
void Split(int x, int pos)
{
    if(pos >= End[x] || pos < x) return;
    if(!tp[x]) split(rt[x], rt[pos + 1], pos - x + 1);
    else
    {
        rt[pos + 1] = rt[x];
        split(rt[pos + 1], rt[x], End[x] - pos);
    }
    End[pos + 1] = End[x]; End[x] = pos;
    S.insert(pos + 1); tp[pos + 1] = tp[x];
}
void Merge(int x, int y)
{
	S.erase(y);
	merge(rt[x], rt[y]);
	End[x] = End[y];
}
int Query(int x, int k)
{
	k -= x - 1;
	if(!tp[x]) return query(rt[x], 1, n, k);
	else return query(rt[x], 1, n, (End[x] - x + 1) - k + 1);
}
vector<int> tmp;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
    read(n); read(m);
    rep(i, 1, n)
    {
        read(a[i]);
        update(rt[i], 1, n, a[i]);
        S.insert(i); End[i] = i;
    }
    while(m--)
    {
        int op, l, r;
        read(op), read(l), read(r);
        it = S.upper_bound(l); --it;
        Split(*it, l - 1);
        it = S.upper_bound(r); --it;
        Split(*it, r);
        set<int>::iterator L, R;
        L = S.lower_bound(l);
        R = S.upper_bound(r);
        if(L != R)
		{
			tmp.clear();
			for(it = L, ++it; it != R; ++it) tmp.pb(*it); 
			rep(i, 0, SZ(tmp) - 1) Merge(*L, tmp[i]);
		}
        tp[*L] = op;
    }
	int q; read(q); it = S.upper_bound(q); --it;
	printf("%d\n", Query(*it, q));
    return 0;
}