BZOJ4552 [HEOI2016 & TJOI2016]排序

题意

在2016年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他。这个难题是这样子的:给出一个$1$到$n$的全排列,现在对这个全排列序列进行$m$次局部排序,排序分为两种:

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

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

题解

这道题的思路还是很巧妙的……
先考虑如果数字只有$0$或$1$,我们怎么对这个序列排序。这个问题似乎并不复杂。查询一下某个区间有多少个$0$,然后直接区间赋值就好了。但是在这道题中,由于数字的范围和$n$是一样的,这么做复杂度就不对了。因此可以考虑把这个序列转化为一个$01$序列。注意到整个询问只有一次,可以考虑二分答案,把大于等于答案的数赋为$1$,否则赋为$0$。接下来只要查询对应位置上的数是否为$1$。如果为$1$,说明答案会大于等于这个数,二分下去即可。
时间复杂度$O(n\log^2n)$

代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=1e5+10;
const int maxm=1e5+10;
struct node{
int opt,l,r;
}modify[maxm];
int val[maxn],a[maxn];
int n,m,pos;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
struct Segment_Tree{
int Sum[maxn<<2],Col[maxn<<2];
int cnt;
inline void Push_Down(int h,int l,int r){
if(Col[h]!=-1){
int mid=(l+r)>>1;
Col[h<<1]=Col[h<<1|1]=Col[h];
Sum[h<<1]=Col[h]*(mid-l+1);Sum[h<<1|1]=Col[h]*(r-mid);
Col[h]=-1;
}
}
inline void Build(int h,int l,int r){
Col[h]=-1;
if(l==r){
Sum[h]=a[++cnt];
return;
}
int mid=(l+r)>>1;
Build(h<<1,l,mid);
Build(h<<1|1,mid+1,r);
Sum[h]=Sum[h<<1]+Sum[h<<1|1];
}
inline void Modify(int h,int l,int r,int L,int R,int Val){
if(L<=l && r<=R){
Sum[h]=Val*(r-l+1);
Col[h]=Val;
return;
}
Push_Down(h,l,r);
int mid=(l+r)>>1;
if(L<=mid)Modify(h<<1,l,mid,L,R,Val);
if(R>mid)Modify(h<<1|1,mid+1,r,L,R,Val);
Sum[h]=Sum[h<<1]+Sum[h<<1|1];
}
inline int Query(int h,int l,int r,int L,int R){
if(L<=l && r<=R)return Sum[h];
Push_Down(h,l,r);
int mid=(l+r)>>1,ans=0;
if(L<=mid)ans+=Query(h<<1,l,mid,L,R);
if(R>mid)ans+=Query(h<<1|1,mid+1,r,L,R);
return ans;
}
}T;
inline int check(int Val){
int i;
T.cnt=0;
for(i=1;i<=n;i++)a[i]=val[i]>=Val?1:0;
T.Build(1,1,n);
for(i=1;i<=m;i++){
int l=modify[i].l,r=modify[i].r,opt=modify[i].opt;
int sum=T.Query(1,1,n,l,r);
if(opt){
if(sum)T.Modify(1,1,n,l,l+sum-1,opt);
if(sum<=r-l)T.Modify(1,1,n,l+sum,r,opt^1);
}
else{
if(sum<=r-l)T.Modify(1,1,n,l,r-sum,opt);
if(sum)T.Modify(1,1,n,r-sum+1,r,opt^1);
}
}
return T.Query(1,1,n,pos,pos);
}
int main(){
int i;
#ifndef ONLINE_JUDGE
freopen("BZOJ4552.in","r",stdin);
freopen("BZOJ4552.out","w",stdout);
#endif
n=read();m=read();
for(i=1;i<=n;i++)val[i]=read();
for(i=1;i<=m;i++){
int opt,l,r;
opt=read();l=read();r=read();
modify[i]=(node){opt,l,r};
}
pos=read();
int l=1,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
printf("%d\n",l);
return 0;
}