t2，对题解的一些补充说明和证明。 题解写的很玄，我来补一发，我完全没有用大眼观察法。 这里解释一下为什么 是正确的。 有的哥们可能会以为这个玩意的计数会和字符串的性质，比如 border 什么的，有一点关系，而且如果从容斥的角度上来讲的话这玩意还真的不是太好证明的。 我们需要写一个动态规划 表示构建字符串长 已经匹配到 的方案数，这个 一写出来就可以发现不管字符串是什么只要 和字符串长度固定，答案一定是固定的。 然后既然答案是永远不变的，那我们不妨考虑特殊情况，那显然所有情况和特殊情况的答案都是相等的。 我们考虑 然后每次钦定一个匹配的最早结束位置，然后可以得到一个和式，把这个和...

题解呢？？？？？？？？？？？？？？？？？？？？？？？

是模拟赛的T2喔。 今天的文章：霍尔定理其二 在我的洛谷博客中获得更好的阅读体验，谢谢喵。 思路都对的，线段树写错了，我好高兴。 对着想了一个小时，啥思路都没有，然后忽然发现可以看作是一个二分图完美匹配，而且这个二分图匹配还挺特殊的。 考虑这样的二分图：左边是 个点代表人数，右边是 个点代表房子，然后可以根据题意连一下边，然后存在每个人都满意的方案就等价于存在一个完美匹配，然后它等价于霍尔定理的某个形式。 （详见 霍尔定理其一 那我们显然的贪心思路是让左边点尽量多右边点尽量少，显然选连续的最划算，否则可以凑成连续的，我们设当前喜欢 的哥们有 个，那么一个区间的代价很容易计算: 左边： ...

#include<bits/stdc++.h> using namespace std; #define lowbit(x) x&(-x) #define endl '\n' int n; int a[2000005]; inline int read(){ char c = getchar();int x =0; while(c<'0' or c>'9')c = getchar(); while('0'<=c and c<='9')x= x*10+(c^48),c = getchar(); return x; }int ls[200000...

rt 我二分找到左端点比询问对象小的最大的左端点，然后前缀预处理出中右端点最大值，但是被卡了