T1 Ice-cream Tycoon
题意：
一个商店，有两种操作：
-
（1）ARRIVE n c表示进货n个，每个c元。
-
（2）BUY n t表示一个买货的人要买n个，一共拿了t元钱。如果现在店里的货的数量大于等于n且最便宜的n个的价格小于等于t则将最便宜的卖给他。否则不卖。
思路:
简单题，一个线段树，节点存储货物的数量和价格，每次计算价格的时候向上更新总数和价格，用一个标记记录这段区间有没有卖掉
T2 New Year Tree
题意：
给出一棵 \(n\) 个节点的树，根节点为 \(1\)。每个节点上有一种颜色 \(c_i\)
\(m\) 次操作。操作有两种：
- \(1 u c\)：将以 \(u\) 为根的子树上的所有节点的颜色改为 \(c\)。
- \(2 u\)：询问以 \(u\) 为根的子树上的所有节点的颜色数量。
思路：
把dfs序存在pos数组中，并把每个节点第一次遍历到的时间点和第二次遍历到的时间点存到in和out数组中，这样就成功地把一棵树转换为了线性结构。对一棵子树进行操作时，只需对这棵子树的根节点两次遍历到的时间戳中间的部分进行操作即可。考虑到60位正好小于Long Long范围，状态压缩放到线段树上,把它分解
T3 Ping-Pong
题意：
有一个区间的集合，初始为空。当 \(c<a<d\) 或 \(c<b<d\) ，且 \((a,b),(c,d)\) 都在集合中时，你可以从区间 \((a,b)\) 移动到 \((c,d)\)。你需要支持下面的操作：
-
\(1 x y\)，加入一个新区间 \((x,y)\)。保证加入的区间长度严格单调递增。
-
\(2 a b\)，询问是否能从第 \(a\) 个加入的区间移动到第 \(b\) 个。
操作数 \(1≤n≤10e5\)，保证其他任何数字都是整数且不超过 \(10^9\)。
解法：
首先考虑两种移动的情况：
-
1.两个区间相交但并不包含
-
2.一个大区间包含一个小区间
对于1情况，这两个区间是可以互相到达的，对于2情况，我们可以从小区间跳到大区间，而不能从大区间到小区间。
1询问不太好想，考虑建一棵线段树，在插入新的区间之前有若干合并过的区间，那么在线段树上找一个节点打上标记，考虑新加入的区间长度严格单调递增，所以必定不被另一个区间所包含。所有右端点在该区间左端点右方或者左端点在该区间右端点左方的区间都是应与该区间合并的。使用并查集，把合并了的旧区间标记删除（最多logn个），打上新区间的标记。
对于2询问，我们直接从包含这个区间的合并区间往上跳包含它的合并区间，看能否跳到包含目标区间的合并区间。
T4 Life as a monster
题意
在一个王国里，有N个人。第i个人住在一个点上（xi, yi）。你是一个怪物，需要绕过王国，抓住所有N个人。
你从某个点开始（u，v）。
在1秒内，你可以从点（u，v）移动到点（u'，v'），其中|u'-u|≤1，|v'-v|≤1。这意味着在1秒内你可以移动到8个相邻的点。你也可以停留在同一位置（这毫无意义）。
你的旅程将是这样的：
你从（u，v）开始
你走到(x1, y1)的第一个人面前，立即抓住他。
然后你需要回到你的家，并休息2秒。
然后你去找位于（x2，y2）的第二个人，立即抓住他。
然后你需要回到你的家，休息2秒。
这样重复下去，直到你抓到所有N个人。
你必须处理2种类型的Q查询：
0 - 第i个人移动到某个新点（xi', yi'）。
1 - 如果你从点（u，v）开始，完成旅程的最短时间是多少？
在这个问题中，你将得到整数BASE和多个查询。你将不得不设置初始值T=0。
0类型的查询意味着指定的人移动到点（（a1 * T + b1）%BASE，（a2 * T + b2）%BASE）。
对于类型1的查询，你需要输出捕获所有的人的旅程的最小时间，如果你将从坐标（（a1 * T + b1）%BASE，（a2 * T + b2）%BASE）开始。你应该用计算出的时间更新T的值。
在第一行输入中，有三个整数N、Q和BASE（0≤N、Q≤105，0≤BASE≤109。在接下来的N行中，有两个整数xi和yi（0≤xi, yi≤BASE）--人们的坐标。
在下面的Q行中，有以下类型的查询：
0 i a1 b1 a2 b2
1 a1 b1 a2 b2
其中i是人的索引（1≤i≤N），a1、b1、a2、b2是前面提到的值（0≤a1、b1、a2、b2≤109）。
解题思路
考虑抓每一个人都是独立的，只需要找到去每一个点的最短距离\(\times2\)(要回来)，再加上2N-2秒的休息就行了。
Part 1 如何使抓人移动次数最短
根据题意，每一次移动可使横纵坐标之差分别减去0或1，所以移动次数最短就是横纵坐标差的最大值。
如下图，假设怪物在(-1,-1),人在(3,2),那么横坐标差了4，纵坐标差3，最少移动次数为4。
Part 2 如何计算
看上去速度很快，实则1e10。
设怪物所在位置为(x1,y1)，要抓的人在(x2,y2)，移动次数为S，根据Part1有：
$ S=max\left ( |x1-x2|,|y1-y2| \right )\( \)=max\left ( x1-x2,x2-x1,y1-y2,y2-y1 \right ) $
其实就是切比雪夫距离，我们知道切比雪夫距离和曼哈顿距离是可以互化的。
对点(x,y),把它转化为点(x+y,x-y),此时怪物在(x1-y1,x1+y1),人在点(x2-y2,x2+y2)
此时计算曼哈顿距离为
$max\left ( x1+y1-x2-x2,x2+y2-x1-y1,x1-y1-x2+y2,x2-y2-x1+y1 \right ) $
化简一下：
$max\left ( 2x1-2x2,2y2-2y1,2y1-2y2,2x2-2x1 \right ) \(，是所求的两倍！！（返程不用\)\times2$了）
剩下的交给动态二维偏序
T5 Tourists
不会
T6 New Year and Conference
题目描述
充满快乐的，Hyunuk将要举办一个关于将来的一年有多伟大的大会！
大会有 \(n\) 个讲座。Hyunuk有两个可供选择的会场\(a\)和\(b\)。对于n个讲座中的每一个，演讲者选择了两个时间区间\([sa_{i},ea_{i}]\)（\(sa_{i} \leq ea_{i}\)）和\([sb_{i},eb_{i}]\)（\(sb_{i} \leq eb_{i}\)）。如果大会在a会场举办，那么讲座就会在\(sa_{i}\)到\(ea_{i}\)的时间举行；如果大会在b会场举行，那么该讲座就会在\(sb_{i}\)到\(eb_{i}\)的时间举行。Hyunuk只能选定两个会场中的一个，然后所有讲座都要在那个会场举行。
两个讲座被称为冲突，当且仅当它们共用了同一个时间点。正式地，我们称一个在区间\([x,y]\)中举办的讲座和一个在\([u,v]\)区间举办的讲座冲突，当且仅当\(\max(x,u) \leq \min(y,v)\)。
我们称一个听众可以参加所有讲座的一个子集\(s\)，当且仅当这个子集中任何一对讲座都不冲突。注意：是否能参加这个子集\(s\)的可能取决于Hyunuk选择的是\(a\)会场或是\(b\)会场来举办大会
对于一个子集\(s\)，若在一个会场，观众可以参加，而在另一个会场，观众却不可以参加，那么它被称为“会场敏感的”。
对于观众来说，是否存在一个会场敏感的子集\(s\)是一个重要的问题，因为观众无法确定讲座时间是否会冲突。Hyunuk会开心当且仅当不存在任意一个会场敏感的子集。请判断Hyunuk是否会开心
解法：
我们考虑给每一个讲座一个随机值\(v[i]\),两个讲座冲突就加入\(v[i]\times v[j]\)的贡献，最后比较一下两个会场的贡献大小就行了。使用扫描线，每一扫到讲座的开始就把\(v[i]\)加入当前的可贡献SUM，扫到结束就从SUM里删除；搜到一个讲座开始计算\(v[i]\times\)之前的SUM的贡献。