社区讨论
各位大佬,我想问下我瞎写的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 条回复,欢迎继续交流。
正在加载回复...