2021 牛客多校第四场 训练记录 暨 补题

太弱小了! 没有力量!

(又迟到了)

队友在激烈讨论签到题F, 我来了以后看榜去读题, 发现J很可做, 稍微推一下知道了是两个平均值最大子串, 印象里是二分平均值然后减去, 但是忘记接下来怎么做了. 蒋叶桢 30min 过了F, 后来又 1h2min +1 过 I, 然后我去问他, 最后想到了做法, 1h15min 过了 J. 之后蒋叶桢去玩构造了, 1h36min 过了. 之后开了B和E, B看上去是个期望, 但是平方搞不来. 我推了半天推出来一个贡献不是平方的🤣. E 也不会, 大概想到了连续区间异或同一个数之后的区间也是连续的, 没有想明白是怎么个连续法. 然后大家就下班了.

太菜了, 知识水平不足, 没人会期望数数这方面的东西; 不会思考, 关于异或的性质也不能很好地挖掘.

$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 \\ 0001 \\ 0010 \\ 0011 \\ 0100 \\ 0101 \\ 0110 \\ 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$.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
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;
}