话说某日无聊决定不看题解水一发 UOJ Round A……

首先来一发好像是 $O(n^3)$ 大暴力（不过能通过 60 分？还是复杂度又分析错了 = =）

#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 写名次树搞得代码巨长 _(:_」∠)_ 这←_←

#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(qn \log^2 n)$${}^{\mathrm{}}$，由于常数大可能较难通过90分的数据。”

可能较难通过

可能较难

嗯就是这样 = =