首页 > 代码库 > 排序(bzoj 4552)
排序(bzoj 4552)
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
/* 题解很神奇。 二分答案k,那么就是要判断a[p]与k的大小关系。 我们把序列变成0/1序列,0代表该位置的数小于k,1代表大于等于k,对于升降序操作, 用线段树维护就可以了,最后判断一下。 */ #include<iostream> #include<cstdio> #include<cstring> #define N 30010 using namespace std; int a[N],b[N][3],n,m,p; int sum[N*4],tag[N*4]; void push_up(int k){ sum[k]=sum[k*2]+sum[k*2+1]; } void push_down(int k,int l,int r){ if(tag[k]==-1) return; int mid=l+r>>1; tag[k*2]=tag[k*2+1]=tag[k]; sum[k*2]=(mid-l+1)*tag[k]; sum[k*2+1]=(r-mid)*tag[k]; tag[k]=-1; } void change(int k,int l,int r,int x,int y,int val){ if(x>y) return; if(l>=x&&r<=y){ sum[k]=(r-l+1)*val; tag[k]=val; return; } push_down(k,l,r); int mid=l+r>>1; if(x<=mid) change(k*2,l,mid,x,y,val); if(y>mid) change(k*2+1,mid+1,r,x,y,val); push_up(k); } int query(int k,int l,int r,int x,int y){ if(l>=x&&r<=y) return sum[k]; push_down(k,l,r); int mid=l+r>>1,tot=0; if(x<=mid) tot+=query(k*2,l,mid,x,y); if(y>mid) tot+=query(k*2+1,mid+1,r,x,y); return tot; } bool check(int mid){ memset(tag,-1,sizeof(tag)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) change(1,1,n,i,i,a[i]>=mid); for(int i=1;i<=m;i++){ int t=query(1,1,n,b[i][1],b[i][2]); if(!b[i][0]){ change(1,1,n,b[i][1],b[i][2]-t,0); change(1,1,n,b[i][2]-t+1,b[i][2],1); } else { change(1,1,n,b[i][1],b[i][1]+t-1,1); change(1,1,n,b[i][1]+t,b[i][2],0); } } int t=query(1,1,n,p,p); return t; } int main(){ 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",&b[i][0],&b[i][1],&b[i][2]); scanf("%d",&p); int l=0,r=n,ans; while(l<=r){ int mid=l+r>>1; if(check(mid)) l=mid+1,ans=mid; else r=mid-1; } printf("%d",ans); return 0; }
排序(bzoj 4552)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。