hdu5649 DZY Loves Sorting

hdu5649 DZY Loves Sorting

​​ Problem Description DZY has a sequence a[1..n] . It is a permutation of integers 1∼n .

Now he wants to perform two types of operations:

0lr : Sort a[l..r] in increasing order.

1lr : Sort a[l..r] in decreasing order.

After doing all the operations, he will tell you a position k , and ask you the value of a[k] .

Input First line contains t , denoting the number of testcases.

t testcases follow. For each testcase:

First line contains n,m . m is the number of operations.

Second line contains n space-separated integers a[1],a[2],⋯,a[n] , the initial sequence. We ensure that it is a permutation of 1∼n .

Then m lines follow. In each line there are three integers opt,l,r to indicate an operation.

Last line contains k .

(1≤t≤50,1≤n,m≤100000,1≤k≤n,1≤l≤r≤n,opt∈{0,1} . Sum of n in all testcases does not exceed 150000 . Sum of m in all testcases does not exceed 150000 )

Output For each testcase, output one line - the value of a[k] after performing all m operations.

Sample Input 1 6 3 1 6 2 5 3 4 0 1 4 1 3 6 0 2 4 3

Sample Output 5

Hint 1 6 2 5 3 4 -> [1 2 5 6] 3 4 -> 1 2 [6 5 4 3] -> 1 [2 5 6] 4 3. At last a[3]=5 a [ 3 ] = 5 .

每次二分下答案 然后将比他大的数改成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); int T=read(); while(T--){ 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小时内删除侵权内容。