2021 牛客多校第四场 E.Tree Xor @ Wings            分类 ACM
发布于 星期日, 八月 15 日, 2021 年
更新于 星期日, 八月 15 日, 2021 年

题目

题意

$n$ 个点的树, 每个点有一个区间 $[l_i, r_i]$, 同时还有边权$w_i$, 要给每个点确定一个值, 这个值要在 $[l_i, r_i]$ 之间, 同时满足和他相邻的点的值为这个值异或上邻接的边(相邻的点也要满足在他自己的区间范围内). 问有多少种情况.

$1 \le n \le 10^5, 0 \le l_i < r_i < 2^30, 0 \le w_i < 2^30$

题解

(当时想到了某一段区间异或上同一个数还是一段连续的区间, 但是没有想明白是怎样的区间, 然后就光荣下班了.

第二天还是第三天有场cf, 就又遇到这样的问题, 连续区间异或同一个数, 然后推了挺久的, 给推出来了.)

先来看前几步思考. 首先可以发现, 两点之间的路径是唯一的, 所以任意两点都满足异或某个值的关系, 而这个值就是边上的权值异或起来. 这样这题就和树没什么关系了.

然后只要确定一个点, 那么接下来所有点都确定了. 那么一个区间里的数, 同时异或上某个值, 得到的是另一个点的取值范围限制, 这个限制当然要和本身的限制取一个交集. 如果把所有点的限制都通过其他点的限制区间异或得到的区间, 加上自己的区间, 取一个交集来找到, 那么最终每个点的取值范围, 也都满足异或的这个条件. 而每个点的取值个数都应该是相同的(否则不满足异或的这个条件). 所以我们可以把所有区间都异或到某个点, 然后做区间交, 得到的交集大小就是答案了.

(emm好像说的不是很好, 算了)

接下来手玩一下可以发现, 一个连续区间, 异或上同一个数, 得到的区间也可能是连续的. 比如 $[0, 7]$ 这个区间, 随便异或哪一个数, 得到的区间都是连续的. 为什么呢, 把他写成二进制来看:

$$ \begin{aligned} 0000 \newline 0001 \newline 0010 \newline 0011 \newline 0100 \newline 0101 \newline 0110 \newline 0111 \end{aligned} $$

可以发现, 这些数的前 $3$ 位(第 $0, 1, 2$ 位)恰好含有所有的情况, 即 $2^3$ 个, 第 $3$ 位以上都是一样的. 那么这些位同时异或上一个数, 得到的结果是, 这些数的前三位还是恰好所有情况. 而第 $3$ 位往上还是一样的, 所以这些数又连续了.

那么可以很容易发现, 如果从 $0$ 开始, 到某一个数 $x$, 就可以和"倍增"一样取一段区间, 这样就有 $O(\log x)$ 个区间.

举个例子, $[0, 14]$ 分成 $[0, 7], [8, 12], [13, 14]$ 这三个区间, 这三个区间异或上同一个数, 还是连续的三个区间, (可能会因为恰好连续是两个甚至一个, 但是不管怎么样一定是三个连续的区间组合).

但题目是考虑 $[l, r]$ 的区间, 这要怎么做呢? 可以先考虑 $[0, r]$ 的区间的贡献, 然后再减去 $[0, l-1]$ 的贡献.

算区间交集可以用权值线段树, 把 $[0, r]$ 异或得到的 $\log$ 个区间的位置都加 $1$, $[0, l-1]$ 异或得到的 $\log$ 个区间的位置都减 $1$. 由于不好离散化, 所以考虑动态开点. 记录最大值和最大值出现次数, 这个和第二场A差不多. 最后只需要看一下根的最大值是不是 $n$, 是的话输出次数, 不是的话输出 $0$.

代码
struct Node {
  int l, r, mid;  // 不再利用完全二叉树的下标性质
  int lch, rch;        // 而是直接分配下标, 从而动态开点
  int mx, tag, cnt;         // 初始值需要满足可以在开点时赋值, 如全0
} t[MAXM]; // 预先估计一下点的个数
int idx = 0, root = -1;
/* 动态开点, 左右儿子没开, 为0; 返回新建节点标号 */
int newNode(int l, int r) {
  t[++idx] = Node{l, r, (l+r)>>1, 0, 0, 0, 0, r-l+1};
  return idx;
}
/* 初始化线段树, 建立一个 [1, n] 区间的节点 */
void init(int _n) {
  root = newNode(1, _n);
}
/* 更新一条完整的线段 */
void updateNode(int u, int d) {
  t[u].mx += d;
  t[u].tag += d;   //打上标记, 不再往下
}
/* 将标记下放 */
void pushDown(int u) {
  if (!t[u].lch)  // 第一次访问, 开点
    t[u].lch = newNode(t[u].l, t[u].mid);
  updateNode(t[u].lch, t[u].tag);
  if (!t[u].rch)
    t[u].rch = newNode(t[u].mid+1, t[u].r);
  updateNode(t[u].rch, t[u].tag);
  t[u].tag = 0;
}
/* 由左右儿子线段合并更新当前线段 */
void pushUp(int u) {
  t[u].cnt = 0;
  t[u].mx = max(t[t[u].lch].mx, t[t[u].rch].mx);
  if (t[u].mx == t[t[u].lch].mx)
    t[u].cnt += t[t[u].lch].cnt;
  if (t[u].mx == t[t[u].rch].mx)
    t[u].cnt += t[t[u].rch].cnt;
}
/* 区间修改 */
void update(int l, int r, int d, int u = -1) {
  if (u == -1) u = root;
  if (t[u].l == l && t[u].r == r)
    updateNode(u, d); // 找到对应线段更新
  else {
    pushDown(u);  // 访问u的儿子线段, 需要先下放标记更新
    if (l > t[u].mid)
      update(l, r, d, t[u].rch); //更新的线段全在该区间右边
    else if (r <= t[u].mid)
      update(l, r, d, t[u].lch); // 全在左边
    else { // 跨越了左右两边
      update(l, t[u].mid, d, t[u].lch);
      update(t[u].mid+1, r, d, t[u].rch);
    }
    pushUp(u);  // 由儿子线段的更新后的值计算当前线段值
  }
}

int n, w[MAXN];
PII range[MAXN];
vector<PII> G[MAXN];

void dfs(int u, int f, int d) {
  w[u] = d;
  for (auto[v, x] : G[u]) if (v != f)
    dfs(v, u, d ^ x);
}

vector<PII> getRange(int x, int m) {
  vector<PII> res;
  int p = 0;
  m++;
  for (int k = 30; ~k; k--) {
    if (m >= (1<<k)) {
      int t = p ^ x;
      t = (t>>k)<<k;
      res.emplace_back(t, t + (1<<k) - 1);
      p += 1<<k;
      m -= 1<<k;
    }
  }
  return res;
}

void add(int x, int m, int d) {
  vector<PII> rg = getRange(x, m);
  for (auto[l, r] : rg)
    update(l+1, r+1, d);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    range[i] = {l, r};
  }
  for (int i = 1; i < n; i++) {
    int u, v, x;
    scanf("%d%d%d", &u, &v, &x);
    G[u].emplace_back(v, x);
    G[v].emplace_back(u, x);
  }
  dfs(1, 0, 0);
  init(1<<30);
  for (int i = 1; i <= n; i++) {
    auto[l, r] = range[i];
    add(w[i], r, 1);
    if (l)
      add(w[i], l-1, -1);
  }
  printf("%d\n", t[root].mx == n ? t[root].cnt : 0);
  return 0;
}

留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch