【线段树 二分】洛谷 P2824 排序
2021-03-25 14:52:00 # ACM

题链

二分答案，将原数组中小于二分值的置$0$，大于等于的置$1$，则区间排序问题则可变为区间赋值问题

线段树维护区间和，记$cnt$为$[l,r]$区间的$1$的个数，区间升序排序$[l,r]$可以转为对$[r-cnt+1,r]$区间值变为$1$，$[l,r-cnt]$区间值变为$0$，区间降序同理

若所求$pos$的值为$1$，说明经过一轮排序后该点的值是大于等于二分的答案的，可知单调性

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
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
//#pragma GCC optimize("O2")
using namespace std;
using namespace __gnu_pbds;
#define Pair pair<LL,LL>
#define Combine Pair, greater<Pair>, pairing_heap_tag
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 1000009
#define INF 1e18
#define DBINF 1e100
#define Pi acos(-1.0)
#define eps 1e-9
#define mod 99999997

LL n,m;
LL mid;
LL a[MS];
struct node{
	LL op,l,r;
}cp[MS];
LL p[MS<<2];
LL la[MS<<2];

void push_up(int rt){
	p[rt] = p[ls] + p[rs];
}

void push_down(int rt,int l,int r){
	if(la[rt] != -1){
		int m = l+r>>1;
		p[ls] = (m-l+1)*la[rt];
		p[rs] = (r-m)*la[rt];
		la[ls] = la[rt];
		la[rs] = la[rt];
		la[rt] = -1;
	}
}

void build(int l,int r,int rt){
	la[rt] = -1;
	if(l == r){
		if(a[l] < mid) p[rt] = 0;
		else p[rt] = 1;
		return;
	}
	int m = l+r>>1;
	build(l,m,ls);
	build(m+1,r,rs);
	push_up(rt);
}

void update(int L,int R,int l,int r,int rt,LL val){
	if(L <= l && r <= R){
		p[rt] = (r-l+1)*val;
		la[rt] = val;
		return;
	}
	int m = l+r>>1;
	push_down(rt,l,r);
	if(m >= L) update(L,R,l,m,ls,val);
	if(m <  R) update(L,R,m+1,r,rs,val);
	push_up(rt);
}

LL get_sum(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		return p[rt];
	}
	int m = l+r>>1;
	push_down(rt,l,r);
	LL ans = 0;
	if(m >= L) ans += get_sum(L,R,l,m,ls);
	if(m <  R) ans += get_sum(L,R,m+1,r,rs);
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=1;i<=m;i++){
		cin >> cp[i].op >> cp[i].l >> cp[i].r;
	}
	LL pos,ans;
	cin >> pos;
	LL l = 1 ,r = n;
	while(l<=r){
		mid = l+r>>1;
		build(1,n,1);
		for(int i=1;i<=m;i++){
			LL cnt = get_sum(cp[i].l,cp[i].r,1,n,1);
			if(!cnt || cnt == cp[i].r-cp[i].l+1) continue;
			if(!cp[i].op){
				update(cp[i].l,cp[i].r-cnt,1,n,1,0);
				update(cp[i].r-cnt+1,cp[i].r,1,n,1,1);
			}
			else{
				update(cp[i].l,cp[i].l+cnt-1,1,n,1,1);
				update(cp[i].l+cnt,cp[i].r,1,n,1,0);
			}
		}
		LL tar = get_sum(pos,pos,1,n,1);
		if(tar) ans = mid ,l = mid+1;
		else r = mid-1;
	}
	cout << ans << endl;


	return 0;

}
Prev
2021-03-25 14:52:00 # ACM
Next