本文主要是介绍【codeforces 620E】【dfs】【线段树 】【lazy】【子树区间修改,区间求和】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://codeforces.com/problemset/problem/620/E
【题意】
子树区间修改,区间求和
【分析】先将树形结构通过dfs序转化为线性结构，子树的操作转化为线性区间上的操作，加个2进制ll存储val,lazy标记更新
【代码】
好久没写线段树了，呜呜呜
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 6;
int c[maxn], pos[maxn];
vector<int>v[maxn];//线段树部分----------------------------------------------------------
struct node {int l, r;ll val;int lazy;int mid(void) {return l + r >> 1;}
}tr[maxn<<2];void pushDown(int p) {if (tr[p].lazy) {tr[p << 1].lazy = tr[p << 1 | 1].lazy = tr[p].lazy;tr[p << 1 | 1].val = tr[p << 1].val = 1LL << tr[p].lazy;tr[p].lazy = 0;}
}void build(int p, int l,int r) {tr[p].l = l;tr[p].r = r;tr[p].lazy = 0;tr[p].val = 0;if (l == r) {tr[p].val = 1LL << c[pos[l]];return;}int mid = tr[p].mid();build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);tr[p].val = tr[p << 1].val | tr[p << 1 | 1].val;
}void update(int p, int l, int r, int L, int R, int x) {if (L <= tr[p].l&&tr[p].r <= R) {tr[p].lazy = x;tr[p].val = 1LL << x;return;}pushDown(p);int mid = tr[p].mid();if (L <= mid)update(p << 1, l, mid, L, R, x);if (R > mid)update(p << 1 | 1, mid + 1, r, L, R, x);tr[p].val = tr[p << 1].val | tr[p << 1 | 1].val;
}ll query(int p, int l, int r, int L,int R) {if (L <= l && r <= R) {return tr[p].val;}pushDown(p);int mid = tr[p].mid();ll res = 0;if (L <= mid)res |= query(p << 1, l, mid, L, R);if (R > mid)res |= query(p << 1 | 1, mid + 1, r, L, R);tr[p].val = tr[p << 1].val | tr[p << 1 | 1].val;return res;
}//dfs部分---------------------------------------------------------------
int dfsL[maxn], dfsR[maxn];
int tot = 0;
//获得每个节点1->tot的编号
void dfs(int p, int f ) {//L,R表示一个子树的范围dfsL[p] = ++tot;pos[tot] = p;for (int q : v[p]) {if (q == f)continue;dfs(q, p);}dfsR[p] = tot;
}int main() {int n, m;while (~scanf("%d%d", &n, &m)) {for (int i = 1; i <= n; i++) {scanf("%d", &c[i]);v[i].clear();}for (int i = 1; i < n; i++) {int x, y;scanf("%d%d", &x, &y);v[x].push_back(y);v[y].push_back(x);}dfs(1, 0);build(1, 1, n);while (m--) {int op;scanf("%d", &op);if (op == 1) {int v, x;scanf("%d%d", &v, &x);update(1, 1, n, dfsL[v], dfsR[v], x);}else {int v;scanf("%d", &v);ll ans = query(1, 1, n, dfsL[v], dfsR[v]);printf("%d\n", bitset<1000>(ans).count());}}}
}
这篇关于【codeforces 620E】【dfs】【线段树 】【lazy】【子树区间修改,区间求和】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
