...
题目：题意：分析：代码：
题目：
题目传送门
题意：
有一个长度为
n
n
n的排列，接下来会有
q
q
q个操作，共有两种操作，分别是将制定区间的数按升序或降序排列，求最后在
p
p
p位置上的是哪个数
分析：
我们对一个长度为
n
n
n的排列进行排序是很慢的，最好情况下也只能达到
n
l
o
g
n
nlogn
nlogn 但对于一个
01
01
01串来说就尤为优秀了，我们就需要用到线段树来进行维护 设
0
0
0有
k
k
k个，那么升序是把前
k
k
k个数变为
0
0
0，后
n
−
k
+
1
n-k+1
n−k+1个变为
1
1
1，降序则反之 如此一来，时间复杂度是十分优秀的
l
o
g
n
logn
logn了 在原题的基础上开始思考如何能把这个排列变为
01
01
01串呢，我们用到了二分答案，把原排列中大于
t
a
ta
ta的变为
1
1
1，小于
t
a
ta
ta的变为
0
0
0，如果排序之后第
p
p
p位是
1
1
1，意味这个答案是合法的
代码：
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
#define LL long long
using namespace std
;
inline LL
read() {
LL d
=0,f
=1;char s
=getchar();
while(s
<'0'||s
>'9'){if(s
=='-')f
=-1;s
=getchar();}
while(s
>='0'&&s
<='9'){d
=d
*10+s
-'0';s
=getchar();}
return d
*f
;
}
int a
[100005];
int n
=read(),m
=read(),q
,L
=1,R
=n
;
struct tree
{
int w
,l
,r
,lazy
;
}t
[400005];
void build(int k
,int l
,int r
,int w
)
{
t
[k
].l
=l
;t
[k
].r
=r
;t
[k
].lazy
=0;
if(l
==r
) {t
[k
].w
=(a
[l
]>=w
);return;}
int mid
=(l
+r
)>>1;
build(k
*2,l
,mid
,w
);build(k
*2+1,mid
+1,r
,w
);
t
[k
].w
=t
[k
*2].w
+t
[k
*2+1].w
;
return;
}
void pushdown(int k
)
{
if(!t
[k
].lazy
) return;
t
[k
*2].lazy
=t
[k
*2+1].lazy
=t
[k
].lazy
;
int mid
=(t
[k
].l
+t
[k
].r
)>>1;
if(t
[k
].lazy
==1) {t
[k
*2].w
=mid
-t
[k
].l
+1;t
[k
*2+1].w
=t
[k
].r
-mid
;}
else t
[k
*2].w
=t
[k
*2+1].w
=0;
t
[k
].lazy
=0;
return;
}
int query(int k
,int l
,int r
)
{
if(l
<=t
[k
].l
&&t
[k
].r
<=r
) return t
[k
].w
;
if(r
<t
[k
].l
||l
>t
[k
].r
) return 0;
pushdown(k
);
return query(k
*2,l
,r
)+query(k
*2+1,l
,r
);
}
void change(int k
,int l
,int r
,int w
)
{
if(l
<=t
[k
].l
&&t
[k
].r
<=r
) {t
[k
].w
=w
*(t
[k
].r
-t
[k
].l
+1);t
[k
].lazy
=!w
?-1:1;return;}
if(r
<t
[k
].l
||l
>t
[k
].r
) return;
pushdown(k
);
change(k
*2,l
,r
,w
);change(k
*2+1,l
,r
,w
);
t
[k
].w
=t
[k
*2].w
+t
[k
*2+1].w
;
return;
}
int qquery(int k
,int x
)
{
if(t
[k
].l
==x
&&t
[k
].r
==x
) return t
[k
].w
;
pushdown(k
);
int mid
=(t
[k
].l
+t
[k
].r
)>>1;
if(x
<=mid
) return qquery(k
*2,x
);
else return qquery(k
*2+1,x
);
}
int o
[100005],l
[100005],r
[100005];
bool
check(int w
)
{
build(1,1,n
,w
);
for(int i
=1;i
<=m
;i
++)
{
int x
=query(1,l
[i
],r
[i
]);
if(!o
[i
])
{
change(1,r
[i
]-x
+1,r
[i
],1);
change(1,l
[i
],r
[i
]-x
,0);
}
else
{
change(1,l
[i
],l
[i
]+x
-1,1);
change(1,l
[i
]+x
,r
[i
],0);
}
}
return qquery(1,q
);
}
int main()
{
for(int i
=1;i
<=n
;i
++) a
[i
]=read();
for(int i
=1;i
<=m
;i
++) o
[i
]=read(),l
[i
]=read(),r
[i
]=read();
q
=read();
while(L
<R
)
{
int mid
=(L
+R
)>>1;
if(check(mid
)) L
=mid
+1; else R
=mid
;
}
cout
<<L
-1;
return 0;
}
