线段树选记
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:
模拟一下可以发现，矛盾的情况有以下两种：
-
某两个区间最小值相同，但无交集。
-
某些最小值相同的区间的交集被另一个最小值更大的区间完全覆盖。
所以，可以想到按照区间的最小值，从大到小排序。
然后区间覆盖并集，查询交集是否被完全覆盖，从而得出矛盾。
题目中是要输出最先矛盾的位置，不难想到二分答案。
3.水果姐逛水果街1
题目描述
水果姐今天心情不错，来到了水果街。
水果街有n家水果店，呈直线结构，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。
学过oi的水果姐迅速发现了一个赚钱的方法：在某家水果店买一个水果，再到另外一家店卖出去，赚差价。
就在水果姐窃喜的时候，cgh突然出现，他为了为难水果姐，给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去，求每个问题中最多可以赚多少钱。
输入格式
第一行n，表示有n家店
下来n个正整数，表示每家店一个苹果的价格。
下来一个整数m，表示下来有m个询问。
下来有m行，每行两个整数x和y，表示从第x家店出发到第y家店。
Solution:
可以直接考虑如何合并两个区间。
记录每个区间的最小值、最大值、从左往右走的最大收益以及从右往左走的最大收益。
正确性显然。写颗线段树直接合并即可。
4.收割韭菜
问题描述
小张喜欢菜，他种下了一排共株韭菜种子，从左往右编号到，其中第株韭菜每天会长高厘米。
何老板来割韭菜了！
何老板接下来会进行次割韭菜操作，其中第次割韭菜发生在第天，他会把所有韭菜高度大于等于的部分全都割去。
何老板想知道，每次割韭菜割下的韭菜高度总和是多少？
输入格式
第一行，两个整数 \(n, m\)
第二行，\(n\) 个整数 \(A_1, A_2, ..., A_n\)
接下来 \(m\) 行，每行两个整数 \(D_i, B_i\)，描述一次割韭菜。