专栏文章

题解 - CF2152G Query Jungle

hhopeful_imitation
CF2152G题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minpinq6
此快照首次捕获于
2025/12/02 06:14
3 个月前
此快照最后确认于
2025/12/02 06:14
3 个月前
查看原文
如果不放在 G 题，是不是一切都会不一样了？

简述题意

给一棵树，每个点有一个 01 变量 bib_i。qq 次修改，每次给某个子树的 bib_i 取反。每次求解最少的路径条数满足：
  • 都有 11 这个根作为端点；
  • 所有 bp=1b_p=1 的 pp 都在至少一条路径上。
n,q≤2.5×105n, q\le 2.5\times 10^5。

解法

考虑策略，是对每个 bp=1∧∑q∈subtree(p)bq=1b_p=1\land \sum_{q\in\text{subtree}(p)} b_q=1 的 pp，都建立一个 1→p1\to p 的路径。这个的最优性证明就是考虑任意两个满足上述条件的点 s,ts,t，它们无法被同一条路径覆盖，那么此方案达到了下界。
考虑用括号序表达这个性质。建立括号序，只保留 bp=1b_p=1 的 pp 的括号，那么上面的条件就直接对应一个子串 ()，而这个用线段树维护是容易的。复杂度 O(n+qlog⁡n)O(n+q\log n)。

主要代码

CPP
const int MXN = 250005;
const int MXL = MXN * 2;
int N, Q, init_col[MXN];
int li[MXN], ri[MXN], did;
bool typ[MXL], init_app[MXL];
bool tag[MXL * 4];
vector<int> adj[MXN];

struct Node {
  int lc, rc, pr;
  Node(int x=-1) : lc(x), rc(x), pr(0) {}
} node[MXL * 4][2];
inline Node operator+(Node x, Node y) {
  if (x.lc == -1) return y;
  if (y.lc == -1) return x;
  Node z;
  z.lc = x.lc, z.rc = y.rc, z.pr = x.pr + y.pr + (x.rc == 0 && y.lc == 1);
  return z;
}

void pre(int p, int f) {
  li[p] = did++;
  for (int q : adj[p]) if (q ^ f) pre(q, p);
  ri[p] = did++;
  typ[li[p]] = 0, typ[ri[p]] = 1;
  init_app[li[p]] = init_app[ri[p]] = init_col[p];
}

inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
inline void pushup(int p) {
  node[p][0] = node[ls(p)][0] + node[rs(p)][0];
  node[p][1] = node[ls(p)][1] + node[rs(p)][1];
}
inline void flip(int p) {
  swap(node[p][0], node[p][1]);
  tag[p] = !tag[p];
}
inline void pushdown(int p) {
  if (tag[p]) flip(ls(p)), flip(rs(p)), tag[p] = false;
}
void build(int p, int l, int r) {
  tag[p] = false;
  if (r - l == 1) {
    node[p][init_app[l]] = {typ[l]};
    node[p][!init_app[l]] = {-1};
    return;
  }
  int m((l + r) >> 1);
  build(ls(p), l, m), build(rs(p), m, r);
  pushup(p);
}
void flip(int p, int l, int r, int tl, int tr) {
  if (l >= tl && r <= tr) return flip(p);
  if (l >= tr || r <= tl) return;
  pushdown(p);
  int m((l + r) >> 1);
  flip(ls(p), l, m, tl, tr);
  flip(rs(p), m, r, tl, tr);
  pushup(p);
}

void work() {
  cin >> N;
  for (int i(0); i != N; ++i) cin >> init_col[i], adj[i].clear();
  for (int i(1), x(0), y(0); i != N; ++i) {
    cin >> x >> y, --x, --y;
    adj[x].push_back(y), adj[y].push_back(x);
  }
  did = 0;
  pre(0, -1);
  build(1, 0, did);
  cin >> Q;
  cout << node[1][1].pr << '\n';
  for (int p(0); Q--;) {
    cin >> p, --p;
    flip(1, 0, did, li[p], ri[p] + 1);
    cout << node[1][1].pr << '\n';
  }
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...