DZY Loves Sorting
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 753 Accepted Submission(s): 249
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].
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)
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$.
Source
Recommend
wange2014
题意就是一个n的排列，执行Q次操作，每次操作是对某个区间从小到大排序或者从大到小排序。最后只查询一次，输出第k个位置当前的数。
因为只查询一次，而且这是n的全排列，所以直接二分答案，比mid小的赋值为0，大的赋值为1。区间查询判断的时候直接与0和1比较就可以了。
代码:
1 //M-线段树+二分-HDU5649
2 #include<iostream>
3 #include<algorithm>
4 #include<cstring>
5 #include<iomanip>
6 #include<stdio.h>
7 #include<stdlib.h>
8 #include<math.h>
9 #include<cstdlib>
10 #include<set>
11 #include<map>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<vector>
16 #include<set>
17 using namespace std;
18 typedef long long ll;
19 const int inf=0x3f3f3f3f;
20 const double eps=1e-5;
21 const int maxn=1e5+10;
22 #define lson l,m,rt<<1
23 #define rson m+1,r,rt<<1|1
24
25 struct node{
26 int c,l,r;
27 }q[maxn];
28 int n,m,k;
29 int a[maxn],tree[maxn<<2],add[maxn<<2];
30
31 void pushup(int rt)
32 {
33 tree[rt]=tree[rt<<1]+tree[rt<<1|1];
34 }
35 void pushdown(int rt,int m)
36 {
37 if(add[rt]!=-1){
38 add[rt<<1]=add[rt<<1|1]=add[rt];
39 tree[rt<<1]=(m-(m>>1))*add[rt];
40 tree[rt<<1|1]=(m>>1)*add[rt];
41 add[rt]=-1;
42 }
43 }
44 void build(int x,int l,int r,int rt)
45 {
46 add[rt]=-1;
47 if(l==r){
48 tree[rt]=a[l]<=x?0:1;
49 return ;
50 }
51
52 int m=(l+r)>>1;
53 build(x,lson);
54 build(x,rson);
55 pushup(rt);
56 }
57 void update(int L,int R,int c,int l,int r,int rt)
58 {
59 if(L>R) return ;
60 if(L<=l&&r<=R){
61 add[rt]=c;
62 tree[rt]=(r-l+1)*c;
63 return ;
64 }
65
66 pushdown(rt,r-l+1);
67 int m=(l+r)>>1;
68 if(L<=m) update(L,R,c,lson);
69 if(R> m) update(L,R,c,rson);
70 pushup(rt);
71 }
72 int query(int L,int R,int l,int r,int rt)
73 {
74 if(L<=l&&r<=R){
75 return tree[rt];
76 }
77
78 pushdown(rt,r-l+1);
79 int m=(l+r)>>1;int ret=0;
80 if(L<=m) ret+=query(L,R,lson);
81 if(R> m) ret+=query(L,R,rson);
82 return ret;
83 }
84 bool check(int x)
85 {
86 build(x,1,n,1);
87 for(int i=1;i<=m;i++){
88 int c=q[i].c,l=q[i].l,r=q[i].r;
89 int cnt=query(l,r,1,n,1);
90 if(c){
91 update(l,l+cnt-1,1,1,n,1);
92 update(l+cnt,r,0,1,n,1);
93 }
94 else{
95 update(r-cnt+1,r,1,1,n,1);
96 update(l,r-cnt,0,1,n,1);
97 }
98 }
99 return query(k,k,1,n,1);
100 }
101 int main()
102 {
103 int t;
104 scanf("%d",&t);
105 while(t--){
106 scanf("%d%d",&n,&m);
107 for(int i=1;i<=n;i++)
108 scanf("%d",&a[i]);
109 for(int i=1;i<=m;i++)
110 scanf("%d%d%d",&q[i].c,&q[i].l,&q[i].r);
111 scanf("%d",&k);
112 int l=1,r=n;
113 while(l<=r){
114 int mid=(l+r)>>1;
115 if(!check(mid)) r=mid-1;
116 else l=mid+1;
117 }
118 printf("%d
",r+1);
119 }
120 return 0;
121 }