http://www.lydsy.com/JudgeOnline/problem.php?id=4552
二分答案
把>=mid 的数看做1，<mid 的数看做0
这样升序、降序排列相当于区间查询0,1 的个数，区间覆盖0,1
线段树即可完成
查询给定位置p
如果=1，说明p位置的数>=mid ，上调下界
如果=0，说明p位置的数<mid，下调上界
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001 int n,m,p; int a[N],MID; int sum0[N<<],sum1[N<<],flag[N<<]; int tot0,tot1; struct node
{
int ty,l,r;
}e[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void build(int k,int l,int r)
{
sum0[k]=sum1[k]=;
flag[k]=-;
if(l==r)
{
if(a[l]>=MID) sum1[k]++;
else sum0[k]++;
return;
}
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
sum0[k]=sum0[k<<]+sum0[k<<|];
sum1[k]=sum1[k<<]+sum1[k<<|];
} void down(int k,int l,int mid,int r)
{
if(!flag[k])
{
sum0[k<<]=mid-l+;
sum1[k<<]=;
sum0[k<<|]=r-mid;
sum1[k<<|]=;
}
else
{
sum1[k<<]=mid-l+;
sum0[k<<]=;
sum1[k<<|]=r-mid;
sum0[k<<|]=;
}
flag[k<<]=flag[k<<|]=flag[k];
flag[k]=-;
} void query(int k,int l,int r,int opl,int opr)
{
if(l>=opl && r<=opr)
{
tot0+=sum0[k];
tot1+=sum1[k];
return;
}
int mid=l+r>>;
if(flag[k]!=-) down(k,l,mid,r);
if(opl<=mid) query(k<<,l,mid,opl,opr);
if(opr>mid) query(k<<|,mid+,r,opl,opr);
} void change(int k,int l,int r,int opl,int opr,int ty)
{
if(l>=opl && r<=opr)
{
if(!ty)
{
sum0[k]=r-l+;
sum1[k]=;
}
else
{
sum0[k]=;
sum1[k]=r-l+;
}
flag[k]=ty;
return;
}
int mid=l+r>>;
if(flag[k]!=-) down(k,l,mid,r);
if(opl<=mid) change(k<<,l,mid,opl,opr,ty);
if(opr>mid) change(k<<|,mid+,r,opl,opr,ty);
sum0[k]=sum0[k<<]+sum0[k<<|];
sum1[k]=sum1[k<<]+sum1[k<<|];
} int ask(int k,int l,int r,int pos)
{
if(l==r) return sum1[k];
int mid=l+r>>;
if(flag[k]!=-) down(k,l,mid,r);
if(pos<=mid) return ask(k<<,l,mid,pos);
return ask(k<<|,mid+,r,pos);
} bool check(int mid)
{
MID=mid;
build(,,n);
for(int i=;i<=m;++i)
{
tot0=tot1=;
query(,,n,e[i].l,e[i].r);
if(!e[i].ty)
{
if(tot0) change(,,n,e[i].l,e[i].l+tot0-,);
if(tot1) change(,,n,e[i].r-tot1+,e[i].r,);
}
else
{
if(tot1) change(,,n,e[i].l,e[i].l+tot1-,);
if(tot0) change(,,n,e[i].r-tot0+,e[i].r,);
}
}
return ask(,,n,p);
} int main()
{
read(n); read(m);
for(int i=;i<=n;++i) read(a[i]);
for(int i=;i<=m;++i) read(e[i].ty),read(e[i].l),read(e[i].r);
read(p);
int l=,r=n,mid,ans;
while(l<=r)
{
mid=MID=l+r>>;
if(check(mid)) ans=mid,l=mid+;
else r=mid-;
}
cout<<ans;
}
4552: [Tjoi2016&Heoi2016]排序
Time Limit: 60 Sec Memory Limit: 256 MB
Submit: 1478 Solved: 748
[Submit][Status][Discuss]
Description
在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题
，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排
序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q
位置上的数字。
Input
输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整
数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序
排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 10^5
，1 <= m <= 10^5
Output
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。
Sample Input
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
Sample Output
5