线段树选记

1. [TJOI2018]数学计算

题目描述

小豆现在有一个数 \(x\)，初始值为 \(1\)。小豆有 \(Q\) 次操作，操作有两种类型：

1 m：将 \(x\) 变为 \(x \times m\)，并输出 \(x \bmod M\)

2 pos：将 \(x\) 变为 \(x\) 除以第 \(pos\) 次操作所乘的数（保证第 \(pos\) 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），并输出 \(x \bmod M\)。

Solution:

显然直接拿一个变量暴力乘会有问题。

我们可以考虑把操作序列当成一个区间来处理，使用线段树维护区间乘。

2.[USACO08JAN]Haybale Guessing G

题目描述

给一个长度为 \(n\) 的数组 \(q\) 个条件，数组中的数字互不相同，每个条件格式形如 \(l_i,r_i,x_i\) 表示这个数组的区间 \([l_i,r_i]\) 内的最小值为 \(x_i\)，输出最早与前面的条件有矛盾的条件的编号，如果所有条件都不发生矛盾，输出 \(0\)。

Solution:

模拟一下可以发现，矛盾的情况有以下两种：