当前位置: 首页 > news >正文

CF2152G Query Jungle(线段树,重链剖分,*)

CF2152G Query Jungle

子树翻转,求没有黑色子孙的黑色点个数。套上 mincnt 标签和双生 rev 标签即可。不明白提交记录里的人都在写什么鬼。

Code

const int inf = 1 << 30;struct Node {int m1 = inf, mc1 = 0, m0 = inf, mc0 = 0;friend Node operator+(const Node& u, const Node& v) {Node w;w.m1 = min(u.m1, v.m1);w.mc1 = (u.m1 == w.m1 ? u.mc1 : 0) + (v.m1 == w.m1 ? v.mc1 : 0);w.m0 = min(u.m0, v.m0);w.mc0 = (u.m0 == w.m0 ? u.mc0 : 0) + (v.m0 == w.m0 ? v.mc0 : 0);return w;}
};struct Tag {int rev = false, x = 0;friend void operator+=(Node& u, const Tag& v) {if (v.x) {u.m1 += v.x;u.m0 -= v.x;}if (v.rev) {swap(u.m1, u.m0);swap(u.mc1, u.mc0);}}friend void operator+=(Tag& u, const Tag& v) {if (v.x) !u.rev ? u.x += v.x : u.x -= v.x;u.rev ^= v.rev;}
};
...
vector<Node> init(n);
folr(u, 0, n - 1) init[dfn[u]] = {sa[u] - a[u], a[u], c[u] - sa[u] - !a[u], !a[u]};
SegTree<Node, Tag> T(init);
auto calc = [&]() {auto tot = T.total();debug(tot.m1, tot.mc1, tot.m0, tot.mc0);return tot.m1 == 0 ? tot.mc1 : 0;
};
cout << calc() << '\n';
int q;
cin >> q;
while (q--) {int u;cin >> u, --u;auto info = T.at(dfn[u]);debug(u, info.m1, info.mc1, info.m0, info.mc0);T.add(dfn[u], dfn[u] + c[u], Tag{true, 0});int delta = info.m0 + info.mc0 - info.m1 - info.mc1;for (int v = fa[u]; ~v; v = fa[top[v]]) T.add(dfn[top[v]], dfn[v] + 1, Tag{false, delta});cout << calc() << '\n';	
}
http://www.hskmm.com/?act=detail&tid=25233

相关文章:

  • 代码随想录算法训练营第九天 | leetcode 151 卡特55
  • [题解] 分竹子
  • 分数规划
  • CSS - transition 粗浅记忆
  • 【MC】LittleTiles模组结构数据解析和版本迁移方案
  • 容器魔方导致盒子满了
  • 课程学习笔记——[大一秋]遗传学
  • P3067 [USACO12OPEN] Balanced Cow Subsets G
  • Vivado 2025 界面中文设置
  • 词汇学习——专业词汇
  • P4556 [Vani有约会] 雨天的尾巴 [模板] 线段树合并
  • P4550 收集邮票
  • P8110 [Cnoi2021] 矩阵
  • P9751 [CSP-J 2023] 旅游巴士
  • P9234 [蓝桥杯 2023 省 A] 买瓜
  • P1044 [NOIP 2003 普及组] 栈
  • P1080 [NOIP 2012 提高组] 国王游戏
  • 音响没声音
  • P1654 OSU!
  • DynamoDB十年演进:云原生数据库的技术革新
  • 完整教程:MySQL全量、增量备份与恢复
  • 10/5
  • 10/4
  • 嵌入式MCU
  • porting perf性能观测工具
  • Windows常用快捷指令
  • Python 在金融中的应用- Part 1 - 教程
  • QBXT2025S刷题 Day4
  • java学习日记9.25
  • porting 开源memtester