一道优先队列或是线段树，一道找性质
T1:
题面：
众所周知，九条可怜家里有矿。
你可以把可怜家的矿场抽象成一条数轴。可怜家有nn种矿，第ii种矿可以从[li,ri]的任意位置开采得到。
这个暑假，地理老师给了可怜一个列表：可怜的暑假作业就是收集齐这些矿石。为了保证可怜的安全，可怜的爸爸选定了m个相对安全的采矿点，第ii个采矿点的坐标为ai。可怜只能选择其中一个采矿点开采她需要的矿石。
可怜是一个马虎的女孩子。暑假刚开始没多久，可怜就把老师的列表弄丢了。唯一的线索是，列表上的所有矿石都是可怜家有的：一共有2n−12n−1种可能的列表。
可怜现在想要知道，在所有的可能的任务列表中，有多少种是她能够在某一个安全的采矿点完全收集齐的。
题解：
自己被自己的想法卡了，哇，hanpiLKX，考虑怎么处理重复的情况，如果有容斥的话，就是把每一个采矿点分开来看了，然而并不用，完全可以把之前的贡献计入当前采矿点，对于维护区间信息求求你想想线段树好吗？
对于重复的区间，我们就区间减1，然后当前采矿点的贡献就是2^(总)-2^(-1)，当然也可以用差分转换为单点修改，把 l -1，r+1 +1；
当然还有一种是优先队列的写法，大致思路同上（感觉就是暴力？？？？）
T2：
题面：
可怜不喜欢括号序列，但是她发现总是有人喜欢出括号序列的题。
为了让全世界都能感受到她的痛苦，她想要写一个转换器：它能把普通的小写字符串转换成长度相同的合法的括号序列。
在可怜的构思中，这样的转换器需要满足如下两个条件：
1．结果的括号序列必须要是合法的，即左右括号必须要是相匹配的。
2．对于一堆相匹配的左右括号，他们所在的位置原来的小写字母必须相同。
举例来说，对于字符串aabaab，()(())就是一个合法的答案，而()()()不满足第二个条件， (((())不满足第一个条件。
可怜发现对于一个小写字符串，有时候有很多满足条件的括号序列，有些时候一个都没有。
于是可怜给出了一个小写字符串，她想让你帮她算一下，有多少个不同的子串满足能转换成合法的括号序列。
题解：
首先暴力就是枚举栈底（也可以理解为左端点），然后就像普通括号匹配去做，遇到一样的就弹栈，不一样就加进来，如果栈地为空则表明匹配成功，注意！！！这道题有字母的限制所以不能全部hash成括号
时间复杂度 O（n^2）
考虑优化，注意到一个性质：当栈中元素在不同次弹栈后是一样的，就说明这两个位置之间的序列是满足条件的，那么遇到连续的就统计（两个两个的匹配就是n*(n-1)/2）