问题描述
在 2016 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。
这个难题是这样子的：给出一个 1 到 n 的排列，现在对这个排列序列进行 m 次局部排序，排序分为两种：
0 l r表示将区间 [l,r] 的数字升序排序1 l r表示将区间 [l,r] 的数字降序排序
注意，这里是对下标在区间 [l,r] 内的数排序。
最后询问第 q 位置上的数字。
输入格式
输入数据的第一行为两个整数 n 和 m，n 表示序列的长度，m 表示局部排序的次数。
第二行为 n 个整数，表示 1 到 n 的一个排列。
接下来输入 m 行，每一行有三个整数 $ ext{op},l,r(，) ext{op}$ 为 0 代表升序排序，( ext{op}) 为 1 代表降序排序, l,r 表示排序的区间。
最后输入一个整数 q，表示排序完之后询问的位置。
输出格式
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第 q 位置上的数字。
样例输入
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
样例输出
5
说明
河北省选2016第一天第二题。
对于 30% 的数据，(n,mleq 1000)
对于 100% 的数据，(n,mleq 10^5)，(1leq qleq n)
解析
最简单的做法是每次都排序，但复杂度上显然不能够通过。
考虑优化一下这个做法。首先发现答案具有单调性，那么就二分一个mid，把大于等于mid的数变为1，小于mid的数变成0。排序时，如果是顺序排序，就可以把所有0放在区间前面，1放在区间后面；逆序同理。这可以用线段树实现。如果最后第q为上是1，说明还可以有更大的mid，否则说明当前的mid过大。
代码
#include <iostream>
#include <cstdio>
#define N 100002
using namespace std;
struct SegmentTree{
int dat,add;
}t[N*4];
struct event{
int op,l,r;
}p[N];
int n,m,q,i,a[N],l,r,mid,ans;
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
void update(int p)
{
t[p].dat=t[p*2].dat+t[p*2+1].dat;
}
void spread(int p,int l,int r)
{
if(t[p].add!=-1){
int mid=(l+r)/2;
t[p*2].add=t[p].add;
t[p*2+1].add=t[p].add;
t[p*2].dat=t[p].add*(mid-l+1);
t[p*2+1].dat=t[p].add*(r-mid);
t[p].add=-1;
}
}
void build(int p,int l,int r,int x)
{
t[p].add=-1;
if(l==r){
t[p].dat=(a[l]>=x);
return;
}
int mid=(l+r)/2;
build(p*2,l,mid,x);
build(p*2+1,mid+1,r,x);
update(p);
}
int ask(int p,int l,int r,int ql,int qr)
{
if(ql>qr) return 0;
if(ql<=l&&r<=qr) return t[p].dat;
int mid=(l+r)/2,ans=0;
spread(p,l,r);
if(ql<=mid) ans+=ask(p*2,l,mid,ql,qr);
if(qr>mid) ans+=ask(p*2+1,mid+1,r,ql,qr);
return ans;
}
void change(int p,int l,int r,int ql,int qr,int x)
{
if(ql>qr) return;
if(ql<=l&&r<=qr){
t[p].add=x;
t[p].dat=(r-l+1)*x;
return;
}
int mid=(l+r)/2;
spread(p,l,r);
if(ql<=mid) change(p*2,l,mid,ql,qr,x);
if(qr>mid) change(p*2+1,mid+1,r,ql,qr,x);
update(p);
}
bool check(int x)
{
build(1,1,n,x);
for(int i=1;i<=m;i++){
int cnt=ask(1,1,n,p[i].l,p[i].r);
if(p[i].op==0){
change(1,1,n,p[i].l,p[i].r-cnt,0);
change(1,1,n,p[i].r-cnt+1,p[i].r,1);
}
else{
change(1,1,n,p[i].l,p[i].l+cnt-1,1);
change(1,1,n,p[i].l+cnt,p[i].r,0);
}
}
return ask(1,1,n,q,q);
}
int main()
{
n=read();m=read();
for(i=1;i<=n;i++){
a[i]=read();
r=max(r,a[i]);
}
for(i=1;i<=m;i++) p[i].op=read(),p[i].l=read(),p[i].r=read();
q=read();
while(l<=r){
mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d
",ans);
return 0;
}