\(T1\)写了一个随机化贪心拿了\(20\)，\(T2\)水了一个\(prufer\)的分
写\(T2\)的时候居然认为边双是有向图的概念，暴搜也没有打出来
毕竟放假之前最多也只有三次考试了
首先要了解什么是霍尔定理
设\(M(U)\)为与\(U\)中的点相连的点集，一个二分图\(U,V(|U|<=|V|)\)存在完美匹配，满足对于任意点集\(x\inU\)都有|\(M(X)|>=|X|\)
因为要去枚举每一个子集，所以复杂度是\(3^n\)的
但是可以证明在题目条件下,只需要对每个左边的连续区间验证霍尔定理
考虑反证法,假如我们左边选了很多段连续区间,只考虑两段的情况,其余情况是类似的
先把所有没有和左边点相连的右边点去掉,那么对于每个左边的连续区间,与其相邻的右边点也是一个连续区间
那么我们分两种情况讨论:
\(1\):左边两段在右边的对应点是两段区间如果左边两段分别验证霍尔定理都合法,那么左边这两段的并也一定合法
\(2\):左边两段在右边的对应点是一段区间
那么我们考虑把左边两段中间的点也选上,根据条件右边的点不会变多,这样的限制显然更紧
所以没有必要选择左边不连续的多段验证霍尔定理
只需要枚举\(n^2\)个区间就可以了
先把所有询问按照左端点从小到大排序
因为区间没有包含关系，那么排完序之后左右端点一定都是单调递增的，那么就可以用前缀和处理
设\(a[i]\)为石子个数的前缀和,\(b[i]\)为每一次操作中实际选择的石子的前缀和
注意这里是实际选择的，而不是题目中要求选择的
因为实际选择的一定要满足霍尔定理，因为你已经选了这些了
但是题目中要求的你不一定全选
对于没有被询问包含的石子，要把它们的个数置成\(0\)，否则会影响结果
那么根据霍尔定理对于任意的\(i\leqj\)，必定存在\(b_j-b_{i-1}\leqa_{r[j]}-a_{l[i]-1}\)
即\(b_j-a_{r[j]}\leqb_{i-1}-a_{l[i]-1}\)
此时左边和右边分别只有\(j\)和\(i\)，可以分开考虑
设\(s_i=b_i-a_{r[i]},t_i=b_{i-1}-a_{l[i]-1}\)
即对于任意的\(i\leqj\)，都有\(s_j\leqt_i\)
设当前询问在按照左端点排序时的排名为\(p\)
当前的答案就是区间\([1,p]\)中\(t\)的最小值减去区间\([p,m]\)中\(s\)的最大值
还要和想要的石子个数取一个\(min\)
考虑当前答案会对\(s\)和\(t\)数组造成什么影响
对于\(s\)，要在区间\([p,m]\)加上\(ans\)
对于\(t\)，要在区间\([p+1,m]\)加上\(ans\)
对于左右端点都在\([p+1,m]\)的区间，因为都加上了\(ans\)，所以减完之后关系不会改变
对于左右端点都在\([1,p-1]\)的区间，当前的答案不会影响到它们，所以也不用考虑
我们要考虑的只是左端点在\([1,p]\)，右端点在\([p,m]\)的区间
我们加上答案后不能违背霍尔定理，所以答案不能超过区间\([1,p]\)中\(t\)的最小值减去区间\([p,m]\)中\(s\)的最大值
不要忘了更新\(s\)和\(t\)数组
这个东西拿线段树维护一下就行了
首先,我们可以证明,答案的环会包含所有左上角到关键点左上角的最短路
如图,绿色线是最短路,如果我们按照蓝色的区域去划分的话
不如把黄色部分也划进来,这样答案不会更劣
接着,我们把每个点按顺序拆成\(4\)个点\(0,1,2,3\),每个点向顺时针的下一个点连边权为\(0\)的边
两个跨过一条边的点要连边权为权值的边
那么任何一个可以自交的环可以看做从左上角的\(1\)到左上角的\(3\)的一条路径
图中红色部分代表最短路,由于我们答案路径要包含最短路所以\((A0,A3),(A2,A3),(C0,C1),(C1,C2),(D0,D3),(D2,D3)\)之间不能连边
当然这还不够,我们还需要保证我们的路径能够把所有的关键点包起来
这就相当于是我们的路径不能经过关键点里面的\(4\)个点,在连边时去掉这些点即可