[TJOI 2016&HEOI 2016]排序-白红宇

[TJOI 2016&HEOI 2016]排序

阅读量：4678 次

发布时间：2019-06-09

本文共 3433 字，大约阅读时间需要 11 分钟。

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

Sample Output

题解（转载）

首先常规套路，如果值域较小，那么枚举值域线段树区间覆盖

那么这题这么做这个转换呢？直接二分答案，把小于的部分赋为$0$，大于等于部分$1$，这样转换过来了，注意线段树只要存$1$就好,$0$直接可以相减得出

1 //It is made by Awson on 2017.10.23  2 #include 
      
         3 #include 
         4 #include 
        
           5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 #include 
                 
                   14 #include 
                  
                    15 #include 
                   
                     16 #define LL long long 17 #define Min(a, b) ((a) < (b) ? (a) : (b)) 18 #define Max(a, b) ((a) > (b) ? (a) : (b)) 19 #define Lr(o) (o<<1) 20 #define Rr(o) (o<<1|1) 21 using namespace std; 22 const int N = 1e5; 23 24 int n, m, q, a[N+5]; 25 struct operat { 26 int opt, l, r; 27 }p[N+5]; 28 struct tt { 29 int sgm[(N<<2)+5], lazy[(N<<2)+5]; 30 void build(int o, int l, int r, int key) { 31 lazy[o] = 0; 32 if (l == r) { 33 sgm[o] = (a[l]>=key); return; 34 } 35 int mid = (l+r)>>1; 36 build(Lr(o), l, mid, key); build(Rr(o), mid+1, r, key); 37 sgm[o] = sgm[Lr(o)]+sgm[Rr(o)]; 38 } 39 void pushdown(int o, int l, int r, int mid) { 40 if (lazy[o] == 1) { 41 lazy[Lr(o)] = lazy[Rr(o)] = 1; 42 sgm[Lr(o)] = mid-l+1, sgm[Rr(o)] = r-mid; 43 lazy[o] = 0; 44 }else if (lazy[o] == -1) { 45 lazy[Lr(o)] = lazy[Rr(o)] = -1; 46 sgm[Lr(o)] = 0, sgm[Rr(o)] = 0; 47 lazy[o] = 0; 48 } 49 } 50 void update(int o, int l, int r, int a, int b, int key) { 51 if (a <= l && r <= b) { 52 if (key) lazy[o] = 1, sgm[o] = r-l+1; 53 else lazy[o] = -1, sgm[o] = 0; 54 return; 55 } 56 int mid = (l+r)>>1; 57 pushdown(o, l, r, mid); 58 if (a <= mid) update(Lr(o), l, mid, a, b, key); 59 if (mid < b) update(Rr(o), mid+1, r, a, b, key); 60 sgm[o] = sgm[Lr(o)]+sgm[Rr(o)]; 61 } 62 int query(int o, int l, int r, int a, int b) { 63 if (a <= l && r <= b) return sgm[o]; 64 int mid = (l+r)>>1; 65 pushdown(o, l, r, mid); 66 int ca = 0, cb = 0; 67 if (a <= mid) ca = query(Lr(o), l, mid, a, b); 68 if (mid < b) cb = query(Rr(o), mid+1, r, a, b); 69 return ca+cb; 70 } 71 }T; 72 73 bool judge(int x) { 74 T.build(1, 1, n, x); 75 int l, r, cnt0, cnt1; 76 for (int i = 1; i <= m; i++) { 77 l = p[i].l, r = p[i].r; 78 cnt1 = T.query(1, 1, n, l, r); cnt0 = r-l+1-cnt1; 79 if (p[i].opt == 0) { 80 if (cnt0 != 0) T.update(1, 1, n, l, l+cnt0-1, 0); 81 if (cnt1 != 0) T.update(1, 1, n, l+cnt0, r, 1); 82 }else { 83 if (cnt1 != 0) T.update(1, 1, n, l, l+cnt1-1, 1); 84 if (cnt0 != 0) T.update(1, 1, n, l+cnt1, r, 0); 85 } 86 } 87 return T.query(1, 1, n, q, q) == 1; 88 } 89 void work() { 90 scanf("%d%d", &n, &m); 91 for (int i = 1; i <= n; i++) scanf("%d", &a[i]); 92 for (int i = 1; i <= m; i++) scanf("%d%d%d", &p[i].opt, &p[i].l, &p[i].r); 93 scanf("%d", &q); 94 int l = 1, r = n, ans; 95 while (l <= r) { 96 int mid = (l+r)>>1; 97 if (judge(mid)) l = mid+1, ans = mid; 98 else r = mid-1; 99 }100 printf("%d\n", ans);101 }102 int main() {103 work();104 return 0;105 }