首页 > 代码库 > bzoj4552 [Tjoi2016&Heoi2016]排序
bzoj4552 [Tjoi2016&Heoi2016]排序
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
正解：二分答案+线段树。
我们考虑二分答案，二分出一个$mid$的时候，我们把小于$mid$的数记为$0$，大于等于$mid$的数记为$1$。
那么局部排序就直接用线段树查询区间$0$和$1$的数量对应修改就行了。
最后查询$q$位置上的数是多少，如果是$0$说明答案比$mid$小，否则说明答案大于等于$mid$。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define N (200010)14 #define ls (x<<1)15 #define rs (x<<1|1)16 #define il inline17 #define RG register18 #define ll long long19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)20 21 using namespace std;22 23 struct data{ int op,l,r; }q[N];24 25 int lazy[4*N],sum[4*N],a[N],b[N],n,m,pos;26 27 il int gi(){28 RG int x=0,q=1; RG char ch=getchar();29 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();30 if (ch==‘-‘) q=-1,ch=getchar();31 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();32 return q*x;33 }34 35 il void pushdown(RG int x,RG int l,RG int r){36 RG int mid=(l+r)>>1; sum[ls]=(mid-l+1)*lazy[x],sum[rs]=(r-mid)*lazy[x];37 lazy[ls]=lazy[x],lazy[rs]=lazy[x],lazy[x]=-1; return;38 }39 40 il void build(RG int x,RG int l,RG int r){41 lazy[x]=-1; if (l==r){ sum[x]=b[l]; return; } RG int mid=(l+r)>>1;42 build(ls,l,mid),build(rs,mid+1,r),sum[x]=sum[ls]+sum[rs]; return;43 }44 45 il void update(RG int x,RG int l,RG int r,RG int xl,RG int xr,RG int v){46 if (xl<=l && r<=xr){ sum[x]=(r-l+1)*v,lazy[x]=v; return; }47 if (lazy[x]!=-1) pushdown(x,l,r); RG int mid=(l+r)>>1;48 if (xr<=mid) update(ls,l,mid,xl,xr,v);49 else if (xl>mid) update(rs,mid+1,r,xl,xr,v);50 else update(ls,l,mid,xl,mid,v),update(rs,mid+1,r,mid+1,xr,v);51 sum[x]=sum[ls]+sum[rs]; return;52 }53 54 il int query(RG int x,RG int l,RG int r,RG int xl,RG int xr){55 if (xl<=l && r<=xr) return sum[x];56 if (lazy[x]!=-1) pushdown(x,l,r); RG int mid=(l+r)>>1;57 if (xr<=mid) return query(ls,l,mid,xl,xr);58 else if (xl>mid) return query(rs,mid+1,r,xl,xr);59 else return query(ls,l,mid,xl,mid)+query(rs,mid+1,r,mid+1,xr);60 }61 62 il int check(RG int key){63 for (RG int i=1;i<=n;++i) b[i]=a[i]>=key; build(1,1,n);64 for (RG int i=1,res;i<=m;++i){65 res=query(1,1,n,q[i].l,q[i].r);66 if (!q[i].op){67 if (q[i].l<=q[i].r-res) update(1,1,n,q[i].l,q[i].r-res,0);68 if (q[i].r-res+1<=q[i].r) update(1,1,n,q[i].r-res+1,q[i].r,1);69 } else{70 if (q[i].l<=q[i].l+res-1) update(1,1,n,q[i].l,q[i].l+res-1,1);71 if (q[i].l+res<=q[i].r) update(1,1,n,q[i].l+res,q[i].r,0);72 }73 }74 return query(1,1,n,pos,pos);75 }76 77 il int find(){78 RG int l=1,r=n,mid,ans;79 while (l<=r){80 mid=(l+r)>>1;81 if (check(mid)) ans=mid,l=mid+1; else r=mid-1;82 }83 return ans;84 }85 86 il void work(){87 n=gi(),m=gi(); for (RG int i=1;i<=n;++i) a[i]=gi();88 for (RG int i=1;i<=m;++i) q[i].op=gi(),q[i].l=gi(),q[i].r=gi();89 pos=gi(); printf("%d\n",find()); return;90 }91 92 int main(){93 File("sort");94 work();95 return 0;96 }
bzoj4552 [Tjoi2016&Heoi2016]排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。