1 /**************************************************************  2     Problem: 3173  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:660 ms  7     Memory:3936 kb  8 ****************************************************************/  9   10 #include <cstdlib> 11 #include <cstdio> 12 #include <cstring> 13 #include <algorithm> 14   15 using namespace std; 16 const int N = 100005; 17 const int inf = 1e9; 18   19 struct treap_node { 20   treap_node *son[2]; 21   int pri, sz, v; 22 } *null, *root, mempool[N], *cnt_treap = mempool; 23   24 int n, cnt, len; 25 int a[N], ans[N], mn[N]; 26   27 int read() { 28   int x = 0; 29   char ch = getchar(); 30   while (ch < ‘0‘ || ‘9‘ < ch) 31     ch = getchar(); 32   while (‘0‘ <= ch && ch <= ‘9‘) 33     (x *= 10) += ch - ‘0‘, ch = getchar(); 34   return x; 35 } 36   37 #define Ls (p -> son[0]) 38 #define Rs (p -> son[1]) 39 #define Pri (p -> pri) 40 #define Sz (p -> sz) 41 #define V (p -> v) 42 inline void treap_update(treap_node *p) { 43   Sz = Ls -> sz + Rs -> sz + 1; 44 } 45   46 void treap_rotate(treap_node *&p, int ch) { 47   treap_node *tmp = p -> son[ch]; 48   p -> son[ch] = tmp -> son[!ch]; 49   tmp -> son[!ch] = p; 50   treap_update(p), treap_update(tmp); 51   p = tmp; 52 } 53   54 void treap_insert(treap_node *&p, int rank) { 55   if (p == null) { 56     p = ++cnt_treap, Ls = Rs = null; 57     Pri = rand(), Sz = 1, V = cnt; 58     return; 59   } 60   ++Sz; 61   if (Ls -> sz < rank) { 62     treap_insert(Rs, rank - Ls -> sz - 1); 63     if (Rs -> pri > Pri) treap_rotate(p, 1); 64   } else { 65     treap_insert(Ls, rank); 66     if (Ls -> pri > Pri) treap_rotate(p, 0); 67   } 68 } 69   70 void get_seq(treap_node *p) { 71   if (p == null) return; 72   get_seq(Ls); 73   a[++cnt] = V; 74   get_seq(Rs); 75 } 76 #undef Ls 77 #undef Rs 78 #undef Pri 79 #undef Sz 80 #undef Num 81   82 int main() { 83   int i, t; 84   n = read(); 85   null = ++cnt_treap; 86   null -> son[0] = null -> son[1] = null; 87   null -> pri = null -> sz = null -> v = 0; 88   root = null; 89   for (cnt = 1; cnt <= n; ++cnt) 90     treap_insert(root, read()); 91   cnt = 0; 92   get_seq(root); 93   memset(mn, 127, sizeof(mn)); 94   for (mn[0] = -inf, i = 1; i <= n; ++i) { 95     t = upper_bound(mn, mn + len + 1, a[i]) - mn; 96     if (mn[t - 1] <= a[i]) { 97       mn[t] = min(mn[t], a[i]); 98       ans[a[i]] = t; 99       len = max(t, len);100     }101   }102   for (i = 1; i <= n; ++i)103     printf("%d\n", ans[i] = max(ans[i], ans[i - 1]));104   return 0;105 }

 1 /************************************************************** 2     Problem: 3173 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:248 ms 7     Memory:3540 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13  14 #define lowbit(x) (x & -x)15 using namespace std;16 const int N = 100005;17 const int inf = 1e9;18 const int Maxlen = N * 8;19    20 int n, len;21 int a[N], ans[N], mn[N];22 int bit[N], b[N];23 char buf[Maxlen], *c = buf;24 int Len;25  26 inline int read() {27   int x = 0;28   while (*c < ‘0‘ || ‘9‘ < *c) ++c;29   while (‘0‘ <= *c && *c <= ‘9‘)30     x = x * 10 + *c - ‘0‘, ++c;31   return x;32 }33  34 void print(int x) {35   if (x >= 10) print(x / 10);36   putchar(x % 10 + ‘0‘);37 }38  39 inline int get_kth(int k) {40   int res = 0, cnt = 0, i;41   for (i = 20; ~i; --i) {42     res += 1 << i;43     if (res >= n || cnt + bit[res] >= k) res -= 1 << i;44     else cnt += bit[res];45   }46   return res + 1;47 }48  49 inline void bit_del(int x) {50   while (x <= n)51     --bit[x], x += lowbit(x);52 }53  54 int main() {55   Len = fread(c, 1, Maxlen, stdin);56   buf[Len] = ‘\0‘;57   int i, t, w, mx;58   n = read();59   for (i = 1; i <= n; ++i) {60     b[i] = read(), ++bit[i];61     if (i + lowbit(i) <= n)62       bit[i + lowbit(i)] += bit[i];63   }64   for (i = n; i; --i) {65     a[w = get_kth(b[i] + 1)] = i;66     bit_del(w);67   }68   memset(mn, 127, sizeof(mn));69   for (mn[0] = -inf, i = 1; i <= n; ++i) {70     t = upper_bound(mn, mn + len + 1, a[i]) - mn;71     if (mn[t - 1] <= a[i]) {72       mn[t] = min(mn[t], a[i]);73       ans[a[i]] = t;74       len = max(t, len);75     }76   }77   for (i = 1, mx = 0; i <= n; ++i) {78     if (ans[i] > mx) mx = ans[i];79     print(mx);80     putchar(‘\n‘);81   }82   return 0;83 }