线段树+树状数组+贪心 HDOJ 5338 ZZX and Permutations-白红宇

线段树+树状数组+贪心 HDOJ 5338 ZZX and Permutations

阅读量：6428 次

发布时间：2019-06-23

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

1 /*  2     题意：不懂。。。  3     线段树+树状数组+贪心：贪心从第一位开始枚举，一个数可以是循环节的末尾或者在循环节中，循环节(循环节内部是后面的换到前面，最前面的换到最后面)。线段树维护最大值，树状数组维护区间是否是循环节，查找前面最左边不是循环节的可用二分。我还是云里雾里的，看懂了网上的解题报告但还是不是完全明白题意:(  4     详细解释：http://blog.csdn.net/qq_24451605/article/details/47173933  5 */  6 /************************************************  7 Author        :Running_Time  8 Created Time  :2015-8-1 9:31:45  9 File Name     :L.cpp 10 *************************************************/ 11  12 #include 
     
       13 #include 
      
        14 #include 
       
         15 #include 
        
          16 #include 
         
           17 #include 
          
            18 #include 
           
             19 #include 
            
              20 #include 
             
               21 #include 
              
                22 #include 
               
                 23 #include 
                
                  24 #include 
                  25 #include 
                  
                    26 #include 
                   
                     27 #include 
                    
                      28 #include 
                     
                       29 using namespace std; 30 31 #define lson l, mid, rt << 1 32 #define rson mid + 1, r, rt << 1 | 1 33 typedef long long ll; 34 const int MAXN = 1e5 + 10; 35 const int INF = 0x3f3f3f3f; 36 const int MOD = 1e9 + 7; 37 int a[MAXN], pos[MAXN], ans[MAXN]; 38 int n; 39 struct Segment_Tree { 40 int mx[MAXN<<2]; 41 void push_up(int rt) { 42 mx[rt] = max (mx[rt<<1], mx[rt<<1|1]); 43 } 44 void build(int l, int r, int rt) { 45 if (l == r) { 46 mx[rt] = a[l]; return ; 47 } 48 int mid = (l + r) >> 1; 49 build (lson); build (rson); 50 push_up (rt); 51 } 52 void updata(int p, int l, int r, int rt) { 53 if (l == r) { 54 mx[rt] = -a[l]; return ; 55 } 56 int mid = (l + r) >> 1; 57 if (p <= mid) updata (p, lson); 58 else updata (p, rson); 59 push_up (rt); 60 } 61 int query(int ql, int qr, int l, int r, int rt) { 62 if (ql <= l && r <= qr) { 63 return mx[rt]; 64 } 65 int mid = (l + r) >> 1; int ret = -INF; 66 if (ql <= mid) ret = max (ret, query (ql, qr, lson)); 67 if (qr > mid) ret = max (ret, query (ql, qr, rson)); 68 return ret; 69 } 70 }st; 71 struct BIT { 72 int c[MAXN]; 73 void init(void) { 74 memset (c, 0, sizeof (c)); 75 } 76 void updata(int i, int x) { 77 while (i <= n) { 78 c[i] += x; i += i & (-i); 79 } 80 } 81 int query(int i) { 82 int ret = 0; 83 while (i) { 84 ret += c[i]; i -= i & (-i); 85 } 86 return ret; 87 } 88 }bit; 89 90 int my_binary_search(int l, int r) { 91 int t = r; 92 while (l != r) { 93 int mid = (l + r) >> 1; 94 if (bit.query (t) - bit.query (mid) > 0) l = mid + 1; 95 else r = mid; 96 } 97 return l + 1; 98 } 99 100 int main(void) { //HDOJ 5338 ZZX and Permutations101 int T; scanf ("%d", &T);102 while (T--) {103 scanf ("%d", &n);104 for (int i=1; i<=n; ++i) {105 scanf ("%d", &a[i]); pos[a[i]] = i;106 }107 st.build (1, n, 1); bit.init ();108 for (int i=1; i<=n; ++i) {109 int p = pos[i];110 if (bit.query (p) - bit.query (p-1) > 0) {111 ans[i] = a[p+1]; continue;112 }113 int v1 = -1;114 if (p != n && bit.query (p+1) - bit.query (p) == 0) v1 = a[p+1];115 int l = my_binary_search (0, p);116 int v2 = st.query (l, p, 1, n, 1); int p2 = pos[v2];117 if (v2 > v1) {118 ans[i] = v2; for (int i=p2; i<=p; ++i) bit.updata (i, 1);119 }120 else {121 ans[i] = v1; st.updata (p + 1, 1, n, 1);122 }123 }124 for (int i=1; i<=n; ++i) {125 printf ("%d%c", ans[i], (i == n) ? '\n' : ' ');126 }127 }128 129 return 0;130 }