首页 > 代码库 > [bzoj4552][Tjoi2016&Heoi2016]排序
[bzoj4552][Tjoi2016&Heoi2016]排序
来自FallDream的博客，未经允许，请勿转载，谢谢。
在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。
n,m<=10^5
一道十分巧妙的题 虽然被ditoly秒切了(orz集训队大爷)
考虑二分答案，然后大于的设成1，小等于设成0，用线段树维护。
每次排序就是把0和1其中一个全部丢到前面，另一个丢到后面，也就是区间赋值
复杂度nlog^2n
#include<iostream>#include<cstdio>#define MN 100000using namespace std;inline int read(){ int x=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar(); return x;}int a[MN+5],n,m,Mid,Res,Pos;struct op{int kind,l,r;}q[MN+5];struct Tree{int l,r,tag,val,x;}T[MN*4+5];void build(int x,int l,int r){ T[x].tag=0; if((T[x].l=l)==(T[x].r=r)){T[x].x=(a[l]<=Mid);return;} int mid=l+r>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); T[x].x=T[x<<1].x+T[x<<1|1].x;}inline void Mark(int x,int v){ T[x].tag=1;T[x].val=v; T[x].x=(v?0:T[x].r-T[x].l+1);}inline void pushdown(int x){ Mark(x<<1,T[x].val); Mark(x<<1|1,T[x].val); T[x].tag=0;}void Modify(int x,int l,int r,int ad){ if(l>r) return; if(T[x].l==l&&T[x].r==r){Mark(x,ad);return;} if(T[x].tag) pushdown(x); int mid=T[x].l+T[x].r>>1; if(r<=mid) Modify(x<<1,l,r,ad); else if(l>mid) Modify(x<<1|1,l,r,ad); else Modify(x<<1,l,mid,ad),Modify(x<<1|1,mid+1,r,ad); T[x].x=T[x<<1].x+T[x<<1|1].x;}int Query(int x,int l,int r){ if(T[x].l==l&&T[x].r==r) return T[x].x; if(T[x].tag) pushdown(x); int mid=T[x].l+T[x].r>>1; if(r<=mid) return Query(x<<1,l,r); else if(l>mid) return Query(x<<1|1,l,r); else return Query(x<<1,l,mid)+Query(x<<1|1,mid+1,r);}int main(){ n=read();m=read(); for(int i=1;i<=n;++i) a[i]=read(); for(int i=1;i<=m;++i) q[i].kind=read(),q[i].l=read(),q[i].r=read(); Pos=read();int l=1,r=n; while(l<=r) { Mid=l+r>>1; build(1,1,n); for(int i=1;i<=m;++i) { int x=Query(1,q[i].l,q[i].r); if(q[i].kind) Modify(1,q[i].l,q[i].r-x,1),Modify(1,q[i].r-x+1,q[i].r,0); else Modify(1,q[i].l,q[i].l+x-1,0),Modify(1,q[i].l+x,q[i].r,1); } if(Query(1,Pos,Pos)) Res=Mid,r=Mid-1; else l=Mid+1; } printf("%d\n",Res); return 0;}
[bzoj4552][Tjoi2016&Heoi2016]排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。