BZOJ 4552 排序

发表于 | 更新于

Link

好题，只可惜不是原创。

Solution

暴力非常好写，直接模拟，不停地sort，改一改比较的functor，然后就TLE啦！ 很明显那么做完全没有利用到只有一个询问这个条件。 考虑排序有什么意义 从单个元素看，区间[l,r][l,r]第KK小/大恰好在l+K−1l+K-1的位置(废话) 从整体的区间来看，区间[l,p−1][l,p-1]的所有数字都比a[p]a[p]小/大(废话) 第一个性质涉及到单点，似乎没有很大的价值， 相比之下，第二个性质本来就带着“区间”，似乎可以试试。 根据第二个性质，似乎套个二分答案就可以把区间的数字都变成0/10/1了？于是正解就出来了 当然作为一个juruo以上纯属看题解之后的表演

Why Can't

没有对单个数字的条件充分思考下去，而且抱着第一个性质不放，没有把思维发散出去。

Code

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
#include "lucida"
#define pass void(0)

const int MAXN=1e5+11;
namespace segtree {
	const int SIZE=MAXN<<2;
	struct Node {
		Node *son[2];
		int cnt,sz,cov;
		Node():cnt(0),sz(1),cov(-1) {}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,SIZE);
			return Me++;
		}
		void Cover(int c) {
			cnt=sz*c;
			cov=c;
		}
		void Up() {
			cnt=son[0]->cnt+son[1]->cnt;
		}
		void Down() {
			if(cov!=-1) {
				son[0]->Cover(cov);
				son[1]->Cover(cov);
				cov=-1;
			}
		}
	};
	struct SegTree {
		Node *root;int L,R;
		void Build(Node *&pos,int L,int R) {
			pos=new Node;
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid);
				Build(pos->son[1],Mid+1,R);
				pos->sz=pos->son[0]->sz+pos->son[1]->sz;
			}
		}
		int Access(Node *pos,int L,int R,const int l,const int r) {
			if(l<=L && R<=r) return pos->cnt;
			else {
				int Mid=(L+R)>>1;pos->Down();
				return (l<=Mid?Access(pos->son[0],L,Mid,l,r):0)+(Mid+1<=r?Access(pos->son[1],Mid+1,R,l,r):0); 
			}
		}
		void Edit(Node *pos,int L,int R,const int l,const int r,const int c) {
			if(l<=L && R<=r) pos->Cover(c);
			else {
				int Mid=(L+R)>>1;pos->Down();
				l<=Mid?Edit(pos->son[0],L,Mid,l,r,c):pass;
				Mid+1<=r?Edit(pos->son[1],Mid+1,R,l,r,c):pass;
				pos->Up();
			}
		}
		SegTree(int L,int R):L(L),R(R) {
			Build(root,L,R);
		}
		void Reset() {
			root->Cover(0);
		}
		int Access(int l,int r=0) {
			return l<=(r?r:l)?Access(root,L,R,l,r?r:l):0;
		}
		void Edit(int l,int r,int c) {
			l<=r?Edit(root,L,R,l,r,c):pass;
		}
		void Edit(int pos,int c) {
			Edit(root,L,R,pos,pos,c);
		}
	};
}using segtree::SegTree;
int n,m,q,a[MAXN];
struct Opt {
	int op,l,r;
}op[MAXN];
bool MaybeSmaller(int x) {
	static SegTree seg(1,n);
	seg.Reset();
	for(int i=1;i<=n;++i) {
		seg.Edit(i,x<a[i]);
	}
	//<= : 0  > : 1
	for(int i=1;i<=m;++i) {
		int sum=seg.Access(op[i].l,op[i].r);
		if(op[i].op==0) {
			seg.Edit(op[i].l,op[i].r-sum,0);
			seg.Edit(op[i].r-sum+1,op[i].r,1);
		} else {
			seg.Edit(op[i].l,op[i].l+sum-1,1);
			seg.Edit(op[i].l+sum,op[i].r,0);
		}
	}
	return seg.Access(q)==0;
}
int main() {
	freopen("input","r",stdin);
	is>>n>>m;
	for(int i=1;i<=n;++i) {
		is>>a[i];
	}
	for(int i=1;i<=m;++i) {
		is>>op[i].op>>op[i].l>>op[i].r;
	}
	is>>q;
	int L=1,R=n;
	while(L!=R) {
		int Mid=(L+R)>>1;
		MaybeSmaller(Mid)?(R=Mid):(L=Mid+1);
	}
	os<<L<<'\n';
	return 0;
}