题目描述
在 20162016 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。
这个难题是这样子的：给出一个 1 到 n 的排列，现在对这个排列序列进行 m 次局部排序，排序分为两种：
0 l r表示将区间 [l,r][l,r] 的数字升序排序1 l r表示将区间 [l,r][l,r] 的数字降序排序
注意，这里是对下标在区间 [l,r][l,r] 内的数排序。
最后询问第 q 位置上的数字。
输入格式
输入数据的第一行为两个整数 n 和 m，n 表示序列的长度，mm 表示局部排序的次数。
第二行为 n 个整数，表示 11 到 n 的一个排列。
接下来输入 m 行，每一行有三个整数 op,l,r，op 为 0 代表升序排序，op 为 1 代表降序排序, l,r 表示排序的区间。
最后输入一个整数 q，表示排序完之后询问的位置
输出格式
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第 q 位置上的数字。
输入输出样例
输入 #1
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
输出 #1
5
说明/提示
河北省选2016第一天第二题。
对于 30% 的数据，n,m≤1000
对于 100% 的数据，n,m≤10e5，1≤q≤n
题解：
很有意思的一道题，如果完全按照题目中所说的去写(也就是说直接nlogn排序)的化时间复杂度就是mnlogn，肯定是会超时的，但是我们发现整个题目只有一个询问，也就是说我们可以考虑一些离线做法。
这里我们思考另一个问题，如何对一个01串进行排序？当然我们是可以直接nlogn排序的，但是更好的做法就是求得整个01串的和sum(也就是1的数量)，然后把前sum个数字全部覆盖成1，后面所有数字全都覆盖成0，反之亦然。这样的化我们如果可以提前用数据结构处理一下的化就可以降低每次排序的时间复杂度了。
另外，题目中说了是1到n的一个排列，也就是说数字的范围和下标的范围是一样的。我们可以考虑一个二分来猜测k位置上的数字。
我们假设一个mid，然后把整个数列里面大于等于mid的数字都标记成1，小于mid的数字都标记成0，接着按照上面所说的方式对这个01串进行排序，最后我们只要检查在k位置上的数字是1还是0，如果是1的化证明我们的mid是(geq)真实答案的，反过来也是一样的。
至于用来平推区间的数据结构，线段树就可以了
当然dalao们也可以试一试珂朵莉树，不过我猜测不吸氧是过不了的
这里思想如果有点没理解的化可以去康康这道题
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct ques {
int o,l,r;
} q[maxn];
struct node {
int sum,tag;
} t[maxn];
int a[maxn],n,m,k;
void pushdown(int pos,int l,int r) {
if(t[pos].tag!=-1) {
t[pos<<1].tag=t[pos<<1|1].tag=t[pos].tag;
int mid=(l+r)/2;
t[pos<<1].sum=t[pos].tag*(mid-l+1);
t[pos<<1|1].sum=t[pos].tag*(r-mid);
t[pos].tag=-1;
}
}
void pushup(int pos) {
t[pos].sum=t[pos<<1].sum+t[pos<<1|1].sum;
}
void build(int l,int r,int pos,int k) {
t[pos].tag=-1;
if(l==r) {
t[pos].sum=(a[l]>=k);
return;
}
int mid=(l+r)/2;
build(l,mid,pos<<1,k);
build(mid+1,r,pos<<1|1,k);
pushup(pos);
}
int query(int ll,int rr,int l,int r,int pos) {
if(ll<=l&&rr>=r) return t[pos].sum;
pushdown(pos,l,r);
int mid=(l+r)/2,res=0;
if(ll<=mid) {
res+=query(ll,rr,l,mid,pos<<1);
}
if(mid<rr) {
res+=query(ll,rr,mid+1,r,pos<<1|1);
}
return res;
}
void update(int ll,int rr,int l,int r,int pos,int x) {
if(ll>rr) return;
if(ll<=l&&rr>=r) {
t[pos].tag=x;
t[pos].sum=(r-l+1)*x;
return;
}
pushdown(pos,l,r);
int mid=(l+r)/2;
if(ll<=mid) {
update(ll,rr,l,mid,pos<<1,x);
}
if(rr>mid) {
update(ll,rr,mid+1,r,pos<<1|1,x);
}
pushup(pos);
}
int check(int x,int k) {
build(1,n,1,x);
for(int i=1; i<=m; i++) {
int sum=query(q[i].l,q[i].r,1,n,1);
if(!q[i].o) {
update(q[i].l,q[i].r-sum,1,n,1,0);
update(q[i].r-sum+1,q[i].r,1,n,1,1);
} else {
update(q[i].l,q[i].l+sum-1,1,n,1,1);
update(q[i].l+sum,q[i].r,1,n,1,0);
}
}
return query(k,k,1,n,1);
}
int main(void) {
scanf("%d %d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
for(int i=1; i<=m; i++) {
scanf("%d %d %d",&q[i].o,&q[i].l,&q[i].r);
}
scanf("%d",&k);
int l=0,r=1e6,res=0;
while(l<=r) {
int mid=(l+r)/2;
if(check(mid,k)) {
l=mid+1;
res=mid;
} else {
r=mid-1;
}
}
printf("%d",res);
}