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 <cstdio>
13 #include <algorithm>
14 #include <iostream>
15 #include <sstream>
16 #include <cstring>
17 #include <cmath>
18 #include <string>
19 #include <vector>
20 #include <queue>
21 #include <deque>
22 #include <stack>
23 #include <list>
24 #include <map>
25 #include <set>
26 #include <bitset>
27 #include <cstdlib>
28 #include <ctime>
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 Permutations
101 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) ? '
' : ' ');
126 }
127 }
128
129 return 0;
130 }
线段树+树状数组+贪心 HDOJ 5338 ZZX and Permutations
编译人生，运行世界！