10·20题解

T1

分别处理平行于x轴和平行于y轴的线。对于平行于x轴的情况，我们只需把所有三角形投影到x轴上变成区间，然后判断直线穿过了多少个区间即可。要注意不能是恰好穿过端点的情况。

T2

维护括号序列的经典方式是往栈里扔左括号，来右括号消掉一个。所以dp状态记录当前栈里有几个左括号的信息。设$f_{i,j,k}$表示在$(i,j)$位置上，此时栈里的括号个数是$k$的最长序列长度。如果我们倒着dp，即从终点往起点dp，每次扔进右括号进栈。那么最终的答案就是$f_{1,M,0}$。

但是还需要记录字典序最小的情况。我们通过以dp状态做结点，dp转移关系做边，进行一个图上搜索。要求字典序最小所以我们从起点往终点搜索。具体来说一个结点可以用四元组表示：$(i,j,k,dp_{i,j,k})$，搜索时我们采用以第四维度作为深度进行广搜。四个维度分别重命名为$(x,y,sum,len)$，那么len相同的节点我们给答案序列填的位置都是相同的。我们把所有当前len节点按照字符排序：空格最先搜，左括号其次，右括号最次。先搜空格保证我们把所有len相同的括号选项都能找到，扩展空格的时候len不变化。扩展括号的时候len会变化。所以当现在队列里所有节点都是同样len的时候，就可以优先给当前答案序列的位置填左括号，没有就填右括号。能成为填入选项的位置我们就继续搜他的后继节点。打上标记，这样一个位置只会被搜索一次。复杂度$O(R^2S)$.

T3

将连边方式转化为：每次连接$m-i+1$的所有倍数。这样的图的连通性每一天都跟原图是相同的，所以我们就用这个图进行后续查询。这样暴力连边的边数是$nlogn$级别的。我们就这样暴力建一棵树出来。将边权设置为这条边被加入的天数，发现a和b之间的最大瓶颈就是他们可以相见的天数。于是可以直接树链剖分或者kruskal重构树查询lca即可。

T4

首先分析发现一个数i可以被唯一确定就是$\exists k_1,k_2,k_1|i-1,k_2|i$。那么就想不重不漏的根据每个i究竟被哪些k整除i-1，哪些k整除i进行分类。这样分类i肯定是可以将所有i按照S和V进行分类的，那么定义$f(S,V)$表示只有S集合里的k可以整除i-1，只有V集合里的k可以整除i，满足这样条件i的个数。答案就应该是枚举所有的S和V，对f进行求和。但是f不好计算，于是很容易联想到容斥。类似定义一个$h(S,V)$表示钦定S集合里的k可以整除i-1，钦定V集合里的k可以整除i，满足这样条件i的个数。首先观察发现S和V集合肯定是不交的。其次我们假设S，V已经确定，如何计算$h(S,V)$，计算方式是求出$lcm(S),lcm(V)$,根据$lcm(S)x+1=lcm(V)y$，用扩展欧几里得算法去求出x，y的通解，写成通解形式后，可以写出i的通解，同样为一个线性形式，计算在n的范围内有多少个解非常简单，这样就可以求h了。求出h后我们根据h容斥计算f。这里辅助定义一个$g(S,V)$，S是恰好，V是钦定，其余与h，f相同。那么可以推导。

做完了。复杂度$O(3^mlogn)$