社区讨论

各位大佬,我想问下我瞎写的zkw线段树这样做有问题吗?

P3950部落冲突参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo2e642o
此快照首次捕获于
2023/10/23 12:22
2 年前
此快照最后确认于
2023/11/03 12:29
2 年前
查看原帖
CPP
#include <iostream>
#include <bits/stdc++.h>

using namespace std;
template <typename type>
inline void read(type& x){
    x = 0; bool f = 0; char c = getchar();
    while(c < '0' || c > '9'){f = c == '-'; c = getchar();}
    while(c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
    if(f) x = -x;
}

const int maxN = 3E5 + 5;
int head[maxN], dfn[maxN], fa[maxN], son[maxN], sz[maxN], depth[maxN], top[maxN];
int history[maxN];
int k = 0, cnt = 0, m = 1;
bool tree[maxN << 2];
struct edge{
    int to, next;
    edge(int to = 0, int next = -1):to(to), next(next){}
}edges[maxN << 1];

inline void add(int u, int v){
    edges[k] = edge(v, head[u]);
    head[u] = k++;
}

inline void dfs1(int now, int f){
    fa[now] = f;
    depth[now] = depth[f] + 1;
    sz[now] = 1;
    int maxS = -1;
    for(int e = head[now]; ~e; e = edges[e].next){
        if(edges[e].to == f) continue;
        dfs1(edges[e].to, now);
        sz[now] += sz[edges[e].to];
        if(sz[edges[e].to] > maxS){
            maxS = sz[edges[e].to];
            son[now] = edges[e].to;
        }
    }
}

inline void dfs2(int now, int topf){
    top[now] = topf;
    dfn[now] = ++cnt;
    if(!son[now]) return;
    dfs2(son[now], topf);
    for(int e = head[now]; ~e; e = edges[e].next){
        if(dfn[edges[e].to]) continue;
        dfs2(edges[e].to, edges[e].to);
    }
}

inline void updata(int x, bool t){
    x += m; tree[x] = t; x >>= 1;
    while(x){
        tree[x] = tree[x << 1] & tree[x << 1 | 1];
        x >>= 1;
    }
}
//查询,l的右兄弟在区间内,r的左兄弟在区间内,除了单点l和r,不查询l和r本身
inline bool queryRange(int l, int r){
    if(l > r) return true;
    l += m, r += m;
    if(l == r) return tree[l];
    if(!tree[l] || !tree[r]) return false;
    while(l ^ r ^ 1){
        if((~l & 1) && !tree[l ^ 1]) return false;
        if((r & 1) && !tree[r ^ 1]) return false;
        l >>= 1;
        r >>= 1;
    }
    return true;
}

inline void query(int u, int v){
    bool res = 1;
    while(top[u] != top[v]){
        if(depth[top[u]] < depth[top[v]]) swap(u, v);
        res &= queryRange(dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if(dfn[u] > dfn[v]) swap(u, v);
    res &= queryRange(dfn[u] + 1, dfn[v]);
    if(res){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
}

int main(){
    int n, q, u, v;
    char type;
    read(n), read(q);
    memset(dfn, 0, sizeof(int) * (n + 1));
    memset(head, -1, sizeof(int) * (n + 1));
    memset(son, 0, sizeof(int) * (n + 1));
    memset(tree, 1, sizeof(tree));
    while(m <= n) m <<= 1;
    for(int i = 0; i < n - 1; i++){
        read(u), read(v);
        add(u, v);
        add(v, u);
    }
    depth[0] = 0;
    dfs1(1, 0);
    dfs2(1, 1);
    k = 0;
    for(int i = 0; i < q; i++){
        cin >> type;
        if(type == 'Q'){
            read(u), read(v);
            query(u, v);
        }
        else if(type == 'C'){
            read(u), read(v);
            history[++k] = max(dfn[u], dfn[v]);
            updata(history[k], 0);
        }
        else if(type == 'U'){
            read(u);
            updata(history[u], 1);
        }
    }
    return 0;
}
这几天刚学的zkw线段树,虽然a了,但是我还是不太懂zkw线段树如何处理除了加减覆盖求最值之外的操作

回复

0 条回复,欢迎继续交流。

正在加载回复...