P2824 [HEOI2016/TJOI2016] 排序

P2824 [HEOI2016/TJOI2016] 排序

[HEOI2016/TJOI2016] 排序

题目描述

在 $2016$ 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。

这个难题是这样子的：给出一个 $1$ 到 $n$ 的排列，现在对这个排列序列进行 $m$ 次局部排序，排序分为两种：

• 0 l r 表示将区间 $[l,r]$ 的数字升序排序
• 1 l r 表示将区间 $[l,r]$ 的数字降序排序

注意，这里是对下标在区间 $[l,r]$ 内的数排序。
最后询问第 $q$ 位置上的数字。

输入格式

输入数据的第一行为两个整数 $n$ 和 $m$，$n$ 表示序列的长度，$m$ 表示局部排序的次数。

第二行为 $n$ 个整数，表示 $1$ 到 $n$ 的一个排列。

接下来输入 $m$ 行，每一行有三个整数 $\text{op},l,r$，$\text{op}$ 为 $0$ 代表升序排序，$\text{op}$ 为 $1$ 代表降序排序, $l,r$ 表示排序的区间。

最后输入一个整数 $q$，表示排序完之后询问的位置

输出格式

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第 $q$ 位置上的数字。

样例 #1

样例输入 #1

6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
1
2
3
4
5
6

样例输出 #1

5
1

提示

河北省选2016第一天第二题。

对于 $30\%$ 的数据，$n,m\le 1000$

对于 $100\%$ 的数据，$n,m\le 10^5$，$1\le q\le n$

解析：

排序的时间复杂度为 $O(nlogn)$，总的时间复杂度为 $O(nmlogm)$ ，会超时。

对于 01序列 的排序（以升序为例）可以简化排序的过程：

• 将前部分置 0，将后部分置 1

01序列 的排序实际上是去区间查询，区间修改：

• 查询 $[l,r]$ 区间中 $1$ 的个数为 $cn{t}_1$
• 将区间 $[r-cn{t}_1+1,r]$ 置 1，将区间 $[l,r-cn{t}_1]$ 置 0

接下来考虑如何将序列转化为 01序列：

对于猜测答案 $x$，将序列中小于 $x$ 的数置 0，大于等于 $x$ 的数置 1，即可得到 01序列

答案是否具有单调性：

对 01序列 进行局部排序操作，然后查询 $q$ 位置的数：

• 如果为1，则说明正确答案大于等于 $x$
• 如果为0，则说明正确答案小于 $x$

因此具有单调性，所以可以二分答案。

总的时间复杂度为 $O(mlo{g}^{2}n)$

代码中需要注意的是：

• 特判一下 全0/全1 的排序
• 每次二分检查的时候，需要将线段树清空，尤其是 lazytag，不要只清零叶子节点的 lazytag（悲）

代码：

#include
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

inline int ls(int x){return x << 1;}
inline int rs(int x){return x << 1 | 1;}
struct Query{
	int op, l, r;
}q[maxn];
struct node{
	int sum; // 1 的个数 
	int tag;
}t[maxn << 2];
int n, m, p;
int a[maxn], b[maxn];

void init(int x){
	for(int i = 1; i <= n; i++){
		if(a[i] < x)
			b[i] = 0;
		else
			b[i] = 1;
	}
}
void pushup(int k){
	t[k].sum = t[ls(k)].sum + t[rs(k)].sum;
}
void build(int k, int l, int r){
	t[k].tag = 0;
	if(l == r){
		t[k].sum = b[l];		
		return;
	}
	int mid = (l+r) >> 1;
	build(ls(k), l, mid);
	build(rs(k), mid+1, r);
	pushup(k);
}

// tag = 0 : 无事发生
// tag = 1 : 全为 0
// tag = 2 : 全为 1
void pushdown(int k, int l, int r){
	if(t[k].tag == 0)
		return;
		
	if(t[k].tag == 1){
		t[ls(k)].sum = 0;
		t[rs(k)].sum = 0;
	}
	else if(t[k].tag == 2){
		int mid = (l+r) >> 1;
		t[ls(k)].sum = mid - l + 1;
		t[rs(k)].sum = r - mid;
	}
	t[ls(k)].tag = t[rs(k)].tag = t[k].tag;
	t[k].tag = 0; 
}
void modify(int k, int l, int r, int x, int y, int v){
	if(x <= l && y >= r){
		t[k].tag = v;
		if(v == 1) t[k].sum = 0;
		if(v == 2) t[k].sum = r-l+1;
		return;
	}
	pushdown(k, l, r);
	int mid = (l+r) >> 1;
	if(x <= mid)
		modify(ls(k), l, mid, x, y, v);
	if(y > mid)
		modify(rs(k), mid+1, r, x, y, v);
	pushup(k);
}
int querycnt1(int k, int l, int r, int x, int y){
	if(x <= l && y >= r)
		return t[k].sum;
	int mid = (l+r) >> 1;
	pushdown(k, l, r);
	int res = 0;
	if(x <= mid)
		res += querycnt1(ls(k), l, mid, x, y);
	if(y > mid)
		res += querycnt1(rs(k), mid+1, r, x, y);
	return res;
}
int querypos(int k, int l, int r, int pos){
	if(l == r && l == pos)
		return t[k].sum;
	pushdown(k, l, r);
	int mid = (l+r) >> 1;
	int res;
	if(pos <= mid)
		res = querypos(ls(k), l, mid, pos);
	else
		res = querypos(rs(k), mid+1, r, pos);
	return res;
}
bool check(int x){
	init(x);
	build(1, 1, n);
	for(int i = 1; i <= m; i++){
		int cnt1 = querycnt1(1, 1, n, q[i].l, q[i].r); 
		if(cnt1 == 0 || cnt1 == (q[i].r - q[i].l + 1))
			continue;
		if(q[i].op == 0){ // 升序 
			modify(1, 1, n, q[i].l, q[i].r-cnt1, 1);
			modify(1, 1, n, q[i].r-cnt1+1, q[i].r, 2);
		}
		else if(q[i].op == 1){ // 降序 
			modify(1, 1, n, q[i].l+cnt1, q[i].r, 1);
			modify(1, 1, n, q[i].l, cnt1+q[i].l-1, 2);			 
		}
	}
	int res = querypos(1, 1, n, p);
	return res == 1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= m; i++)
		cin >> q[i].op >> q[i].l >> q[i].r;
	cin >> p; 
	int l = 1, r = n, res;
	while(l <= r){
		int mid = (l+r) >> 1;
		if(check(mid)){
			res = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	cout << res << endl;
	return 0;
}

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