DHUOJ 2017121906&&BZOJ 4552 排序

Posted on | In ,

思路

DHU数据结构期末考题，来源bzoj4552[Tjoi2016&Heoi2016]。非常好的一道线段树的题目，让我看到了自己对二分，线段树的理解尚浅。
本题的思路是二分处于q位置上的数字，然后将原数列转换成01序列（比他大置1，反之置0）。对于一个01序列，按递增排序相当于把后半部分置1，前半部分置0（线段树区间更新）。递减思路类似。最后我们check返回q位置上的值。

代码

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
#include <bits/stdc++.h>
#define ll long long
#define INF 0x7fffffff
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
#define ms(a,val) memset((a),(val),(sizeof(a)))

using namespace std;

const int MAXN = 100005, MAXM = 100005;
int n, m, q, a[MAXN], b[MAXN];
struct node {
	int l, r, val, lazy;
	node() {};
	node(int l, int r, int val) :l(l), r(r), val(val) { lazy = -1; };
}tree[MAXN * 4];
struct ask {
	int oper, l, r;
	ask() {};
	ask(int oper, int l, int r) :oper(oper), l(l), r(r) {};
}as[MAXM];
void push_up(int root) {
	tree[root].val = tree[lson(root)].val + tree[rson(root)].val;
}
void push_down(int root) {
	if (tree[root].lazy<0)return;
	tree[lson(root)].val = (tree[lson(root)].r - tree[lson(root)].l + 1)*tree[root].lazy, tree[lson(root)].lazy = tree[root].lazy;
	tree[rson(root)].val = (tree[rson(root)].r - tree[rson(root)].l + 1)*tree[root].lazy, tree[rson(root)].lazy = tree[root].lazy;
	tree[root].lazy = -1;
}
void buildtree(int l, int r, int root) {
	tree[root].l = l, tree[root].r = r,tree[root].lazy=-1;
	if (l == r)tree[root].val=b[l];
	else {
		int mid = (l + r) / 2;
		buildtree(l, mid, lson(root));
		buildtree(mid + 1, r, rson(root));
		push_up(root);
	}
}
void change(int l, int r, int oper, int root) {
	if (l <= tree[root].l&&r >= tree[root].r) {
		tree[root].lazy = oper;
		tree[root].val = (tree[root].r - tree[root].l + 1)*oper;
	}
	else {
		int mid = (tree[root].l + tree[root].r) >> 1;
		push_down(root);
		if (l <= mid)change(l, r, oper, lson(root));
		if (mid<r)change(l, r, oper, rson(root));
		push_up(root);
	}
}
int query(int l, int r, int root) {
	if (l <= tree[root].l&&tree[root].r <= r)return tree[root].val;
	push_down(root);
	int mid = (tree[root].l + tree[root].r) >> 1, res = 0;
	if (l <= mid)res += query(l, r, lson(root));
	if (mid<r)res += query(l, r, rson(root));
	return res;
}
bool check(int x) {
	for (int i = 1;i <= n;i++) {
		if (a[i]>x)b[i] = 1;
		else b[i] = 0;
	}
	buildtree(1, n, 1);
	for (int i = 1;i <= m;i++) {
		int sum = query(as[i].l, as[i].r, 1);
		if (as[i].oper == 0) {
			if (as[i].r - sum >= as[i].l)change(as[i].l, as[i].r - sum, 0, 1);
			if (sum)change(as[i].r - sum + 1, as[i].r, 1, 1);
		}
		else {
			if (sum)change(as[i].l, as[i].l + sum - 1, 1, 1);
			if (as[i].r >= as[i].l + sum)change(as[i].l + sum, as[i].r, 0, 1);
		}
	}
	return query(q, q, 1);
}
int main() {
	while (~scanf("%d%d", &n, &m)) {
		for (int i = 1;i <= n;i++)scanf("%d", &a[i]);
		for (int i = 1;i <= m;i++)scanf("%d%d%d", &as[i].oper, &as[i].l, &as[i].r);
		scanf("%d", &q);
		int l = 1, r = n;
		while (l<r) {
			int mid = (l + r) >> 1;
			if (check(mid))l = mid + 1;
			else r = mid;
		}
		printf("%d\n", l);
	}
	return 0;
}