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 Sample Output

5 HINT

Source

每次二分下答案 然后将比他大的数改成1比他小的数改成0 那么每次对一个区间排序显然就是对0，1排序 那么查询一下区间内有多少个0，1即可 然后直接线段树区间修改 然后最后询问p位置上是0 还是1 如果是1 说明答案还可以再大 一直二分即可

#include#include#include#define lc (x<<1)#define rc (x<<1|1)#define N 100010using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if(T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}struct node{ int s,tag;}tree[N<<2];inline void pushdown(int x,int l,int r,int mid){ if (tree[x].tag==-1) return; if (tree[x].tag==1){tree[x].tag=-1; tree[lc].s=mid-l+1;tree[lc].tag=1; tree[rc].s=r-mid;tree[rc].tag=1;return; }tree[x].tag=-1; tree[lc].s=tree[rc].s=tree[lc].tag=tree[rc].tag=0;}inline void update(int x){tree[x].s=tree[lc].s+tree[rc].s;}inline void modify(int x,int l,int r,int l1,int r1,int v){ if (l1>r1) return; if (l1<=l&&r1>=r){tree[x].tag=v;tree[x].s=v*(r-l+1);return;} int mid=l+r>>1;pushdown(x,l,r,mid); if (l1<=mid) modify(lc,l,mid,l1,r1,v); if (r1>mid) modify(rc,mid+1,r,l1,r1,v);update(x);}int ave,a[N];inline void build(int x,int l,int r){ if(l==r) {tree[x].s=(a[l]>=ave);return;}int mid=l+r>>1; tree[x].tag=-1;build(lc,l,mid);build(rc,mid+1,r);update(x);}inline int query(int x,int l,int r,int l1,int r1){ if (l1<=l&&r1>=r) return tree[x].s; int mid=l+r>>1;pushdown(x,l,r,mid);int tmp=0; if (l1<=mid) tmp+=query(lc,l,mid,l1,r1); if (r1>mid) tmp+=query(rc,mid+1,r,l1,r1);return tmp;}inline void print(int x,int l,int r){ if(l==r) {printf("%d %d %d\n",l,r,tree[x].s);return;} int mid=l+r>>1;pushdown(x,l,r,mid); print(lc,l,mid);printf("%d %d %d\n",l,r,tree[x].s); print(rc,mid+1,r);}int n,m,l[N],r[N],op[N],p;inline bool check(int md){ ave=md;build(1,1,n);//printf("%d\n",md);print(1,1,n);puts("---"); for (int i=1;i<=m;++i){static int s,s1; if(op[i]==0){ s=query(1,1,n,l[i],r[i]);s1=r[i]-l[i]+1-s; modify(1,1,n,l[i],l[i]+s1-1,0); modify(1,1,n,r[i]-s+1,r[i],1);//print(1,1,n);puts("---"); }else{ s=query(1,1,n,l[i],r[i]);s1=r[i]-l[i]+1-s; modify(1,1,n,l[i],l[i]+s-1,1);//print(1,1,n);puts("---"); modify(1,1,n,r[i]-s1+1,r[i],0);//print(1,1,n);puts("---"); } }return query(1,1,n,p,p);}int main(){ freopen("bzoj4552.in","r",stdin); n=read();m=read();int L=1,R=n; for (int i=1;i<=n;++i) a[i]=read(); for (int i=1;i<=m;++i) op[i]=read(),l[i]=read(),r[i]=read();p=read(); while(L<=R){static int mid; mid=L+R>>1; if (check(mid)) L=mid+1;else R=mid-1; }printf("%d\n",R); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。