bzoj1095: [ZJOI2007]Hide 捉迷藏 线段树维护括号序列 点分治 链分治

这题真是十分难写啊 不管是点分治还是括号序列都有一堆细节。。

 

点分治：时空复杂度$O(n\log^2n)$，常数巨大

主要就是3个堆的初始状态

C堆：每个节点一个，为子树中的点到它父亲的距离的堆。

B堆：每个节点一个，存所有儿子的堆的堆顶。特别地，如果该节点关灯，那么将加入一个0；如果没有元素，堆顶应返回负数。

A堆：全局一个，存所有B堆的最大值和最小值之和。特别地，如果B堆不足两个，返回负数。

这样，我们一开始需要关闭所有的等，即对所有点调用一次turn_off。由于堆顶返回的是负数，删除时找不到的话直接忽略即可，如果返回的是0，则有可能误删有用的信息。

 

代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 100000 + 10, logn = 17;

struct RMQ {
    int n, f[logn + 1][N * 2], Log[N * 2];
    void init(int n) {
        Log[0] = -1;
        for(int i = 1; i <= n; i++) Log[i] = Log[i >> 1] + 1;
        this->n = n;
        for(int i = 1; (1 << i) < n; i++) {
            for(int j = 1; j <= n; j++) {
                f[i][j] = min(f[i-1][j], f[i-1][j + (1 << (i-1))]);
            }
        }
    }

    int query(int l, int r) {
        int t = Log[r - l + 1];
        return min(f[t][l], f[t][r - (1 << t) + 1]);
    }
} rmq;

struct Edge {
    int to; Edge *next;
} pool[N * 2], *pis = pool, *fir[N];

void AddEdge(int u, int v) {
    pis->to = v, pis->next = fir[u], fir[u] = pis++;
}

int dfn[N], dfs_clock, *seq = rmq.f[0], dep[N], ds[N], tot;

#define v p->to
void dfs(int u, int fa) {
    dfn[u] = ++dfs_clock;
    seq[dfs_clock] = dep[u];
    for(Edge *p = fir[u]; p; p = p->next) {
        if(v != fa) {
            dep[v] = dep[u] + 1, dfs(v, u);
            seq[++dfs_clock] = dep[u];
        }
    }
    ds[tot++] = u;
}
#undef v

int dis(int u, int v) {
    if(dfn[u] > dfn[v]) swap(u, v);
    return dep[u] + dep[v] - (rmq.query(dfn[u], dfn[v]) << 1);
}
const int INF = 1 << 29;

struct Set {
    multiset<int> s;
    void insert(int x) {s.insert(x);}
    void erase(int x) {
        multiset<int>::iterator it = s.find(x);
        if(it != s.end()) s.erase(it);
    }
    int size() const {return s.size();}
    int top() {return s.empty() ? -INF : *--s.end();}
    int    query() {
        if(s.size() < 2) return -INF;
        return *--s.end() + *----s.end();
    }
} A, B[N], C[N];

    void print(const Set &ss) {
        const multiset<int> &s = ss.s;
        for(multiset<int>::iterator it = s.begin(); it != s.end(); ++it) {
            printf("%d ", *it);
        }
        puts("");
    }
bool centre[N];
int fa[N], maxsz[N], sz[N], root;

#define v p->to
void dfs_size(int u, int fa) {
    sz[u] = 1, maxsz[u] = 0;
    for(Edge *p = fir[u]; p; p = p->next) {
        if(!centre[v] && v != fa) {
            dfs_size(v, u);
            sz[u] += sz[v];
            maxsz[u] = max(maxsz[u], sz[v]);
        }
    }
}

void dfs_root(int u, int fa, int r) {
    maxsz[u] = max(maxsz[u], sz[r] - sz[u]);
    if(maxsz[u] < maxsz[root]) root = u;
    for(Edge *p = fir[u]; p; p = p->next) {
        if(!centre[v] && v != fa) dfs_root(v, u, r);
    }
}

