大作死（[UOJ 186] [UR #13] Yist）
话说某日无聊决定不看题解水一发 UOJ Round A……
首先来一发好像是 O(n3) 大暴力（不过能通过 60 分？还是复杂度又分析错了 = =）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <cstdio>#include <cstring>static const int MAXN = 1004;inline int min(int a, int b) { return a < b ? a : b; }inline int max(int a, int b) { return a > b ? a : b; }int n;int a[MAXN], a_id[MAXN];bool b[MAXN], b_id[MAXN];inline int get_rg_min(int *a, int n, int l, int r){ if (l < 0 || r >= n) return -233; int ans = a[l]; for (++l; l <= r; ++l) ans = min(ans, a[l]); return ans;}bool check(int x){ static int c[MAXN]; memcpy(c, a, sizeof a); int ct = ::n; for (int i = 1; i <= n; ++i) if (!b_id[i]) { for (int j = 0; j < ct; ++j) if (c[j] == i) { bool valid = false; for (int k = 0; k < x; ++k) if (get_rg_min(c, ct, j - k, j - k + x - 1) == i) { valid = true; break; } if (!valid) return false; for (; j < ct - 1; ++j) c[j] = c[j + 1]; } --ct; } return true;}void solve(){ int hi = n + 1, lo = 1, mid; while (lo < hi - 1) { mid = (lo + hi) >> 1; if (check(mid)) lo = mid; else hi = mid; } printf("%d\n", lo);}int main(){ scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); a_id[a[i]] = i; } int q; scanf("%d", &q); getchar(); do { for (int i = 0; i <= n; ++i) { b[i] = (getchar() == '1'); b_id[a[i]] = b[i]; } solve(); } while (--q); return 0;} |
然后开始脑补名次树……用名次树来加速检查……顺带搞了个单调队列区间最小值 = =
作死用 Splay 写名次树搞得代码巨长 _(:_」∠)_ 这←_←
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 | #include <cstdio>#include <cstring>#include <utility>static const int MAXN = 1000004;inline int min(int a, int b) { return a < b ? a : b; }inline int max(int a, int b) { return a > b ? a : b; }int n;int a[MAXN], a_id[MAXN];bool b[MAXN], b_id[MAXN];int b_ct;struct spl_node { int size; int child[2], parent; spl_node() { } spl_node(int p) : size(1), parent(p) { child[0] = child[1] = -1; }} t[MAXN];int spl_size = 1;inline void spl_update(int idx){ t[idx].size = 1; if (t[idx].child[0] != -1) t[idx].size += t[t[idx].child[0]].size; if (t[idx].child[1] != -1) t[idx].size += t[t[idx].child[1]].size;}int spl_build(int l, int r, int p = 0){ if (l > r) return -1; int m = (l + r) >> 1; int idx = a[m]; t[idx].parent = p; if (l == r) { t[idx].child[0] = t[idx].child[1] = -1; t[idx].size = 1; } else { t[idx].child[0] = spl_build(l, m - 1, idx); t[idx].child[1] = spl_build(m + 1, r, idx); spl_update(idx); } return idx;}inline void spl_rotate(int i, int d){ int p = t[i].parent, g = t[p].parent; t[p].child[d] = t[i].child[1 - d]; t[t[i].child[1 - d]].parent = p; t[i].child[1 - d] = p; t[p].parent = i; t[g].child[t[g].child[1] == p] = i; t[i].parent = g; spl_update(p); spl_update(i);}inline void spl_zig(int idx) { spl_rotate(idx, 0); }inline void spl_zag(int idx) { spl_rotate(idx, 1); }inline void spl_1splay(int idx) { spl_rotate(idx, t[t[idx].parent].child[1] == idx); }inline void spl_2splay(int idx, int under){ int par = t[idx].parent, gpn = t[par].parent; if (gpn == under) spl_1splay(idx); else { if (t[gpn].child[0] == par) { if (t[par].child[0] == idx) { spl_zig(par); spl_zig(idx); } else { spl_zag(idx); spl_zig(idx); } } else { if (t[par].child[0] == idx) { spl_zig(idx); spl_zag(idx); } else { spl_zag(par); spl_zag(idx); } } }}inline void spl_lift(int idx, int under = 0){ while (t[idx].parent != under) spl_2splay(idx, under);}int spl_getrank(int idx){ int ans = (t[idx].child[0] == -1 ? 0 : t[t[idx].child[0]].size); while (idx != 0) { while (idx != 0 && t[t[idx].parent].child[0] == idx) idx = t[idx].parent; if (idx == 0) break; idx = t[idx].parent; if (t[idx].child[0] != -1) ans += t[t[idx].child[0]].size; ans += 1; // Current node } return ans;}int spl_atrank(int rank){ int idx = t[0].child[0], lst_size; while (1) { lst_size = (t[idx].child[0] == -1 ? 0 : t[t[idx].child[0]].size); if (rank == lst_size) return idx; else if (rank < lst_size) idx = t[idx].child[0]; else { idx = t[idx].child[1]; rank -= (lst_size + 1); } } // Should never get here}void spl_remove(int idx){ int rk = spl_getrank(idx); int n1 = spl_atrank(rk - 1), n2 = spl_atrank(rk + 1); spl_lift(n1, 0); spl_lift(n2, t[0].child[0]); t[n2].child[0] = -1; spl_update(n2); spl_update(n1);}inline void spl_reset(){ spl_size = 1; t[0].child[0] = spl_build(0, n - 1); t[0].child[1] = -1; spl_lift(spl_atrank(n - 1)); t[MAXN - 2] = spl_node(t[0].child[0]); t[t[0].child[0]].child[1] = MAXN - 2; spl_lift(spl_atrank(0)); t[MAXN - 1] = spl_node(t[0].child[0]); t[t[0].child[0]].child[0] = MAXN - 1; //spl_lift(spl_atrank(n / 2)); <- Balance the tree}inline int window_min(int l, int r, int w){ int ans = 0; // first -> index, second -> value static std::pair<int, int> q[MAXN]; int qhead = 0, qtail = 0; for (int i = l; i <= r; ++i) { int val = spl_atrank(i); while (qhead != qtail && q[qhead - 1].second > val) --qhead; q[qhead++] = std::make_pair(i, val); if (q[qtail].first == i - w) ++qtail; if (i >= l + w - 1) ans = max(ans, q[qtail].second); } return ans;}bool check(int x){ spl_reset(); int ct = ::n; for (int i = 1; i <= n; ++i) if (!b_id[i]) { int j = spl_getrank(i); if (window_min(max(j - x + 1, 1), min(j + x - 1, ct), x) != i) return false; spl_remove(i); --ct; } return true;}void solve(){ int hi = b_ct + 2, lo = 1, mid; while (lo < hi - 1) { mid = (lo + hi) >> 1; if (check(mid)) lo = mid; else hi = mid; } printf("%d\n", lo);}int main(){ scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); a_id[a[i]] = i; } int q; scanf("%d", &q); getchar(); do { b_ct = 0; for (int i = 0; i <= n; ++i) { b[i] = (getchar() == '1'); b_id[a[i]] = b[i]; b_ct += b[i]; } solve(); } while (--q); return 0;} |
然后杯具地发现大样例 TLE……杯具 60 分……（手动再见
然后晚自习就下课……了…………←_←
真是充实的一个晚上
UPD
终于弃疗看题解啦
“使用平衡树等数据结构优化算法二，时间复杂度 O(qnlog2n)，由于常数大可能较难通过90分的数据。”
可能较难通过
可能较难
嗯就是这样 = =
评论 (0)