Description
题库链接
给定一棵有 \(n\) 个节点的无根树和 \(m\) 个操作, 操作有 \(2\) 类:
将节点 \(a\) 到节点 \(b\) 路径上所有点都染成颜色 \(c\) ;
询问节点 \(a\) 到节点 \(b\) 路径上的颜色段数量 (连续相同颜色被认为是同一段)
Solution
线段树苟题因为没有下传 \(lazy\) 标记调了一上午
- Code
- //It is made by Awson on 2018.3.4
- #include <bits/stdc++.h>
- #define LL long long
- #define dob complex<double>
- #define Abs(a) ((a) < 0 ? (-(a)) : (a))
- #define Max(a, b) ((a) > (b) ? (a) : (b))
- #define Min(a, b) ((a) < (b) ? (a) : (b))
- #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
- #define writeln(x) (write(x), putchar('\n'))
- #define lowbit(x) ((x)&(-(x)))
- using namespace std;
- const int N = 1e5;
- void read(int &x) {
- char ch; bool flag = 0;
- for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
- for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
- x *= 1-2*flag;
- }
- void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }
- void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }
- int n, m, c[N+5], a[N+5], u, v, ca;
- struct tt {int to, next; }edge[(N<<1)+5];
- int path[N+5], Top;
- int size[N+5], id[N+5], son[N+5], top[N+5], dep[N+5], fa[N+5], pos;
- char ch[5];
- struct node {
- int l, r, cnt;
- node() {}
- node(int _l, int _r, int _cnt) {l = _l, r = _r, cnt = _cnt; }
- node operator + (const node &b) const {node tmp; tmp.l = l, tmp.r = b.r, tmp.cnt = cnt+b.cnt-(r==b.l); return tmp; }
- };
- struct Segment_tree {
- #define lr(o) (o<<1)
- #define rr(o) (o<<1|1)
- node sgm[(N<<2)+5]; int lazy[(N<<2)+5];
- void pushdown(int o) {sgm[lr(o)] = sgm[rr(o)] = sgm[o]; lazy[lr(o)] = lazy[rr(o)] = 1; lazy[o] = 0; }
- void build(int o, int l, int r) {
- if (l == r) {sgm[o] = node(a[l], a[l], 1); return; }
- int mid = (l+r)>>1;
- build(lr(o), l, mid); build(rr(o), mid+1, r); sgm[o] = sgm[lr(o)]+sgm[rr(o)];
- }
- node query(int o, int l, int r, int a, int b) {
- if (a <= l && r <= b) return sgm[o];
- if (lazy[o]) pushdown(o); int mid = (l+r)>>1;
- if (b <= mid) return query(lr(o), l, mid, a, b);
- if (a > mid) return query(rr(o), mid+1, r, a, b);
- return query(lr(o), l, mid, a, b)+query(rr(o), mid+1, r, a, b);
- }
- void update(int o, int l, int r, int a, int b, int col) {
- if (a <= l && r <= b) {sgm[o] = node(col, col, 1), lazy[o] = 1; return; }
- if (lazy[o]) pushdown(o); int mid = (l+r)>>1;
- if (a <= mid) update(lr(o), l, mid, a, b, col);
- if (b > mid) update(rr(o), mid+1, r, a, b, col);
- sgm[o] = sgm[lr(o)]+sgm[rr(o)];
- }
- }T;
- void add(int u, int v) {edge[++Top].to = v, edge[Top].next = path[u], path[u] = Top; }
- void dfs1(int o, int depth, int father) {
- dep[o] = depth, size[o] = 1, fa[o] = father;
- for (int i = path[o]; i; i = edge[i].next)
- if (dep[edge[i].to] == 0) {
- dfs1(edge[i].to, depth+1, o); size[o] += size[edge[i].to];
- if (size[edge[i].to] > size[son[o]]) son[o] = edge[i].to;
- }
- }
- void dfs2(int o, int tp) {
- id[o] = ++pos, a[pos] = c[o], top[o] = tp;
- if (son[o]) dfs2(son[o], tp);
- for (int i = path[o]; i; i = edge[i].next)
- if (edge[i].to != fa[o] && edge[i].to != son[o]) dfs2(edge[i].to, edge[i].to);
- }
- void update(int u, int v, int c) {
- while (top[u] != top[v]) {
- if (dep[top[u]] < dep[top[v]]) Swap(u, v);
- T.update(1, 1, n, id[top[u]], id[u], c);
- u = fa[top[u]];
- }
- if (dep[u] < dep[v]) Swap(u, v);
- T.update(1, 1, n, id[v], id[u], c);
- }
- int query(int u, int v) {
- node n1, n2; int f1 = 1, f2 = 1;
- while (top[u] != top[v]) {
- if (dep[top[u]] > dep[top[v]]) {
- if (f1) n1 = T.query(1, 1, n, id[top[u]], id[u]);
- else n1 = T.query(1, 1, n, id[top[u]], id[u])+n1;
- u = fa[top[u]]; f1 = 0;
- }else {
- if (f2) n2 = T.query(1, 1, n, id[top[v]], id[v]);
- else n2 = T.query(1, 1, n, id[top[v]], id[v])+n2;
- v = fa[top[v]]; f2 = 0;
- }
- }
- if (dep[u] > dep[v]) {
- if (f1) n1 = T.query(1, 1, n, id[v], id[u]);
- else n1 = T.query(1, 1, n, id[v], id[u])+n1; f1 = 0;
- }else {
- if (f2) n2 = T.query(1, 1, n, id[u], id[v]);
- else n2 = T.query(1, 1, n, id[u], id[v])+n2; f2 = 0;
- }
- if (f1) return n2.cnt;
- if (f2) return n1.cnt;
- Swap(n1.l, n1.r); n1 = n1+n2; return n1.cnt;
- }
- void work() {
- read(n), read(m); for (int i = 1; i <= n; i++) read(c[i]);
- for (int i = 1; i < n; i++) read(u), read(v), add(u, v), add(v, u);
- dfs1(1, 1, 0), dfs2(1, 1); T.build(1, 1, n);
- while (m--) {
- scanf("%s", ch);
- if (ch[0] == 'Q') read(u), read(v), writeln(query(u, v));
- else read(u), read(v), read(ca), update(u, v, ca);
- }
- }
- int main() {
- work(); return 0;
- }
[SDOI 2011] 染色
来源: http://www.bubuko.com/infodetail-2514728.html