void divide(int u, int _fa) {
    dfs_size(u, 0), dfs_root(u, 0, root = u);
    centre[u = root] = 1, fa[u] = _fa;
    for(Edge *p = fir[u]; p; p = p->next) {
        if(!centre[v]) divide(v, u);
    }
}
#undef v

void add(int u, int v, int flag) {
    if(u == v) {
        A.erase(B[u].query());
        if(flag) B[u].insert(0);
        else B[u].erase(0);
        A.insert(B[u].query());
    }
    int f = fa[u];
    if(!f) return;
    A.erase(B[f].query());
    B[f].erase(C[u].top());
    if(flag) C[u].insert(dis(f, v));
    else C[u].erase(dis(f, v));
    B[f].insert(C[u].top());
    A.insert(B[f].query());
    add(f, v, flag);
}

int col[N];

int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
#endif

    int n; scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        AddEdge(u, v), AddEdge(v, u);
    }
    dfs(1, 0);
    rmq.init((n << 1) - 1);
    divide(1, 0);
    int cnt_off = n;
    for(int i = 0; i < n; i++)
        add(ds[i], ds[i], col[ds[i]] = 1);
    
    int m, u; scanf("%d", &m);
    char opt[8];
    while(m--) {
        scanf("%s", opt);
        if(opt[0] == 'G') {
            if(cnt_off == 0) puts("-1");
            else if(cnt_off == 1) puts("0");
            else printf("%d\n", A.top());
        } else {
            scanf("%d", &u), add(u, u, col[u] ^= 1);
            if(col[u]) cnt_off++; else cnt_off--;
        }
    }

    return 0;
}

括号序列：时间复杂度$O(n\log n)$,空间复杂度$O(n)$

#include<bits/stdc++.h>

using namespace std;

const int N = 100000 + 10;

int col[N];
const int bracket[] = {-2, -1};

struct Data {
    /*
        0 : 从区间左起的
        [ x ] x的数量

        c[] 是左右括号的数量，而d[]和s[]必须保证旁边至少有一个满足条件的点
    */
    int c[2]; // [ )...) ] 或 [ (...( ]
    int d[2]; // [ )...) ] - [ (...( ] 或反过来
    int s[2]; // [ )...) ] + [ (...( ] 或反过来 
    int ans;

    void set(int x) {
        for(int i = 0; i < 2; i++) {
            c[i] = x == bracket[i];
            d[i] = s[i] = x > 0 && col[x] ? 0 : -(1 << 29);
            // 只有在x是满足条件的点的时候才把d[]和s[]赋为0，否则为-INF
        }
    }
};

void maxit(int &x, int y) {
    if(x < y) x = y;
}

// 实际上需要讨论lhs.c[1] 和 rhs.c[0]的大小
// 但是不合法的一定不是最优的，所以可以对两种情况直接取max
Data operator + (const Data &lhs, const Data &rhs) {
    static Data res;

    // update ans
    res.ans = max(lhs.ans, rhs.ans);
    maxit(res.ans, lhs.s[1] + rhs.d[0]);
    maxit(res.ans, lhs.d[1] + rhs.s[0]);

    // update s[]
    res.s[0] = max(lhs.s[0], rhs.s[0] - lhs.c[1] + lhs.c[0]); // lhs.c[1] >= rhs.c[0]
    res.s[0] = max(res.s[0], lhs.c[0] + lhs.c[1] + rhs.d[0]); // lhs.c[1] <= rhs.c[0]
    res.s[1] = max(rhs.s[1], lhs.s[1] - rhs.c[0] + rhs.c[1]); // rhs.c[1] >= lhs.c[0]
    res.s[1] = max(res.s[1], rhs.c[0] + rhs.c[1] + lhs.d[1]); // rhs.c[1] <= rhs.c[0]

    // update d[]
    res.d[0] = max(lhs.d[0], rhs.d[0] + lhs.c[1] - lhs.c[0]);
    res.d[1] = max(rhs.d[1], lhs.d[1] + rhs.c[0] - rhs.c[1]);

    // update c[] to update next s[] and d[]
    res.c[0] = lhs.c[0] + max(rhs.c[0] - lhs.c[1], 0);
    res.c[1] = rhs.c[1] + max(lhs.c[1] - rhs.c[0], 0);

    return res;
}

