网站论文首页布局技巧,google搜索引擎优化,wordpress自建站哪里换logo,做简历网站 39Tree
给定一棵树#xff0c;节点有点权#xff0c;然后有三种操作#xff1a;
一、修改1−s1-s1−s的路径上的点权与ttt进行按位或。
二、修改1−s1-s1−s的路径上的点权与ttt进行按位与。
三、查询1−s1-s1−s的路径上的点权异或和…Tree
给定一棵树节点有点权然后有三种操作
一、修改1−s1-s1−s的路径上的点权与ttt进行按位或。
二、修改1−s1-s1−s的路径上的点权与ttt进行按位与。
三、查询1−s1-s1−s的路径上的点权异或和是否为ttt。
可以考虑树剖然后对每一位维护一个010101线段树然后push_uppush\_uppush_up区间111的个数即可
对于按位或操作如果当前位为111则区间覆盖为111否则不做操作。
对于按位与操作如果当前位为000则区间覆盖为000否则不做操作。
整体来说只要对线段树维护一个区间覆盖lazylazylazy即可。
对于查询操作如果当前位上111的个数是奇数说明当前位对答案有贡献。
#include bits/stdc.h
#define mid (l r 1)
#define lson rt 1, l, mid
#define rson rt 1 | 1, mid 1, r
#define ls rt 1
#define rs rt 1 | 1using namespace std;const int N 1e5 10;int a[N], b[N], n, m;int head[N], to[N 1], nex[N 1], cnt 1;int son[N], fa[N], sz[N], dep[N], top[N], rk[N], id[N], tot;struct Tree {int sum[N 2], lazy[N 2];void push_up(int rt) {sum[rt] sum[ls] sum[rs];}void push_down(int rt, int l, int r) {if (lazy[rt] ! -1) {lazy[ls] lazy[rt], lazy[rs] lazy[rt];if (lazy[rt]) {sum[ls] mid - l 1, sum[rs] r - mid;}else {sum[ls] 0, sum[rs] 0;}lazy[rt] -1;}}void build(int rt, int l, int r) {lazy[rt] -1;if (l r) {sum[rt] b[rk[l]];return ;}build(lson);build(rson);push_up(rt);}void update(int rt, int l, int r, int L, int R, int v) {if (l L r R) {lazy[rt] v;if (v) {sum[rt] r - l 1;}else {sum[rt] 0;}return ;}push_down(rt, l, r);if (L mid) {update(lson, L, R, v);}if (R mid) {update(rson, L, R, v);}push_up(rt);}int query(int rt, int l, int r, int L, int R) {if (l L r R) {return sum[rt];}push_down(rt, l, r);int ans 0;if (L mid) {ans query(lson, L, R);}if (R mid) {ans query(rson, L, R);}return ans;}
}tree[30];void add(int x, int y) {to[cnt] y;nex[cnt] head[x];head[x] cnt;
}void dfs1(int rt, int f) {fa[rt] f, dep[rt] dep[f] 1, sz[rt] 1;for (int i head[rt]; i; i nex[i]) {if (to[i] f) {continue;}dfs1(to[i], rt);sz[rt] sz[to[i]];if (!son[rt] || sz[to[i]] sz[son[rt]]) {son[rt] to[i];}}
}void dfs2(int rt, int tp) {top[rt] tp, rk[tot] rt, id[rt] tot;if (!son[rt]) {return ;}dfs2(son[rt], tp);for (int i head[rt]; i; i nex[i]) {if (to[i] fa[rt] || to[i] son[rt]) {continue;}dfs2(to[i], to[i]);}
}typedef pairint, int pii;pii A[110];int num;void get_interval(int s) {num 0;while (top[s] ! 1) {A[num] make_pair(id[top[s]], id[s]);s fa[top[s]];}A[num] make_pair(id[1], id[s]);
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf(%d %d, n, m);for (int i 1; i n; i) {scanf(%d, a[i]);}for (int i 1, x, y; i n; i) {scanf(%d %d, x, y);add(x, y);add(y, x);}dfs1(1, 0);dfs2(1, 1);for (int k 0; k 30; k) {for (int i 1; i n; i) {b[i] a[i] k 1;}tree[k].build(1, 1, n);}for (int i 1, op, s, t; i m; i) {scanf(%d %d %d, op, s, t);get_interval(s);if (op 1) {for (int k 0; k 30; k) {if (t k 1) {for (int j 1; j num; j) {int l A[j].first, r A[j].second;tree[k].update(1, 1, n, l, r, 1);}}}}else if (op 2) {for (int k 0; k 30; k) {if (t k 1) {continue;}for (int j 1; j num; j) {int l A[j].first, r A[j].second;tree[k].update(1, 1, n, l, r, 0);}}}else {int ans 0;for (int k 0; k 30; k) {int cur 0;for (int j 1; j num; j) {int l A[j].first, r A[j].second;cur tree[k].query(1, 1, n, l, r);}if (cur 1) {ans | 1 k;}}puts(ans ! t ? YES : NO);}}return 0;
}
