TJOI2016排序

TJOI2016 排序

题目大意:

给出一个1到n的全排列,现在对这个全排列序列进行m次局部排序,排序分为两种:

• (0,l,r)表示将区间[l,r]的数字升序排序

• (1,l,r)表示将区间[l,r]的数字降序排序

最后询问第q位置上的数字。

题解:

这种题比较有意思。

如果没有想到用二分的话,还是比较令人头疼的,但如果想到的话,问题也就迎刃而解了。

我们首先二分第q个位置上的数字。

并且把原排列中大于等于我的都看作1,小于我的看做0。

那么之后的排序操作就相当于把一个区间的所有1和0的位置相应移动。

这个我们用线段树即可实现。

最后操作完后,看q这个位置送是否合法,并相应改变二分的区间。

总的时间复杂度为$O(nlog^2n)$。

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
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
res=0;char c;
while(c=getchar(),c<48);
do res=res*10+(c&15);
while(c=getchar(),c>47);
}
const int N=100005;
int n,m,num[N];
struct Segment_tree{
struct node{
int L,R,sum,flag;
}tree[N<<2];
void up(int p){
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
}
void down(int p){
if(~tree[p].flag){
tree[p<<1].sum=(tree[p<<1].R-tree[p<<1].L+1)*tree[p].flag;
tree[p<<1|1].sum=(tree[p<<1|1].R-tree[p<<1|1].L+1)*tree[p].flag;
tree[p<<1].flag=tree[p<<1|1].flag=tree[p].flag;
tree[p].flag=-1;
}
}
void build(int L,int R,int lim,int p){
tree[p].L=L,tree[p].R=R,tree[p].flag=-1;
if(L==R){
if(num[L]>=lim)tree[p].sum=1;
else tree[p].sum=0;
return;
}
int mid=L+R>>1;
build(L,mid,lim,p<<1);
build(mid+1,R,lim,p<<1|1);
up(p);
}
void update(int L,int R,int v,int p){
if(tree[p].L==L&&tree[p].R==R){
tree[p].sum=(R-L+1)*v;
tree[p].flag=v;
return;
}
down(p);
int mid=tree[p].L+tree[p].R>>1;
if(R<=mid)update(L,R,v,p<<1);
else if(L>mid)update(L,R,v,p<<1|1);
else update(L,mid,v,p<<1),update(mid+1,R,v,p<<1|1);
up(p);
}
int query(int L,int R,int p){
if(tree[p].L==L&&tree[p].R==R)return tree[p].sum;
down(p);
int mid=tree[p].L+tree[p].R>>1;
if(R<=mid)return query(L,R,p<<1);
else if(L>mid)return query(L,R,p<<1|1);
else return query(L,mid,p<<1)+query(mid+1,R,p<<1|1);
}
}T;
int op[N],a[N],b[N],pos;
bool check(int lim){
T.build(1,n,lim,1);
for(int i=1;i<=m;i++){
int cnt_1=T.query(a[i],b[i],1);
int cnt_0=b[i]-a[i]+1-cnt_1;
if(op[i]==1){
if(cnt_1)T.update(a[i],a[i]+cnt_1-1,1,1);
if(cnt_0)T.update(b[i]-cnt_0+1,b[i],0,1);
}else{
if(cnt_0)T.update(a[i],a[i]+cnt_0-1,0,1);
if(cnt_1)T.update(b[i]-cnt_1+1,b[i],1,1);
}
}
return T.query(pos,pos,1);
}
int main(){
Rd(n),Rd(m);
for(int i=1;i<=n;i++)
Rd(num[i]);
for(int i=1;i<=m;i++)
Rd(op[i]),Rd(a[i]),Rd(b[i]);
Rd(pos);
int L=1,R=n,res=-1;
while(L<=R){
int mid=L+R>>1;
if(check(mid)){
res=mid;
L=mid+1;
}else R=mid-1;
}
printf("%d\n",res);
return 0;
}
分享到 评论