struct Edge {int to; Edge *next;} pool[N * 2], *pis = pool, *fir[N];
void AddEdge(int u, int v) {pis->to = v, pis->next = fir[u], fir[u] = pis++;}

int dfs_seq[N * 3], dfs_clock;

void dfs(int u, int fa) {
    col[u] = 1;
    dfs_seq[++dfs_clock] = bracket[1];
    dfs_seq[++dfs_clock] = u;
    for(Edge *p = fir[u]; p; p = p->next) {
        int v = p->to;
        if(v != fa) dfs(v, u);
    }
    dfs_seq[++dfs_clock] = bracket[0];
}

int pos[N];

struct SegmentTree {
    Data da[N * 12];
    void build(int s, int l, int r, int a[]) {
        if(l == r) {
            if(a[l] > 0) pos[a[l]] = s;
            return da[s].set(a[l]);
        }
        int mid = (l + r) >> 1;
        build(s << 1, l, mid, a), build(s << 1 | 1, mid + 1, r, a);
        da[s] = da[s << 1] + da[s << 1 | 1];
    }

    void modify(int x) {
        int s = pos[x]; da[s].set(x);
        while(s >>= 1) da[s] = da[s << 1] + da[s << 1 | 1];
    }
} seg;

int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
#endif

    int n; scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        AddEdge(u, v), AddEdge(v, u);
    }
    dfs(1, 0);
    seg.build(1, 1, n * 3, dfs_seq);

    int m; scanf("%d", &m);
    char opt[8]; int ans, x, cnt = n;
    while(m--) {
        scanf("%s", opt);
        if(opt[0] == 'G') {
            if(cnt >= 2) ans = seg.da[1].ans;
            else if(cnt == 1) ans = 0;
            else ans = -1;
            printf("%d\n", ans);
        } else {
            scanf("%d", &x);
            if(col[x] ^= 1) cnt++; else cnt--;
            seg.modify(x);
        }
    }

    return 0;
}

链分治：时间复杂度$O(n\log^2n)$,空间复杂度$O(n)$ 比点分治快多啦

notice：合并两个线段树节点的时候如果使用=赋值可能丢失儿子信息。

#include<bits/stdc++.h>

using namespace std;

const int N = 100000 + 10, INF = 1 << 29;

struct Set {
    multiset<int> s;
    void erase(int x) {assert(s.find(x) != s.end()), s.erase(s.find(x));}
    void insert(int x) {s.insert(x);}
    int top() const {return s.empty() ? -INF : *--s.end();}
    int query() const {
        if(s.size() < 2) return -INF;
        return *--s.end() + *----s.end();
    }
} heap[N], st;

void print(const Set &ss) {
    const multiset<int> &s = ss.s;
    for(multiset<int>::iterator it = s.begin(); it != s.end(); ++it) {
        printf("%d ", *it);
    }
    puts("");
}

struct Edge {
    int to, w;
    Edge *next;
} pool_edges[N * 2], *fir[N], *pe = pool_edges;

void AddEdge(int u, int v, int w) {
    pe->to = v, pe->w = w, pe->next = fir[u], fir[u] = pe++;
}

int sz[N], top[N], dis[N], son[N], fa[N], dfs_clock, seq[N], dfn[N], end[N], col[N];

#define mid ((l + r) >> 1)
struct Node {
    int L, R, ans;
    Node *ch[2];

    void set(int u) {
        ans = heap[u].query();
        L = R = heap[u].top();
    }

    void modify(int l, int r, int p);

} pool_nodes[N * 3], *pn = pool_nodes, *rt[N];

void print(Node *o, int l, int r) {
    printf("[%d, %d] : L = %d, R = %d, ans = %d\n", l, r, o->L, o->R, o->ans);
    if(l != r) print(o->ch[0], l, mid), print(o->ch[1], mid + 1, r);
}
void merge(Node &res, const Node &lhs, const Node &rhs, int l, int r) {
    res.ans = max(lhs.ans, rhs.ans);
    res.ans = max(res.ans, lhs.R + dis[seq[mid + 1]] - dis[seq[mid]] + rhs.L);

    res.L = max(lhs.L, dis[seq[mid + 1]] - dis[seq[l]] + rhs.L);
    res.R = max(rhs.R, dis[seq[r]] - dis[seq[mid]] + lhs.R);
}

void Node::modify(int l, int r, int p) {
    if(l == r) return set(seq[p]);
    if(p <= mid) ch[0]->modify(l, mid, p);
    else ch[1]->modify(mid + 1, r, p);
    merge(*this, *ch[0], *ch[1], l, r);
}

Node *build(int l, int r) {
    Node *o = pn++;
    if(l == r) o->set(seq[l]);
    else {
        o->ch[0] = build(l, mid);
        o->ch[1] = build(mid + 1, r);
        merge(*o, *o->ch[0], *o->ch[1], l, r);
    }
    return o;
}
#undef mid

#define v it->to
void dfs_size(int u) {
    sz[u] = 1, col[u] = 1;
    for(Edge *it = fir[u]; it; it = it->next) {
        if(v != fa[u]) {
            dis[v] = dis[u] + it->w;
            fa[v] = u;
            dfs_size(v);
            sz[u] += sz[v];
            if(sz[v] > sz[son[u]]) son[u] = v;
        }
    }
}

void dfs_build(int u, int pre) {
    seq[dfn[u] = ++dfs_clock] = u;
    top[u] = pre;
    end[pre] = max(end[pre], dfn[u]);
    if(son[u]) dfs_build(son[u], pre);
    for(Edge *it = fir[u]; it; it = it->next) {
        if(v != fa[u] && v != son[u]) {
            dfs_build(v, v);
            heap[u].insert(rt[v]->L + dis[v] - dis[u]);
        }
    }

    heap[u].insert(0);
    if(top[u] == u) {
        rt[u] = build(dfn[u], end[u]);
        st.insert(rt[u]->ans);
    }
}
#undef v

void modify(int u) { 
    static int anc[20], tot;
    tot = 0;
    for(int t = u; t; t = fa[top[t]]) anc[tot++] = t;

    for(int i = tot-1; i >= 0; i--) {
        st.erase(rt[top[anc[i]]]->ans);
        if(i) heap[anc[i]].erase(rt[top[anc[i-1]]]->L + dis[top[anc[i-1]]] - dis[anc[i]]);
    }
    if(col[u]) heap[u].insert(0);
    else heap[u].erase(0);

    for(int i = 0; i < tot; i++) {
        int x = anc[i], t = top[x];
        rt[t]->modify(dfn[t], end[t], dfn[x]);
        st.insert(rt[t]->ans);
        if(i+1 < tot) heap[anc[i+1]].insert(rt[t]->L + dis[t] - dis[anc[i+1]]);
    }
}

int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
#endif
    int n; scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        AddEdge(u, v, 1), AddEdge(v, u, 1);
    }
    dfs_size(1);
    dfs_build(1, 1);

    int m; scanf("%d", &m);
    char opt[8]; int u, tot = n;
    while(m--) {
        scanf("%s", opt);
        if(opt[0] == 'G') {
            int ans;
            if(tot == 0) ans = -1;
            else if(tot == 1) ans = 0;
            else ans = st.top();
            printf("%d\n", ans);
        } else {
            scanf("%d", &u);
            if(!(col[u] ^= 1)) tot--; else tot++;
            modify(u);
            
        }
    }
}